The author of this paper is Ronald L. Rivest . Rivest (along with Leonard Adleman and Adi Shamir) invented the RSA cryptosystem and is arguably one of the most famous and influential cryptographers of our age. In 2002 he received the Turing Award. [Ronald Rivest](https://en.wikipedia.org/wiki/Ron_Rivest) received a BSc in Mathematics from Yale University in 1969 and a PhD in Computer Science from Stanford in 1974. He is a member of MIT’s Computer Science and Artificial Intelligence Laboratory.  This paper was published in 1997. Internet payments were still rather new. `https` was introduced in 1994 by Netscape and Amazon was founded that same year. The business models that would eventually sustain the internet were still being defined. Rivest would go on to start Peppercoin Inc in 2001, a micropayments company that used a lot of the ideas laid out in this paper. Peppercoin raised $\$15$ M in venture capital and was acquired in 2007. Here is a quick overview of some of the topics Rivest believes are important for understanding this paper: **Public-keys and Private-keys** The concept of public-key and private-key come from Public-key cryptography. Public-key cryptography is a set of cryptographic protocols based on algorithms that require two separate keys: - Private-key - which as the name indicates is meant to be secret - Public-key - which is public / visible to others These two keys are mathematically linked. In public-key cryptography the public key is used to encrypt plaintext, where the private key is used to decrypt cipher text. **Digital Signatures** Digital signatures make heavy use of public-key cryptography. You can think of a digital signature as somewhat similar to a physical signature. A digital signature is also used to prove the authenticity of a document/digital message. A digital signature binds an identity to a message. Only the person with the private key can produce valid signatures. Anybody with access to the public key can test the validity of the signatures. Say alice wants to digitally sign a message *m*. In order to do that Alice must have: - Private-key (signing key) - $KEY_{private}$ - Public-key (verification key) - $KEY_{public}$ Alice then uses the *signing* function to produce a valid signature: $$signing(message, KEY_{private}) \rightarrow signature$$ Don’t worry about the internals of the *signing* function. What you need to know is that it takes a *message* and the Private-key and it will produce a signature (a short string). Again, only a person who possesses a private key can produce a valid signature. Anyone can use the public key to verify the signature: $$verify(m,signature,KEY_{public}) \rightarrow true\ or\ false$$ **Hash Functions** A hash function takes a string of characters of arbitrary length (called message) and maps it to another string of characters of fixed length (called a hash value or simply hash). Bitcoin uses a hash function called SHA-256. Let’s look at an example: $$SHA-256(fermat) = 5e494e69...139dab5e$$ In this example the input/message is ‘fermat’ and the output/hash is 32 byte hash (I omitted part of the hash). Note that the length of the output/hash is always the same regardless of the size of the input. If you are an OS X user you can compute the SHA-256 hash value of 'fermat' by running the following command in your terminal: ``` echo -n fermat | shasum -a 256 ``` Here are 4 properties of a hash function that are important to note: - it is easy to compute the hash value for any given message - it is infeasible to generate a message from its hash - it is infeasible to modify a message without changing the hash - it is infeasible to find two different messages with the same hash. Whereas in the external indicator scenario, the receiver had to wait for the result of the Massachusetts State Lottery to know if they had a winning ticket, in this case they can know immediately. An easy way to understand this is to just think of two parties, Alice and Bob. Bob wants to download Alice’s website and therefore needs to pay her 1 cent by issuing a lottery ticket. Here is how it plays out: 1. Alice picks a 30 digit decimal number $w$ and computes $h(w)$, the MD5 hash of $w$ 2. Alice sends $h(w)$ to Bob 3. Bob writes $h(w)$ in the *winning number indicator* field of the lottery ticket 4. Bob picks a 3 digit ticket number and writes it in the lottery ticket 5. Bob gives the lottery ticket to Alice (which has a $\$10$ face value) 6. Alice checks if the 3 digit ticket number matches the last 3 digits of $w$. If that is the case, Alice got a winning lottery ticket and she can go redeem it for the face value. The idea in PayWord is to try to minimize the number of public-key operations required per payment, using hash operations instead whenever possible. You can [read more about it here](https://people.csail.mit.edu/rivest/RivestShamir-mpay.pdf). In this scenario, let’s say you issue a lottery ticket with a face value of $\$10$. You set a winning number indicator to be the last 3 digits of the Massachusetts State Lottery. Whenever the lottery result is announced, the recipient checks the 3 digit ticket number in the lottery ticket you gave him against the last 3 digits of the Massachusetts State Lottery. If those match he knows he can go redeem $\$10$ from the bank that was set to be the payer. There are 1000 possible results for the last 3 digits of the Massachusetts State Lottery, therefore the recipient has a $\frac{1}{1000}$ chance of winning. As a result, the expected value of the lottery ticket is 1 cent ($\$10 \times \frac{1}{1000}$).