Public-key encryption

Relevant readings: Katz and Lindell 9.3, 11.3–11.4, 12.1, 12.4

Discrete logarithms, again

We recall in this section some facts about cyclic groups from Lecture 4.

Let \(G\) be a (multiplicative) group. Then we define “group exponentiation” as the result of multiplying an element \(x \in G\) with itself \(k\) times: $$x^k = \underbrace{x \cdot x \cdots x}_{\text{$k$ times}}.$$ If \(k = 0\), then \(x^0 = e\), the identity element of \(G\).

A finite group \(G\) is cyclic if there is an element \(g \in G\) such that for all \(x \in G\) there is an integer \(k\) with \(x = g^k\); we call such \(g\) a generator of \(G\). For arbitrary \(a \in G\), the set of all powers of \(a\) forms a cyclic subgroup of \(G\), called the subgroup generated by \(a\), denoted by \(\gen{a}\): $$\gen{a} = \Set{a^0, a^1, \ldots}.$$ If \(g\) is a generator of \(G\), then \(\gen{g} = G\).

Suppose \(G\) is a finite cyclic group of order \(n\), and let \(g\) be a generator of \(G\) and \(h \in G\) be an arbitrary element. The discrete logarithm of \(h\) with respect to \(g\) is the unique integer \(x \in \ZZ_n\) such that \(g^x = h\). Group exponentiation and discrete logarithms are inverses of each other.

Intractable problems involving cyclic groups

We recall several computational problems that can be defined for any class of cyclic groups.

The discrete logarithm problem

The discrete logarithm problem (DLP) in a cyclic group \(G\) with generator \(g\) is to compute \(\log_g h\) for an element \(h \in G\) (i.e., find the unique integer \(x \in \ZZ_n\) for which \(g^x = h\) holds).

The Diffie–Hellman problems

Related (but not equivalent) to the DLP are the Diffie–Hellman problems. There are two important variants: the computational Diffie–Hellman (CDH) problem and the decisional Diffie–Hellman (DDH) problem.

The CDH problem for a cyclic group \(G\) is to compute \(g^{ab}\), given the generator \(g\) and elements \(g^a, g^b\). The CDH assumption is that it is hard to solve the CDH problem, i.e., there’s only a negligible probability of doing so. There is a (polynomial-time) reduction from CDH to DLP, which works as follows:

• Given \(g^b\), compute \(b\) using an algorithm for DLP.

• Then compute \(\left(g^a \right)^b = g^{ab}\).

Thus CDH is no harder than DLP, i.e., \(\textsf{CDH} \le_p \textsf{DLP}\).¹

The DDH problem for a cyclic group \(G\) is to distinguish \(g^{ab}\) from an element \(g^c\) where \(c \in \ZZ_n\) is chosen uniformly at random. The DDH assumption states that it is hard to do so. There is a (polynomial-time) reduction from DDH to CDH, which works as follows:

• Given \(g\), \(g^a\), and \(g^b\), compute \(g^{ab}\) using an algorithm for CDH.

• Then check whether \(g^{ab} = g^c\).

Thus DDH is no harder than CDH, i.e., \(\textsf{DDH} \le_p \textsf{CDH}\).

Key exchange and Diffie–Hellman

The key exchange problem

Since private-key cryptography uses the same secret key for encryption and decryption, it begs the question that we haven’t addressed yet:

How can the parties share a secret key in the first place?

The key cannot just be sent over the insecure communication channel because an eavesdropping adversary would then be able to observe the key, thus it would no longer be secret.

One way to address this issue is to establish a key-distribution center (KDC). But such an approach to the key-distribution problem still require, at some point, a private and authenticated channel that can be used to share keys, which is impractical for open systems like the Internet.

The Diffie–Hellman protocol

In 1976, Whitfield Diffie and Martin Hellman published a paper titled “New Directions in Cryptography.” They observed that there are particular actions that are easy to do but difficult to undo, like it’s easy to shatter a glass vase but extremely difficult to put it back together. These actions can be used to derive interactive protocols for secure key exchange by having the parties perform operations that an eavesdropper cannot reverse.

This insight lead to one of the first steps toward moving cryptography out of the private domain and into the public one. To quote (Diffie and Hellman 1976):

We stand today on the brink of a revolution in cryptography. The development of cheap digital hardware has freed it from the design limitations of mechanical computing and brought the cost of high grade cryptographic devices down to where they can be used in such commercial applications as remote cash dispensers and computer terminals. In turn, such applications create a need for new types of cryptographic systems which minimize the necessity of secure key distribution channels …. At the same time, theoretical developments in information theory and computer science show promise of providing provably secure cryptosystems, changing this ancient art into a science.

We now describe the key exchange protocol that appeared in the original paper by Diffie and Hellman:

1. Alice and Bob agree upon a cyclic group \(G\) of order \(q\) (where \(q\) is \(n\) bits long) and a generator \(g \in G\).

2. Alice chooses \(a \getsrandom \ZZ_q\) uniformly at random and sends \(h_A \gets g^a\) to Bob.

3. Bob receives \(h_A\), then chooses \(b \getsrandom \ZZ_q\) uniformly at random and sends \(h_B \gets g^b\) to Alice.

4. Alice receives \(h_B\), and computes the shared key \(k_A \gets h_B^a = (g^b)^a = g^{ab}\).

