 Public-key cryptography

The concept of public-key encryption is simple and elegant, but has far-reaching consequences.

Public-key encryption

Let {Ee: e e K.) be a set of encryption transformations, and let {Д/: d 6 K.) be the set of corresponding decryption transformations, where K. is the key space. Consider any pair of associated encryption/decryption transformations (Ee, Dd) and suppose that each pair has the property that knowing Ee it is computationally infeasible, given a random ciphertext c € C, to find the message m e M such that Ee (m) = c. This property implies that given e it is infeasible to determine the corresponding decryption key d. (Of course e and d are simply means to describe the encryption and decryption functions, respectively.) Ee is being viewed here as a trapdoor one-way function (Definition 1.16) with cl being the trapdoor information necessary to compute the inverse function and hence allow decryption. This is unlike symmetric-key ciphers where e and d are essentially the same.

Under these assumptions, consider the two-party communication between Alice and Bob illustrated in Figure 1.11. Bob selects the key pair (e, d). Bob sends the encryption key e (called the public key) to Alice over any channel but keeps the decryption key d (called the private key) secure and secret. Alice may subsequently send a message m to Bob by applying the encryption transformation determined by Bob’s public key to get c = Ee(m). Bob decrypts the ciphertext c by applying the inverse transformation Д/ uniquely determined by d. Figure 1.11: Encryption using public-key techniques.

Notice how Figttre 1.11 differs from Figure 1.7 for a symmetric-key cipher. Here the encryption key is transmitted to Alice over an unsecured channel. This unsecured channel may be the same channel on which the ciphertext is bemg transmitted (but see §1.8.2).

Since the encryption key e need not be kept secret, it may be made public. Any entity can subsequently send encrypted messages to Bob which only Bob can decrypt. Figure 1.12 illustrates this idea, where A, A2, and A3 are distinct entities. Note that if A destroys message m after encrypting it to ci, then even A cannot recover m from c.

As a physical analogue, consider a metal box with the lid secured by a combination lock. The combination is known only to Bob. If the lock is left open and made publicly available then anyone can place a message inside and lock the lid. Only Bob can retrieve the message. Even the entity which placed the message into the box is unable to retrieve it.

Public-key encryption, as described here, assumes that knowledge of the public key e does not allow computation of the private key d. In other words, this assumes the existence of trapdoor one-way functions (§1.3. l(iii)).

1.50 Definition Consider an encryption scheme consisting of the sets of encryption and decryp- Figure 1.12: Schematic use of public-key encryption.

tion transformations {Ee: e e 1C} and {Д/: d € /С}, respectively. Tlie encryption method is said to be a public-key encryption scheme if for each associated encryption/decryption pair (e, d), one key e (the public key) is made publicly available, while the other d (the private key) is kept secret. For the scheme to be secure, it must be computationally infeasible to compute d from e.

1.51 Remark (private key vs. secret key) To avoid ambiguity, a common convention is to use the term private key in association with public-key cryptosystems, and secret key in association with symmetric-key cryptosystems. This may be motivated by the following line of thought: it takes two or more parties to share a secret, but a key is truly private only when one party alone knows it.

There are many schemes known which are widely believed to be secure public-key encryption methods, but none have been mathematically proven to be secure independent of qualifying assumptions. This is not unlike the symmetric-key case where the only system which has been proven secure is the one-time pad (§1.5.4).