5. Bob computes the shared key \(k_B \gets h_A^b = (g^a)^b = g^{ab}\).

Here, the shared key is a group element, not a bit string.

At the time, they did not provide a proof of security of their protocol mainly because the framework for formulating precise security notions, like what we have today, were not yet in place. Rather, the minimal requirement for security here is that the discrete logarithm problem must be hard relative to the underlying group \(G\). This is necessary but not sufficient, as it is possible that there are other ways of computing the key \(k_A = k_B\) without explicitly computing \(a\) or \(b\).

To be considered secure, the shared key \(g^{ab}\) should be indistinguishable from a group element picked uniformly at random for any adversary given \(g\), \(g^a\), and \(g^b\), which is exactly the decisional Diffie–Hellman (DDH) assumption. Thus a proof of security for the Diffie–Hellman protocol follows almost immediately from the DDH assumption.

Diffie–Hellman in practice

Though the Diffie–Hellman protocol in its basic form is not used in practice because it is insecure against man-in-the-middle attacks, it is found at the core of standardized key exchange protocols that are resilient to man-in-the-middle attacks, most notably in the Transport Layer Security (TLS) protocol.

Introducing public-key cryptography

Aside from a key exchange protocol, Diffie and Hellman introduced the notion of public-key cryptography. Instead of having a secret key for both encryption and decryption, we now have a pair of keys: a public key that is widely disseminated, and a private key that is kept secret. For this reason public-key cryptography is sometimes called asymmetric-key cryptography. Having generated these keys, a party can use them to ensure confidentiality for messages it receives using a public-key encryption scheme, or integrity for messages it sends using a digital signature scheme. Table 1 summarizes the cryptographic primitives in both the private-key setting and the public-key setting.

Why still study private-key cryptography?

There’s no doubt that public-key cryptography is strictly stronger than private-key cryptography. But the answer to the question is simple: private-key cryptography is much more efficient than public-key cryptography, and should be used in settings where it is appropriate.

For example, we don’t use public-key cryptography to directly encrypt the actual message we want to send, but rather, we use it to encrypt the (symmetric) key used to encrypt the message, which was encrypted using private-key cryptography.²

The public-key encryption syntax

Like what we did in Lecture 1, we formally define a public-key encryption scheme as follows:

Security against chosen-plaintext attacks

We recall the IND-EAV game from Lecture 6, but we now define it for a public-key encryption scheme \(\Pi = (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\) and an adversary \(\mathcal{A}\) as follows:

1. \(\Gen{\texttt{1}^n}\) is run to obtain keys \((\pk, \sk)\).

2. The adversary \(\mathcal{A}\) is given \(\pk\) and outputs a pair of messages \(m_{\texttt{0}}, m_{\texttt{1}} \in \mathcal{M}_{\pk}\) of equal length.

3. A uniform bit \(b \in \Set{\texttt{0}, \texttt{1}}\) is chosen. Then the ciphertext \(c \getsrandom \Enc{\pk}{m_b}\) is computed and given to \(\mathcal{A}\). We refer to \(c\) as the challenge ciphertext.

4. \(\mathcal{A}\) outputs a bit \(b^\prime\).

5. \(\mathcal{A}\) wins if \(b^\prime = b\).

The main difference between the IND-EAV game presented here and that from Lecture 7 is that here \(\mathcal{A}\) is given the public key \(\pk\). Furthermore, we allow \(\mathcal{A}\) to choose their messages \(m_{\texttt{0}}\) and \(m_{\texttt{1}}\) based on this public key. This is essential when defining security of public-key encryption since it makes sense to assume that the adversary knows the public key of the recipient.

In effect, we’re giving away \(\mathcal{A}\) access to the encryption oracle for free! This makes sense since \(\mathcal{A}\) is assumed to know the algorithm Enc, thus given \(pk\), they can encrypt any message \(m\) by simply computing \(\Enc{\pk}{m}\). As a consequence, EAV-security and CPA-security are equivalent in the public-key setting:

This is unlike in private-key encryption, where there are schemes that are EAV-secure but not CPA-secure.

ElGamal encryption

In 1985, Taher ElGamal observed that the Diffie–Hellman protocol can be adapted to give a public-key encryption scheme, which paved the way to the ElGamal cryptosystem, which we will describe below.

Let \(G\) be a cyclic group and a generator \(g \in G\) such that the DDH assumption holds in \(G\). Then the ElGamal cryptosystem defines a triple of PPT algorithms \((\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\) as follows:

To see that decryption succeeds, let \((c_1, c_2) = (g^y, h^y \cdot m)\) with \(h = g^x\). Then $$\hat{m} = \frac{c_2}{c_1^x} = \frac{h^y \cdot m}{\left(g^y\right)^x} = \frac{\left(g^x\right)^y \cdot m}{g^{xy}} = \frac{g^{xy} \cdot m}{g^{xy}} = m.$$

References

• Diffie, Whitfield, and Martin E. Hellman. 1976. "New Directions in Cryptography." IEEE Transactions on Information Theory 22 (6): 644--54. https://doi.org/10.1109/TIT.1976.1055638.

• Katz, Jonathan, and Yehuda Lindell. 2021. Introduction to Modern Cryptography. 3rd ed. CRC Press.