Public-Key Cryptography

Public-Key Encryption

In a symmetric-key encryption scheme, both encryption and decryption use the same key. A public-key scheme disrupts this idea and uses different keys for encryption and decryption. The encryption key can be made public so that anyone can send encrypted messages. The decryption key is kept private, and only the holder of this key can decrypt these messages.

14.1. Security definitions for PKE

We start by introducing the syntax of a public-key encryption scheme. In the public-key setting, there is not one key but a key pair consisting of a private key and public key. These two keys must of course be correlated in some way. Therefore, a public-key encryption scheme must include a separate key generation algorithm $\KeyGen$ .

Definition 14.1.1 (Syntax & correctness of public-key encryption)

A public-key encryption (PKE) scheme consists of the following algorithms:

$\KeyGen$ : a randomized algorithm that takes no inputs (besides the security parameter, which we never write explicitly) and outputs a key pair $(\pk,\sk)$ , where $\pk$ is a public key and $\sk$ is a private key.
$\Enc$ : a randomized algorithm that takes a public key $\pk$ and plaintext $\ptxt \in \M$ as input and returns a ciphertext $\ctxt\in \C$ .
$\Dec$ : a deterministic algorithm that takes a private key $\sk$ and ciphertext $\ctxt\in\C$ as input, and returns a plaintext $\ptxt\in \M$ (or raises an error).

A PKE scheme is correct if the following program outputs $\mytrue$ with probability 1, for all $\ptxt \in \M$ :

(PK,SK):=KeyGen()(\pk,\sk) := \KeyGen()(PK,SK):=KeyGen()
C:=Enc(PK,M)\ctxt := \Enc(\pk,\ptxt)C:=Enc(PK,M)
return M==Dec(SK,C)\ptxt == \Dec(\sk,\ctxt)M==Dec(SK,C)

What does it mean for a key to be public? In the security definition, the library provides a way for the adversary/calling program to learn it. By making this change to the security definitions for encryption, and also ensuring that the correct key is used for encryption/decryption, we obtain definitions of CPA and CCA security for PKE:

Definition 14.1.2 (CPA security for public-key encryption)

A PKE scheme $\Sigma$ has security against chosen-plaintext attacks (CPA security) if the following two libraries are indistinguishable:

\lib{pk-cpa-real}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\cpapk(\,)

return

\pk

\cpaenc(\ptxt)

\ctxt := \Sigma.\Enc(\pk, \ptxt)

return

\ctxt

\indist

\lib{pk-cpa-rand}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\cpapk(\,)

return

\pk

\cpaenc(\ptxt)

\ctxt \gets \Sigma.\C(|\ptxt|)

return

\ctxt

Definition 14.1.3 (CCA security for public-key encryption)

A PKE scheme $\Sigma$ has security against chosen-ciphertext attacks (CCA security) if the following two libraries are indistinguishable:

\lib{pk-cca-real}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\ccapk(\,)

return

\pk

\ccaenc(\ptxt)

\ctxt := \Sigma.\Enc(\pk,\ptxt)

return

\ctxt

\ccadec(\ctxt)

return

\Sigma.\Dec(\sk,\ctxt)

\indist

\lib{pk-cca-rand}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\ccapk(\,)

return

\pk

\ccaenc(\ptxt)

\ctxt \gets \Sigma.\C(|\ptxt|)

\mathcal{D}[\ctxt] := \ptxt

return

\ctxt

\ccadec(\ctxt)

\mathcal{D}[\ctxt]

defined: return

\mathcal{D}[\ctxt]

return

\Sigma.\Dec(\sk,\ctxt)

As in the CCA security definition for SKE, ciphertexts generated by $\ccaenc$ are called challenge ciphertexts.

After seeing CPA and CCA security defined for PKE, you may also expect a definition of public-key authenticated encryption (AE). The spirit of AE is that no one can generate valid ciphertexts except the person who holds the secret key. But the spirit of public-key encryption is that anyone can encrypt ciphertexts. The two concepts are incompatible, so in the public-key world we will stop at CCA security.

If anyone can encrypt, why can't I tell whether something is an encryption of $\ptxt$ by re-encrypting $\ptxt$ myself?
This attack would work if PKE encryption were deterministic. But just like the case of SKE, public-key encryption cannot be deterministic. It is tempting to think that $\Enc(\pk,\ptxt)$ has no secrets, because both of its arguments may be public. But the randomness that $\Enc$ samples is a secret that the adversary doesn't know! The randomness used in an SKE's $\Enc$ algorithm is often included in its output, but this cannot be the case for a public-key scheme.

14.2. One-time vs. many-time encryption

Before describing an actual PKE scheme, let's first discuss a property of PKE that will make future security proofs easier.

In the symmetric-key world, it makes a difference whether a key is used to encrypt many plaintexts or just one. For example, OTP is secure when a key is used to encrypt one plaintext, but insecure when used for many encryptions. In the public-key world, there is no such distinction: Any PKE scheme that is secure for a single encryption is also secure for many. What this means is that if we need to prove CPA security for a PKE scheme, it's enough to prove a simpler property of security for a single encryption.

Claim 14.2.1 (One-time CPA security for public-key encryption)

Let $\Sigma$ be a PKE scheme. If the following two libraries are indistinguishable, then $\Sigma$ has CPA security:

\lib{pk-1cpa-real}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\cpaonepk(\,)

return

\pk

\cpaoneenc(\ptxt)

\ctxt^*

undefined:

\ctxt^* := \Sigma.\Enc(\pk, \ptxt)

return

\ctxt^*

\indist

\lib{pk-1cpa-rand}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\cpaonepk(\,)

return

\pk

\cpaoneenc(\ptxt)

\ctxt^*

undefined:

\ctxt^* \gets \Sigma.\C(|\ptxt|)

return

\ctxt^*

In these libraries, $\ctxt^*$ is static/global, and its value is fixed upon the first call to $\cpaoneenc$ . Subsequent calls to $\cpaoneenc$ don't do anything, so the adversary can obtain only a single ciphertext encrypted under the key pair. These libraries are written somewhat differently than in the definition of one-time secrecy for SKE (definition 5.3.2) since here the adversary is allowed to see $\pk$ before choosing its plaintext.

Proof:

The proof uses the following family of hybrids, parameterized by an integer $h$ :

\L_h

(\pk,\sk) := \Sigma.\KeyGen()

\cpapk(\,)

return

\pk

\cpaenc(\ptxt)

count := count + 1

count \le h

\ctxt \gets \Sigma.\C(|\ptxt|)

else:

\ctxt := \Sigma.\Enc(\pk, \ptxt)

return

\ctxt

This library responds with uniformly sampled ciphertexts the first $h$ times $\cpaenc$ is called, and thereafter responds with ciphertexts encrypted in the normal way. Thus:

In $\L_0$ , the else-branch is always taken, so the library behaves identically to $\lib{pk-cpa-real}$ . Every output of $\cpaenc$ is an actual encryption of the given plaintext.
If $q$ is the number of queries that the calling program makes to enc then in $\L_q$ the if-branch is always taken, so the library behaves identically to $\lib{pk-cpa-rand}$ . Every output of $\cpaenc$ is sampled uniformly.

It therefore suffices to show that $\L_h \indist \L_{h+1}$ for every $h \in \{0, \dots, q-1\}$ .

Hybrid Sequence:

We start with

\L_h

then isolate the case of

count == h+1

into its own conditional branch.

We can write the body of the new branch in terms of

\lib{pk-1cpa-*}

. Since this branch is executed at most once during the library's execution, this compound library calls

\cpaoneenc

at most once. Importantly, the library can still encrypt ciphertexts in the else-branch, because it knows the public key! This is the step in the proof that would fail with a symmetric-key scheme.

The if and else-if branches can now be unified, and the result is

\L_{h+1}

, as desired.

\L_h

(\pk,\sk) := \Sigma.\KeyGen()

\cpapk

( ):

return

\pk

\cpaenc

(

\ptxt

count := count + 1

count \le {}

h

h+1

\ctxt \gets \Sigma.\C(|\ptxt|)

else:

\ctxt := \Sigma.\Enc(\pk, \ptxt)

return

\ctxt

\link

\lib{pk-1cpa-real}

(\pk,\sk) := \Sigma.\KeyGen()

\cpaonepk

( ):

return

\pk

\cpaoneenc

(

\ptxt

\ctxt^*

undefined:

\ctxt^* := \Sigma.\Enc(\pk, \ptxt)

return

\ctxt^*

\lib{pk-1cpa-rand}

(\pk,\sk) := \Sigma.\KeyGen()

\cpaonepk

( ):

return

\pk

\cpaoneenc

(

\ptxt

\ctxt^*

undefined:

\ctxt^* \gets \Sigma.\C(|\ptxt|)

return

\ctxt^*

An analogous property is true for CCA security as well. Any PKE scheme that is CCA-secure for a single encryption is secure against many: Its proof is mostly the same as the previous one, and is left as an exercise.

Claim 14.2.2 (One-time CCA security for public-key encryption)

Let $\Sigma$ be a PKE scheme. If the following two libraries are indistinguishable, then $\Sigma$ has CCA security:

\lib{pk-1cca-real}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\ccaonepk(\,)

return

\pk

\ccaoneenc(\ptxt)

\ctxt^*

undefined:

\ctxt^* := \Sigma.\Enc(\pk, \ptxt)

return

\ctxt^*

\ccaonedec(\ctxt)

return

\Sigma.\Dec(\sk,\ctxt)

\indist

\lib{pk-1cca-rand}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\ccaonepk(\,)

return

\pk

\ccaoneenc(\ptxt)

\ctxt^*

undefined:

\ctxt^* \gets \Sigma.\C(|\ptxt|)

\ptxt^* := \ptxt

return

\ctxt^*

\ccaonedec(\ctxt)

\ctxt == \ctxt^*

: return

\ptxt^*

return

\Sigma.\Dec(\sk,\ctxt)

The $\lib{pk-1cca-rand}$ library does not maintain a dictionary $\mathcal{D}[\cdot]$ as in the usual CCA security definition (definition 14.1.3). This library generates only a single challenge ciphertext, so it would assign only one value to the dictionary, at $\mathcal{D}[\ctxt^*]$ . Instead, we simply rename $\mathcal{D}[\ctxt^*]$ to $\ptxt^*$ .

14.3. El Gamal encryption

Using the tools that you have learned about so far, how would you propose two users exchange secret messages when they don't have any shared secret key? First, they could run a key exchange protocol to establish a shared key. Then, they could use that key to encrypt their secret messages under a symmetric-key encryption scheme.

They can use DHKE for key exchange, but what would be a natural choice for the symmetric-key encryption scheme? In the previous section, we saw that it is enough for a PKE to be secure for only one encryption. Thus, perhaps they can consider something as simple as OTP. And since Diffie-Hellman outputs a key that is a cyclic group element, they could use a variant of OTP that uses the cyclic group operation (group multiplication) instead of xor.

If Bob wants to send Alice a private message $\ptxt$ following these recommendations, it looks like this:

If this picture makes sense to you, then you already understand our first PKE scheme, called El Gamal encryption after its creator Taher El Gamal. El Gamal encryption is what you get when you label Alice's message the public key and label Bob's two messages as the encryption of $\ptxt$ .

Construction 14.3.1 (El Gamal encryption)

Let $\G$ be a cyclic group of order $n$ with generator $g$ . El Gamal encryption is defined by the following algorithms:

\begin{aligned} \M &= \G \\ \C &= \G \times \G \end{aligned}

\KeyGen(\,)

\sk \gets \Z_\nmod

\pk := g^{\sk}

return

(\pk,\sk)

\Enc(\pk, \ptxt)

r \gets \Z_\nmod

\ctxt_1 := g^r

\ctxt_2 := \ptxt \cdot \pk^r

return

(\ctxt_1, \ctxt_2)

\Dec\bigl(\sk,(\ctxt_1,\ctxt_2)\bigr)

return

\ctxt_2 \cdot \ctxt_1^{-\sk}

Compared to the picture above, we have renamed values as follows:

\begin{aligned} a &\leadsto \sk & b &\leadsto r & C &\leadsto C_2 \\ A &\leadsto \pk & B &\leadsto C_1 \end{aligned}

Claim 14.3.2 (Security of El Gamal)

If the DDH assumption is true, then El Gamal encryption (construction 14.3.1) is CPA-secure.

Proof:

From claim 14.2.1, it suffices to prove that El Gamal is secure when encrypting one ciphertext. In other words, we will show that the following two libraries are indistinguishable:

\lib{pk-cpa1-real}

\KeyGen

\sk \gets \Z_\nmod

\pk := g^{\sk}

\cpaonepk(\,)

return

\pk

\cpaoneenc(\ptxt)

\ctxt^*

undefined:

\ctxt^* := \Enc(\pk,\ptxt)

r \gets \Z_\nmod

\ctxt_1 := g^r

\ctxt_2 := \ptxt \cdot \pk^r

\ctxt^* := (\ctxt_1, \ctxt_2)

return

\ctxt^*

\indist

\lib{pk-cpa1-rand}

\KeyGen

\sk \gets \Z_\nmod

\pk := g^{\sk}

\cpaonepk(\,)

return

\pk

\cpaoneenc(\ptxt)

\ctxt^*

undefined:

\ctxt^* \gets \C = \G \times \G

\ctxt_1 \gets \G

\ctxt_2 \gets \G

\ctxt^* := (\ctxt_1, \ctxt_2)

return

\ctxt^*

Hybrid Sequence:

[ [ ['96','add','hl'], ['13','add','hl'], ['14','add','hl'], ['92','add','hl'], ['20','remove','slide-up'], ['2','add','slide-down'] ], [ ['23','add','hl'], ['23','remove','hidden'], ['25','add','hl'], ['25','remove','hidden'], ['26','add','hl'], ['26','remove','hidden'], ['99','add','hl'], ['99','remove','slide-left'], ['93','add','hl'], ['93','remove','slide-left'], ['4','add','hidden'], ['96','remove','hl'], ['96','add','slide-left'], ['13','remove','hl'], ['13','add','hidden'], ['14','remove','hl'], ['14','add','hidden'], ['92','remove','hl'], ['92','add','slide-right'] ], [ ['23','remove','hl'], ['25','remove','hl'], ['26','remove','hl'], ['99','remove','hl'], ['93','remove','hl'], ['95','add','hl'], ['38','remove','slide-up'], ['20','add','slide-down'] ], [ ['42','add','hl'], ['42','remove','hidden'], ['43','add','hl'], ['43','remove','hidden'], ['96','add','hl'], ['96','remove','slide-left'], ['95','remove','hl'], ['95','add','slide-right'] ], [ ['42','remove','hl'], ['43','remove','hl'], ['96','remove','hl'], ['23','add','hl'], ['42','add','hl'], ['43','add','hl'], ['25','add','hl'], ['26','add','hl'], ['98','add','hl'], ['58','remove','slide-up'], ['38','add','slide-down'] ], [ ['95','add','hl'], ['95','remove','slide-right'], ['14','add','hl'], ['14','remove','hidden'], ['69','add','hl'], ['69','remove','hidden'], ['23','remove','hl'], ['23','add','hidden'], ['42','remove','hl'], ['42','add','hidden'], ['43','remove','hl'], ['43','add','hidden'], ['25','remove','hl'], ['25','add','hidden'], ['26','remove','hl'], ['26','add','hidden'], ['98','remove','hl'], ['98','add','slide-right'] ], [ ['95','remove','hl'], ['14','remove','hl'], ['69','remove','hl'], ['69','add','hl'], ['100','add','hl'], ['75','remove','slide-up'], ['58','add','slide-down'] ], [ ['77','remove','hidden'], ['101','add','hl'], ['101','remove','slide-left'], ['69','remove','hl'], ['69','add','hidden'], ['100','remove','hl'], ['100','add','slide-right'] ], [ ['101','remove','hl'] ] ]

The starting point is

\lib{pk-1cpa-real}

Since

\ctxt_1 = g^r

and

\pk^r

(used to compute

\ctxt_2

) do not depend on the choice of

\ptxt

, they can be sampled at the beginning of time.

At the beginning of time, the library samples

g^{\sk}

g^r

, and

\pk^r = g^{\sk \cdot r}

. The DDH assumption says that values distributed in this way are pseudorandom. The three-hop maneuver is not shown.

We can move the selection of

\ctxt_1

and

U

back into

\cpaoneenc

. These values are sampled uniformly.

Now

U

is distributed uniformly in

\G

, so

\ctxt_2

is a OTP ciphertext (in a OTP variant that uses the group operation in place of xor; see exercise 2.10). Thus,

\ctxt_2

is distributed uniformly, independent of

\ptxt

. After making this change, the result is

\lib{pk-1cpa-rand}

\lib{pk-1cpa-real}

\sk \gets \Z_\nmod

\pk := g^{\sk}

\cpaonepk

( ):

return

\pk

\cpaoneenc

(

\ptxt

\ctxt^*

undefined:

r \gets \Z_\nmod

\ctxt_1

{}:= g^r

{}\gets \G

\ctxt_2

{}:= \ptxt \cdot {}

\pk^r

U

{}\gets \G

\ctxt^* := (\ctxt_1, \ctxt_2)

return

\ctxt^*

14.4. The Fujisaki-Okamoto construction

In this section we describe how to efficiently convert any CPA-secure PKE into a CCA-secure one. The construction slightly breaks the usual abstraction of an encryption scheme, in an interesting way:

Definition 14.4.1

An encryption algorithm $\Enc$ is randomized, but in this section it will be useful to run the encryption algorithm with some externally determined random choices. We write $\Enc(\pk,\ptxt; R)$ to denote the result of running $\Enc(\pk,\ptxt)$ but setting the random choices of $\Enc$ to be $R$ . It is traditional to use a semicolon to separate the last argument. Note that $\Enc(\cdot,\cdot;\cdot)$ , with the randomness as an explicit third argument, refers a deterministic algorithm.

Using this new notation, what we usually write as $\Enc(\pk,\ptxt)$ refers to the process:

R \gets \mathcal{R}

return

\Enc(\pk,\ptxt; R)

$\mathcal{R}$ refers to the space of possible random choices made by $\Enc$ .

Example 14.4.2

The El Gamal encryption algorithm chooses an exponent $r \gets \Z_\nmod$ as its randomness, so $\mathcal{R} = \Z_\nmod$ above. Writing the encryption algorithm with this randomness as an explicit argument gives:

\Enc(\pk, \ptxt; r) = (g^r, \pk^r \cdot \ptxt).

In this section we will assume that every encryption algorithm's randomness comes from $\bits^\secpar$ . This is without loss of generality, because an encryption algorithm may use its randomness argument to seed a PRG and obtain as much randomness as needed.

The Fujisaki-Okamoto construction is a recipe for converting a CPA-secure PKE into a CCA-secure one, in the random oracle model. Its main idea is to encrypt (under the CPA scheme) plaintexts of the form $X$ using $\ro(X)$ as the randomness. When the receiver decrypts a ciphertext, she will check that it was encrypted with randomness $\ro(X)$ as expected—by re-encrypting it herself with that randomness!—and reject if this is not the case.

You may wonder why using $\ro(X)$ for encryption randomness is useful for CCA security. The reasoning is subtle and clever. “Valid” ciphertexts must have the form $\Enc\bigl(\pk, X; \ro(X) \bigr)$ , and in the random oracle model (it can be argued that) you can't produce a ciphertext of this form without first calling the random oracle at $\ro(X)$ . But if the adversary has previously called the random oracle at input $X$ , then the library has a chance to compute the ciphertext $\ctxt = \Enc\bigl(\pk,X; \ro(X)\bigr)$ and remember the association $\ctxt \leadsto X$ for later. The library is able to know that the decryption of $\ctxt$ should be $X$ , but it has deduced this fact without using the private key! When the library no longer needs the private key, we can apply the CPA security of the underlying PKE.

For technical reasons, $X$ is not the actual plaintext, but has the form $X = \ptxt \|S$ , where $S$ is chosen uniformly. Thus, an encryption of $\ptxt$ has the form $\Enc\bigl( \pk, \ptxt \| S; \ro(\ptxt\|S) \bigr)$ .

Construction 14.4.3 (Fujisaki-Okamoto)

Let $\Sigma$ be a PKE scheme, and $\ro$ be a random oracle with $\secpar$ output bits. Assume that $\Sigma.\Enc$ uses $\secpar$ bits of randomness. Then the Fujisaki-Okamoto PKE scheme consists of the following:

\begin{aligned}\Sigma^*.\K &= \Sigma.\K \\ \Sigma^*.\C(\ell) &= \Sigma.\C(\ell+\secpar) \\ \Sigma^*.\KeyGen &= \Sigma.\KeyGen \end{aligned}

\Sigma^*.\Enc(\pk,\ptxt)

S \gets \bits^\secpar

R := \ro(\ptxt \| S)

\ctxt := \Sigma.\Enc(\pk, \ptxt \| S; R)

return

\ctxt

            Σ∗.Dec(SK,C)\Sigma^*.\Dec(\sk,\ctxt)Σ∗.Dec(SK,C):
          
M∥S:=Σ.Dec(SK,C)\ptxt \| S := \Sigma.\Dec(\sk,\ctxt)M∥S:=Σ.Dec(SK,C)
R:=H(M∥S)R := \ro(\ptxt \| S)R:=H(M∥S)
if C≠Σ.Enc(PK,M∥S;R)\ctxt \ne \Sigma.\Enc(\pk,\ptxt \| S;R)C=Σ.Enc(PK,M∥S;R):
return err\myerrerr
return M\ptxtM

We will prove the security of Fujisaki-Okamoto using the following assumption about the underlying (CPA-secure) scheme.

Definition 14.4.4 (Unique randomness for a PKE)

An encryption algorithm $\Enc$ has unique randomness if for all $\pk$ and all $\ptxt$ , the function $\Enc(\pk,\ptxt; \cdot)$ is 1-to-1 (injective).

This property makes the Fujisaki-Okamoto construction easier to prove, but security can also be proven without it; see exercise 14.14.

Theorem 14.4.5 (Security of Fujisaki-Okamoto)

Suppose $\Sigma$ is a CPA-secure PKE scheme with unique randomness. Then construction 14.4.3 is CCA-secure in the random oracle model. From claim 14.2.2 it suffices to show that the scheme is CCA-secure with respect to a single encryption.

In other words, if:

\lib{pk-cpa-real}

(\pk,\sk) := \Sigma.\KeyGen()

\cpapk(\,)

return

\pk

\cpaenc(\ptxt)

\ctxt \gets \Sigma.\Enc(\pk)

return

\ctxt

\indist

\lib{pk-cpa-rand}

(\pk,\sk) := \Sigma.\KeyGen()

\cpapk(\,)

return

\pk

\cpaenc(\ptxt)

\ctxt \gets \Sigma.\C(|\ptxt|)

return

\ctxt

then:

\lib{pk-1cca-real+ro}

(\pk,\sk) := \Sigma.\KeyGen()

\ccaonepk(\,)

return

\pk

\ccaoneenc(\ptxt)

\ctxt^*

undefined:

\ctxt^* := \Enc(\pk,\ptxt)

S \gets \bits^\secpar

R := \ro(\ptxt \| S)

\ctxt^* := \Sigma.\Enc(\pk, \ptxt \| S; R)

return

\ctxt^*

\ccaonedec(\ctxt)

// return

\Dec(\sk,\ctxt)

\ptxt \| S := \Sigma.\Dec(\sk,\ctxt)

R := \ro(\ptxt \| S)

\ctxt \ne \Sigma.\Enc(\pk,\ptxt\|S;R)

return

\myerr

return

\ptxt

\ro(A)

\rotable[A]

undefined:

\rotable[A] \gets \bits^\secpar

return

\rotable[A]

\indist

\lib{pk-1cca-rand+ro}

(\pk,\sk) := \Sigma.\KeyGen()

\ccaonepk(\,)

return

\pk

\ccaoneenc(\ptxt)

\ctxt^*

undefined:

\ctxt^* \gets \Sigma.\C(\secpar)

\ptxt^* := \ptxt

return

\ctxt^*

\ccaonedec(\ctxt)

\ctxt == \ctxt^*

: return

\ptxt^*

// return

\Dec(\sk,\ctxt)

\ptxt \| S := \Sigma.\Dec(\sk,\ctxt)

R := \ro(\ptxt \| S)

\ctxt \ne \Sigma.\Enc(\pk,\ptxt\|S;R)

return

\myerr

return

\ptxt

\ro(A)

\rotable[A]

undefined:

\rotable[A] \gets \bits^\secpar

return

\rotable[A]

Proof:

One important idea in the proof is that an adversary cannot create a valid ciphertext if they have not already made the expected call to the random oracle $\ro(\ptxt\|S)$ . We formalize the idea as follows:

If $\Enc$ has unique randomness then the following algorithm returns $\mytrue$ with probability at most $1/2^\secpar$ :

\subname{guess}(\pk, X, \ctxt)

\ctxt^* := \Enc(\pk,X)

R \gets \bits^\secpar

\ctxt^* := \Enc(\pk,X; R)

return

\ctxt == \ctxt^*

The subroutine generates an encryption of $X$ and returns $\mytrue$ if the caller successfully predicted the resulting ciphertext. The encryption randomness $R$ is playing the role of a random oracle output that has not yet been sampled/observed. There are $2^\secpar$ choices of $R$ , and since $\Enc$ has unique randomness, each choice of $R$ leads to a distinct outcome $\ctxt^*$ . Since the caller's “guess” $\ctxt$ is fixed before $\ctxt^*$ is chosen, uniformly among $2^\secpar$ possibilities, the algorithm returns $\mytrue$ with probability at most $1/2^\secpar$ . (It may also be the case that $\ctxt$ is not one of the $2^\secpar$ possible ciphertexts, in which case the probability is zero.)

The formal details of the proof follow.

Hybrid Sequence:

[ [ ['11','add','hl'], ['259','add','hl'], ['18','add','hl'], ['20','add','hl'], ['263','add','hl'], ['256','add','hl'], ['276','add','hl'], ['61','remove','slide-up'], ['29','add','slide-down'] ], [ ['41','add','hl'], ['41','remove','hidden'], ['42','add','hl'], ['42','remove','hidden'], ['260','add','hl'], ['260','remove','slide-left'], ['45','add','hl'], ['45','remove','hidden'], ['281','add','hl'], ['281','remove','slide-left'], ['49','add','hl'], ['49','remove','hidden'], ['51','add','hl'], ['51','remove','hidden'], ['52','add','hl'], ['52','remove','hidden'], ['257','add','hl'], ['257','remove','slide-left'], ['3','add','hidden'], ['11','remove','hl'], ['11','add','hidden'], ['259','remove','hl'], ['259','add','slide-right'], ['18','remove','hl'], ['18','add','hidden'], ['20','remove','hl'], ['20','add','hidden'], ['263','remove','hl'], ['263','add','slide-left'], ['256','remove','hl'], ['256','add','slide-right'], ['276','remove','hl'], ['276','add','slide-right'] ], [ ['41','remove','hl'], ['42','remove','hl'], ['260','remove','hl'], ['45','remove','hl'], ['281','remove','hl'], ['49','remove','hl'], ['51','remove','hl'], ['52','remove','hl'], ['257','remove','hl'], ['262','add','hl'], ['52','add','hl'], ['92','remove','slide-up'], ['61','add','slide-down'] ], [ ['263','add','hl'], ['263','remove','slide-left'], ['262','remove','hl'], ['262','add','slide-right'], ['52','remove','hl'], ['52','add','hidden'] ], [ ['263','remove','hl'], ['19','add','hl'], ['51','add','hl'], ['21','add','hl'], ['23','add','hl'], ['122','remove','slide-up'], ['92','add','slide-down'] ], [ ['262','add','hl'], ['262','remove','slide-right'], ['256','add','hl'], ['256','remove','slide-right'], ['276','add','hl'], ['276','remove','slide-right'], ['22','remove','indent-2'], ['118','add','hl'], ['118','remove','hidden'], ['119','add','hl'], ['119','remove','hidden'], ['120','add','hl'], ['120','remove','hidden'], ['19','remove','hl'], ['19','add','hidden'], ['51','remove','hl'], ['51','add','hidden'], ['21','remove','hl'], ['21','add','hidden'], ['22','add','indent-1'], ['23','remove','hl'], ['23','add','hidden'] ], [ ['262','remove','hl'], ['256','remove','hl'], ['276','remove','hl'], ['118','remove','hl'], ['119','remove','hl'], ['120','remove','hl'], ['41','add','hl'], ['42','add','hl'], ['264','add','hl'], ['155','remove','slide-up'], ['122','add','slide-down'] ], [ ['265','add','hl'], ['265','remove','slide-left'], ['137','add','hl'], ['137','remove','hidden'], ['146','add','hl'], ['146','remove','hidden'], ['152','add','hl'], ['152','remove','hidden'], ['153','add','hl'], ['153','remove','hidden'], ['154','add','hl'], ['154','remove','hidden'], ['41','remove','hl'], ['41','add','hidden'], ['42','remove','hl'], ['42','add','hidden'], ['264','remove','hl'], ['264','add','slide-right'] ], [ ['265','remove','hl'], ['137','remove','hl'], ['146','remove','hl'], ['152','remove','hl'], ['153','remove','hl'], ['154','remove','hl'], ['13','add','hl'], ['267','add','hl'], ['187','remove','slide-up'], ['155','add','slide-down'] ], [ ['264','add','hl'], ['264','remove','slide-right'], ['259','add','hl'], ['259','remove','slide-right'], ['268','add','hl'], ['268','remove','slide-left'], ['13','remove','hl'], ['13','add','hidden'], ['267','remove','hl'], ['267','add','slide-right'] ], [ ['264','remove','hl'], ['259','remove','hl'], ['268','remove','hl'], ['270','add','hl'], ['282','add','hl'], ['12','add','hl'], ['137','add','hl'], ['274','add','hl'], ['219','remove','slide-up'], ['187','add','slide-down'] ], [ ['271','add','hl'], ['271','remove','slide-left'], ['216','add','hl'], ['216','remove','hidden'], ['217','add','hl'], ['217','remove','hidden'], ['270','remove','hl'], ['270','add','slide-right'], ['282','remove','hl'], ['282','add','slide-right'], ['12','remove','hl'], ['12','add','hidden'], ['137','remove','hl'], ['137','add','hidden'], ['274','remove','hl'], ['274','add','slide-left'] ], [ ['271','remove','hl'], ['216','remove','hl'], ['217','remove','hl'], ['271','add','hl'], ['45','add','hl'], ['280','add','hl'], ['49','add','hl'], ['257','add','hl'], ['146','add','hl'], ['118','add','hl'], ['119','add','hl'], ['120','add','hl'], ['273','add','hl'], ['253','remove','slide-up'], ['219','add','slide-down'] ], [ ['223','remove','hidden'], ['270','add','hl'], ['270','remove','slide-right'], ['282','add','hl'], ['282','remove','slide-right'], ['232','add','hl'], ['232','remove','hidden'], ['236','add','hl'], ['236','remove','hidden'], ['18','add','hl'], ['18','remove','hidden'], ['19','add','hl'], ['19','remove','hidden'], ['20','add','hl'], ['20','remove','hidden'], ['21','add','hl'], ['21','remove','hidden'], ['22','remove','indent-1'], ['23','add','hl'], ['23','remove','hidden'], ['274','add','hl'], ['274','remove','slide-left'], ['271','remove','hl'], ['271','add','slide-right'], ['45','remove','hl'], ['45','add','hidden'], ['280','remove','hl'], ['280','add','slide-right'], ['49','remove','hl'], ['49','add','hidden'], ['257','remove','hl'], ['257','add','slide-right'], ['22','add','indent-2'], ['146','remove','hl'], ['146','add','hidden'], ['118','remove','hl'], ['118','add','hidden'], ['119','remove','hl'], ['119','add','hidden'], ['120','remove','hl'], ['120','add','hidden'], ['273','remove','hl'], ['273','add','slide-right'] ], [ ['270','remove','hl'], ['282','remove','hl'], ['232','remove','hl'], ['236','remove','hl'], ['18','remove','hl'], ['19','remove','hl'], ['20','remove','hl'], ['21','remove','hl'], ['23','remove','hl'], ['274','remove','hl'] ] ]

The starting point of the proof is

\lib{pk-1cca-real+ro}

We can inline the calls to

\ro

made in

\ccaoneenc

and

\ccaonedec

. We can also remember the decryption of the challenge ciphertext

\ctxt^*

, as

\mathcal{D}[\ctxt^*]

, so that

\ccaonedec

does not need to recompute it. The reason we introduce a dictionary

\mathcal{D}[\cdot]

, even though the library assigns only one position in it, is because later hybrids will use more of it.

Suppose that in some call to

\ccaonedec(\ctxt)

, we see that

\rotable[\ptxt\|S]

is undefined; the adversary has not called the random oracle on this input. The library will return an error unless the adversary has somehow successfully anticipated the result of

\Sigma.\Enc

, with fresh randomness

\rotable[\ptxt\|S]

. Following the reasoning described earlier, such a prediction is successful only with negligible probability at most

1/2^\secpar

, when

\Sigma

has unique randomness. It makes a negligible difference to simply always return an error in this case.

Now

\ccaonedec()

returns an error unless the ciphertext has the form

\Enc(\pk,X; \ro(X))

, and the adversary has already called

\ro(X)

. So instead of decrypting ciphertexts the usual way in

\ccaonedec()

, we can compute the associated ciphertext at the time

\ro(X)

is called, and store its decryption for later use in

\ccaonedec()

. The change has no effect on the calling program.

Modify

\ccaoneenc()

so that, instead of using

\ro(\ptxt\|S^*)

as randomness for

\Sigma.\Enc

, it uses a freshly sampled value

R

unrelated to the random oracle. This changes the library's overall behavior only in the bad event that the adversary also queries

\ro(\ptxt\|S^*)

. We can mark the change with a bad event, and later argue that it has negligible probability.

Now

\ccaoneenc()

uses randomness for

\Sigma.\Enc

that is used for nothing else. This is exactly equivalent to calling

\Sigma.\Enc()

the usual way (i.e., as a randomized algorithm, without externally fixing its randomness). Furthermore, the secret key of

\Sigma

is no longer used anywhere in the library. Hence, we can apply the CPA security of

\Sigma

to replace ciphertext

\ctxt^*

with a uniformly chosen one. The three-hop maneuver is not shown.

Now

S^*

\ccaoneenc()

is used only to trigger the bad event, and does not affect what the adversary sees. We can therefore defer the choice of

S^*

to the end of time.

Finally, we can undo a previous change, moving decryption logic from

\ro()

back to

\ccaonedec()

. Then the only value in

\mathcal{D}[\cdot]

that is used is

\mathcal{D}[\ctxt^*]

, which we rename simply to

\ptxt^*

. As a result, we obtain

\lib{pk-1cca-rand+ro}

, plus some end-of-time logic relating to a bad event.

Lpk-1cca-real+ro\lib{pk-1cca-real+ro}Lpk-1cca-real+ro​
Lpk-1cca-rand+ro\lib{pk-1cca-rand+ro}Lpk-1cca-rand+ro​
(PK,SK):=(\pk,\sk) := {}(PK,SK):=
          Σ.KeyGen()\Sigma.\KeyGen()Σ.KeyGen()
        

          Σ.KeyGen\Sigma.\KeyGenΣ.KeyGen
        

          Σ.KeyGen()\Sigma.\KeyGen()Σ.KeyGen()
        
1cca.pk\ccaonepk1cca.pk( ):
return PK\pkPK
1cca.enc\ccaoneenc1cca.enc(M\ptxtM):
if C∗\ctxt^*C∗ undefined:
// C∗:=Enc(PK,M)\ctxt^* := \Enc(\pk,\ptxt)C∗:=Enc(PK,M)
S∗↞{0,1}λS^* \gets \bits^\secparS∗↞{0,1}λ
if H[M∥S∗]\rotable[\ptxt\|S^*]H[M∥S∗] undefined: 
H[M∥S∗]↞{0,1}λ\rotable[\ptxt\|S^*] \gets \bits^\secparH[M∥S∗]↞{0,1}λ
RR R:={}:= {}:=
              H(M∥S∗)\ro(\ptxt \| S^*)H(M∥S∗)
            

              H[M∥S∗]\rotable[\ptxt \| S^*]H[M∥S∗]
            

          ↞{0,1}λ{}\gets \bits^\secpar↞{0,1}λ
        
C∗\ctxt^* C∗
          :=Σ.Enc(PK,M∥S∗;R){}:= \Sigma.\Enc(\pk, \ptxt \| S^*; R) :=Σ.Enc(PK,M∥S∗;R)
        

          ↞Σ.C(∣M∣+λ){}\gets \Sigma.\C\bigr( |\ptxt| + \secpar \bigr)↞Σ.C(∣M∣+λ)
        
D[C∗]:=M\mathcal{D}[\ctxt^*] := \ptxtD[C∗]:=M
B∗:=M∥S∗B^* := \ptxt \| S^*B∗:=M∥S∗
M∗:=M\ptxt^* := \ptxtM∗:=M
return C∗\ctxt^*C∗
1cca.dec\ccaonedec1cca.dec(C\ctxtC):
if C==C∗\ctxt == \ctxt^*C==C∗: return M∗\ptxt^*M∗

      // return 
          Dec(SK,C)\Dec(\sk,\ctxt)Dec(SK,C)
        

          Dec(C)\Dec(\ctxt)Dec(C):
        
if D[C]\mathcal{D}[\ctxt]D[C] defined: return D[C]\mathcal{D}[\ctxt]D[C]

      M∥S:=Σ.Dec(SK,C)\ptxt \| S := \Sigma.\Dec(\sk,\ctxt)M∥S:=Σ.Dec(SK,C)
    

      R:=H(M∥S)R := \ro(\ptxt \| S)R:=H(M∥S)
    

      if 
          H[M∥S]\rotable[\ptxt\|S]H[M∥S] undefined: 
        

          H[M∥S]\rotable[\ptxt \| S]H[M∥S] undefined: return err\myerrerr
        
H[M∥S]↞{0,1}λ\rotable[\ptxt\|S] \gets \bits^\secparH[M∥S]↞{0,1}λ

      if C≠Σ.Enc(PK,M∥S;\ctxt \ne \Sigma.\Enc(\pk,\ptxt\|S; C=Σ.Enc(PK,M∥S;
          R)R)R):
        

          H[M∥S])\rotable[\ptxt\|S])H[M∥S]):
        

          R)R)R):
        
return err\myerrerr

      return M\ptxtM
    
H\roH(AAA):
if H[A]\rotable[A]H[A] undefined: 
A:=A∪{A}\mathcal{A} := \mathcal{A} \cup \{ A \}A:=A∪{A}
H[A]↞{0,1}λ\rotable[A] \gets \bits^\secparH[A]↞{0,1}λ
C:=Σ.Enc(PK,A;H[A])C := \Sigma.\Enc(\pk,A; \rotable[A])C:=Σ.Enc(PK,A;H[A])
write M∥S:=A\ptxt \| S := AM∥S:=A
D[C]:=M\mathcal{D}[C] := \ptxtD[C]:=M
return H[A]\rotable[A]H[A]
end of time:
S∗↞{0,1}λS^* \gets \bits^\secparS∗↞{0,1}λ
B∗:=B^* := {}B∗:=
          D[C∗]∥S∗\mathcal{D}[\ctxt^*] \| S^*D[C∗]∥S∗
        

          M∗∥S∗\ptxt^* \| S^*M∗∥S∗
        
if B∗∈AB^* \in \mathcal{A}B∗∈A: bad:=true\badvar := \mytruebad:=true

We complete the proof by arguing that the bad event has negligible probability. If the adversary makes $q$ queries to the random oracle, then at the end of time $\mathcal{A}$ contains at most $q$ values, and the bad event happens with probability at most $q/2^\secpar$ , which is negligible.

Real-world Impact: Because the Fujisaki-Okamoto construction adds CCA security to a PKE with almost no overhead, it is used in many standard (and candidate standard) PKE algorithms. The US National Institute of Standards & Technology recently held a competition to standardize the next generation of public-key encryption schemes, holding the first round of submissions in 2017. Out of the forty-six PKE schemes proposed, twenty-five used the Fujisaki-Okamoto technique to achieve CCA security. All four schemes that advanced to the final round of the selection process use Fujisaki-Okamoto or similar variant.

14.5. Hybrid encryption

Public-key cryptography is much, much slower than symmetric-key cryptography. As a simple demonstration, one invocation of the AES block cipher requires only a few CPU cycles, but encrypting in a PKE scheme can take millions. In this section we explore a clever way to get the best of both worlds: the features of PKE, with cost as close as possible to SKE.

Suppose Alice has published her public key $\pk$ , and Bob wants to send her a large file. Using PKE directly on a large file would be incredibly expensive. Instead, Bob can do the following:

Sample a fresh key $\key$ for a symmetric-key encryption scheme.
Encrypt $\key$ under $\pk$ , using PKE, and send it to Alice. Although PKE encryption is slow, we are encrypting only a small value $\key$ .
Encrypt the large file under $\key$ , using SKE, and send it to Alice. SKE encryption is fast for this large file.

When Alice receives this data, she can decrypt the PKE ciphertext to learn $\key$ , then decrypt the SKE ciphertext with $\key$ to obtain the large file. The overall functionality is the same as PKE: Bob can encrypt data to Alice, knowing only her public key.

This method of public-key encryption is called hybrid encryption, where “hybrid” in this context means that the scheme consists of a combination of PKE and SKE.

Construction 14.5.1 (Hybrid encryption)

Let $\Sigma_{\text{pke}}$ be a PKE scheme and $\Sigma_{\text{ske}}$ be a SKE scheme, such that $\Sigma_{\text{ske}}.\K \subseteq \Sigma_{\text{pke}}.\M$ (i.e., it is possible for $\Sigma_{\text{pke}}$ to encrypt keys from $\Sigma_{\text{ske}}$ ). Then hybrid encryption is defined by the following algorithms:

\begin{aligned} \K &= \Sigma_{\text{pke}}.\K \\ \M &= \Sigma_{\text{ske}}.\M \\ \C &= \Sigma_{\text{pke}}.\C \times \Sigma_{\text{ske}}.\C \\ \KeyGen &= \Sigma_{\text{pke}}.\KeyGen \end{aligned}

\Enc(\pk,\ptxt)

\key \gets \Sigma_{\text{ske}}.\K

\ctxt_{\text{pke}} := \Sigma_{\text{pke}}.\Enc(\pk,\key)

\ctxt_{\text{ske}} := \Sigma_{\text{ske}}.\Enc(\key,\ptxt)

return

(\ctxt_{\text{pke}}, \ctxt_{\text{ske}})

\Dec(\sk,(\ctxt_{\text{pke}},\ctxt_{\text{ske}}))

\key := \Sigma_{\text{pke}}.\Dec(\sk,\ctxt_{\text{pke}})

\key == \myerr

: return

\myerr

return

\Sigma_{\text{ske}}.\Dec(\key,\ctxt_{\text{ske}})

The value $\key$ chosen in $\Enc$ is called the ephemeral key.

Each ephemeral key is used to encrypt just a single plaintext, and therefore the symmetric-key scheme $\Sigma_{\text{ske}}$ only needs to have one-time secrecy for the overall hybrid scheme to have CPA security.

Claim 14.5.2 (Security of hybrid encryption)

If $\Sigma_{\text{pke}}$ is a CPA-secure PKE and $\Sigma_{\text{ske}}$ is a one-time secret SKE, then hybrid encryption (construction 14.5.1) is CPA-secure.

Proof:

The proof is an easy consequence of the definitions.

Hybrid Sequence:

Starting with

\lib{pk-cpa-real}

we can immediately apply the CPA-security of

\Sigma_{\text{pke}}

. The simple three-hop maneuver is not shown.

With the ephemeral key

\key

no longer used except to encrypt

\ptxt

, we can apply the one-time secrecy property. Again, the three-hop maneuver is not shown, and the result is

\lib{pk-cpa-rand}

, completing the proof.

\lib{pk-cpa-real}

(\pk,\sk) \gets \Sigma_{\text{pke}}.\KeyGen

\cpapk

( ):

return

\pk

\cpaenc

(

\ptxt

\Sigma_{hyb}.\Enc

\key \gets \Sigma_{\text{ske}}.\K

\ctxt_{\text{pke}}

{}:= \Sigma_{\text{pke}}.\Enc(\pk,\key)

{}\gets \Sigma_{\text{pke}}.\C

\ctxt_{\text{ske}}

{}:= \Sigma_{\text{ske}}.\Enc(\key,\ptxt)

{}\gets \Sigma_{\text{ske}}.\C( |\ptxt| )

return

(\ctxt_{\text{pke}}, \ctxt_{\text{ske}})

CCA Security: The situation of CCA security for hybrid encryption is more subtle. Our usual way of using the real-or-random paradigm to define security doesn't quite work, in the sense that even if both the underlying PKE and SKE are (real-or-random) CCA-secure, the resulting hybrid scheme may not be.

Claim 14.5.3

There exists a (real-or-random) CCA-secure PKE $\Sigma_{\text{pke}}$ and (real-or-random) CCA-secure SKE $\Sigma_{\text{ske}}$ , such that the resulting hybrid encryption (construction 14.5.1) is not (real-or-random) CCA-secure.

However, if we consider the left-or-right paradigm for CCA security, then the property we hope to be true about hybrid encryption is true. Hybrid encryption achieves (left-or-right) CCA security if both its underlying PKE and SKE do.

Claim 14.5.4

If $\Sigma_{\text{pke}}$ is a left-or-right CCA-secure PKE and $\Sigma_{\text{ske}}$ is a left-or-right CCA-secure symmetric encryption scheme, then hybrid encryption (construction 14.5.1) is left-or-right CCA-secure.

Proofs of these two claims are left as exercises.

Hybrid encryption is the only example I know of a completely natural encryption scheme for which the distinction between left-or-right and real-or-random security is significant. In every other case, the encryption schemes we care about in practice satisfy both flavors of security.

14.6. Key encapsulation

Because of hybrid encryption, there is rarely any need to use “true” PKE for anything other than encrypting uniformly sampled values. A key encapsulation mechanism (KEM) is a specialized PKE that is capable of only that; it can encrypt only pseudorandom plaintexts. In a PKE we tell the encryption algorithm our choice of plaintext, but in a KEM we let the encryption algorithm itself choose the plaintext. Although this might seem like a strange modification to make to a PKE, the benefit is that a KEM ciphertext can be shorter than a traditional PKE ciphertext.

To differentiate KEMs from traditional PKE, we usually refer to the algorithms of a KEM as encapsulation/decapsulation rather than encryption/decryption.

Definition 14.6.1 (Key encapsulation mechanism)

A key encapsulation mechanism (KEM) consists of the following algorithms:

$\KeyGen$ : same as in a PKE scheme, a randomized algorithm that takes no inputs and outputs a keypair $(\pk,\sk)$ .
$\Encaps$ : a randomized algorithm that takes only a public key $\pk$ as input and returns both a ciphertext $\ctxt\in \C$ and plaintext $\ptxt\in\M$ .
$\Decaps$ : same as in a PKE scheme, a deterministic algorithm that takes a private key $\sk$ and ciphertext $\ctxt\in\C$ as input, and returns a plaintext $\ptxt\in \M$ (or raises an error).

A KEM is correct if the following process outputs $\mytrue$ with probability 1:

(PK,SK):=KeyGen()(\pk,\sk) := \KeyGen()(PK,SK):=KeyGen()
(C,M):=Encaps(PK)(\ctxt, \ptxt) := \Encaps(\pk)(C,M):=Encaps(PK)
M′:=Decaps(SK,C)\ptxt' := \Decaps(\sk,\ctxt)M′:=Decaps(SK,C)
return M==M′\ptxt == \ptxt'M==M′

The definitions of CPA and CCA security for KEMs are similar to those for traditional PKE. The adversary's $\cpaenc$ interface now takes no arguments, since a KEM's $\Encaps$ algorithm does not take a plaintext argument. In addition to requiring that the ciphertext is pseudorandom, the definitions also require that the plaintext is pseudorandom (and independent of the ciphertext).

Definition 14.6.2 (CPA security for key encapsulation)

A KEM $\Sigma$ has security against chosen-plaintext attacks (CPA security) if the following two libraries are indistinguishable:

\lib{kem-cpa-real}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\cpapk(\,)

return

\pk

\cpaenc(\,)

return

\Sigma.\Encaps(\pk)

\indist

\lib{kem-cpa-rand}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\cpapk(\,)

return

\pk

\cpaenc(\,)

\ctxt \gets \Sigma.\C

\ptxt \gets \Sigma.\M

return

(\ctxt, \ptxt)

Definition 14.6.3 (CCA security for key encapsulation)

A KEM $\Sigma$ has security against chosen-ciphertext attacks (CCA security) if the following two libraries are indistinguishable:

\lib{kem-cca-real}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\ccapk(\,)

return

\pk

\ccaenc(\,)

return

\Sigma.\Encaps(\pk)

\ccadec(\ctxt)

return

\Sigma.\Decaps(\sk,\ctxt)

\indist

\lib{kem-cca-rand}^\Sigma

(\pk,\sk) :=\Sigma.\KeyGen()

\ccapk(\,)

return

\pk

\ccaenc(\,)

\ptxt \gets \Sigma.\M

\ctxt \gets \Sigma.\C

\mathcal{D}[\ctxt] := \ptxt

return

(\ctxt, \ptxt)

\ccadec(\ctxt)

\mathcal{D}[\ctxt]

defined: return

\mathcal{D}[\ctxt]

return

\Sigma.\Decaps(\sk,\ctxt)

Hybrid encryption is sometimes called the KEM-DEM paradigm, where DEM (the symmetric-key encryption scheme) stands for data encapsulation mechanism.

14.6.1. One-time vs. many-time

Just like PKE, if a KEM is secure for a single encryption, then it is secure against many encryptions. Hence we have the following results, analogous to the ones in section 14.2. Because KEM encapsulation takes no plaintext argument, these libraries are slightly simpler than their PKE counterparts; the ciphertext and plaintext can be generated at the beginning of time.

Claim 14.6.4 (One-time security for key encapsulation)

Let $\Sigma$ be a KEM scheme. If the following two libraries are indistinguishable, then $\Sigma$ has CPA security:

\lib{kem-1cpa-real}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

(\ctxt^*,\ptxt^*) := \Sigma.\Encaps(\pk)

\cpaonepk(\,)

return

\pk

\cpaoneenc(\,)

return

(\ctxt^*,\ptxt^*)

\indist

\lib{kem-1cpa-rand}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

\ctxt^* \gets \Sigma.\C

\ptxt^* \gets \Sigma.\M

\cpaonepk(\,)

return

\pk

\cpaoneenc(\,)

return

(\ctxt^*, \ptxt^*)

If the following two libraries are indistinguishable, then $\Sigma$ has CCA security:

\lib{kem-1cca-real}^\Sigma

(\pk,\sk) := \Sigma.\KeyGen()

(\ctxt^*,\ptxt^*) := \Sigma.\Encaps(\pk)

\ccaonepk(\,)

return

\pk

\ccaoneenc(\,)

return

(\ctxt^*, \ptxt^*)

\ccaonedec(\ctxt)

return

\Sigma.\Decaps(\sk,\ctxt)

\indist

\lib{kem-1cca-rand}^\Sigma

(\pk,\sk) :=\Sigma.\KeyGen()

\ctxt^* \gets \Sigma.\C

\ptxt^* \gets \Sigma.\M

\ccaonepk(\,)

return

\pk

\ccaoneenc(\,)

return

(\ctxt^*, \ptxt^*)

\ccadec(\ctxt)

\ctxt == \ctxt^*

: return

\ptxt^*

return

\Sigma.\Decaps(\sk,\ctxt)

The proofs follow the same structure as those in section 14.2, and are left as exercises.

14.6.2. El Gamal KEM

One reason for studying KEMs is that their ciphertexts can be smaller than those of a PKE; El Gamal encryption provides a great example. Recall that El Gamal ciphertexts consist of a pair of group elements that have the form $(g^r, \pk^r \cdot \ptxt)$ . The security proof argues that $\pk^r$ hides the plaintext, because $\pk^r$ is pseudorandom given $\pk$ and $g^r$ . But if $\pk^r$ is pseudorandom, why not just consider $\pk^r$ to be the plaintext and let $g^r$ alone be the ciphertext? The result is El Gamal KEM, and its ciphertexts consist of just a single group element.

Construction 14.6.5 (El Gamal KEM)

Let $\G$ be a cyclic group of order $\nmod$ with generator $g$ . Then El Gamal KEM is defined by the following:

\KeyGen(\,)

\sk \gets \Z_\nmod

\pk := g^{\sk}

return

(\pk,\sk)

\Encaps(\pk)

r \gets \Z_\nmod

\ctxt := g^r

\ptxt := \pk^r

return

(\ctxt, \ptxt)

\Decaps(\sk,\ctxt)

return

\ctxt^{\sk}

Claim 14.6.6 (Security of El Gamal KEM)

El Gamal KEM (construction 14.6.5) is CPA-secure if the DDH assumption holds.

The proof is extremely similar to that of claim 14.3.2, and is left as an exercise.

Exercises

Prove that if a PKE scheme has a deterministic $\Enc$ algorithm, then it cannot have CPA security.
Let $\Sigma$ be a PKE scheme with $\M = \bits^n$ , and let $\Sigma^2$ be defined as follows:

$\begin{aligned} \M &= \bits^{2n} \\ \C &= (\Sigma.\C)^2 \\ \KeyGen &= \Sigma.\KeyGen \end{aligned}$

$\Enc(\pk,\ptxt_1 \| \ptxt_2)$ :

// each $\ptxt_i$ is $n$ bits

$\ctxt_1 := \Enc(\pk,\ptxt_1)$

$\ctxt_2 := \Enc(\pk,\ptxt_2)$

return $(\ctxt_1, \ctxt_2)$

$\Dec\bigl( \sk, (\ctxt_1,\ctxt_2) \bigr)$ :

$\ptxt_1 := \Dec(\sk,\ctxt_1)$

$\ptxt_2 := \Dec(\sk,\ctxt_2)$

return $\ptxt_1\|\ptxt_2$
1. Prove that $\Sigma^2$ is CPA-secure if $\Sigma$ is.
2. Prove that $\Sigma^2$ is not CCA-secure (even if $\Sigma$ is).
h Let $\Sigma$ be a CPA-secure symmetric-key encryption scheme, and suppose it has an additional randomized algorithm $\textsf{ReRandomize}$ such that the following libraries are indistinguishable:

$\lib{rerand-real}^\Sigma$

$\subname{rerand}(\key,\ctxt)$ :

return $\Sigma.\textsf{ReRandomize}(\ctxt)$

$\indist$

$\lib{rerand-fake}^\Sigma$

$\subname{rerand}(\key,\ctxt)$ :

$\ptxt := \Sigma.\Dec(\key,\ctxt)$

return $\Sigma.\Enc(\key,\ptxt)$

The idea behind $\textsf{ReRandomize}$ is that when its input is an encryption of $\ptxt$ , then its output is also an encryption of $\ptxt$ . Not only do the input and output ciphertexts encrypt the same thing, the output ciphertext is distributed just like a fresh re-encryption of $\ptxt$ . And $\textsf{ReRandomize}$ is able to do this all without knowing $\ptxt$ or the key $\key$ .

Describe how to use this $\Sigma$ to construct a PKE, and prove that your construction is CPA-secure.

From exercise 14.2 it is enough to construct a PKE whose plaintext space is $\M = \{\bit0,\bit1\}$ . The public key in your PKE scheme should include $\ctxt_0 = \Enc(\sk,\bit0)$ and $\ctxt_1 = \Enc(\sk,\bit1)$ .
Prove claim 14.2.2 (one-time CCA security implies many-time CCA security).
Below are parameters for El Gamal encryption (prime $p$ , generator $g$ , and a user's private key) and an El Gamal ciphertext $(C_1, C_2)$ .

$\begin{aligned} p &= \longnum{820352377101055884914460791538599368437918206431245996677118212255669324388510923534966153248485697321865777338727602021579688760726401763871773605863599043632214034707416231834019537149866575202482386776278066585668125927276425009779822325780293591260030911095663277044721309804734814551532256818493} \\ g &= 2 \\ \sk &= \longnum{306033152423344432110873337270518746079412713693849345056658514895080413997457075906501550362842203171386314578226690305048842904885022025641077841375072635002329298772202663102727543201221833570076490977067539007385463977153703095726422723750680937329958625495800630322994618237566748102114046656069} \\ C_1 &= \longnum{462054157245413467558826072791385044036879483117702714989843900229935194869085734295713385708063663647004475374447278157812605079099785722745766123633236262309194634963603597800630964317028376563068090101355339547855197628919380823904604547121058779885144513823662739084822466772834215530613199671852} \\ C_2 &= \longnum{363997211863183238889564744554761007626218766957232278199695792262726404818908096009225062142352538150744210033702637001010465153129696735055444199306708284949138506063666875862705763978705223762919549775254323612712554068732510778676226769703774955995845877873850997054909183025915660486248217201296}\end{aligned}$
1. What is the corresponding public key, and how did you compute it?
2. What is the result of decrypting the ciphertext, and how did you compute it?
Show that El Gamal is not a CCA-secure PKE.
h Suppose you are given a passively secure key exchange protocol (definition 13.3.3) $\Sigma$ , in which each user sends only one protocol message. Formally describe how to use $\Sigma$ to build a CPA-secure PKE scheme, and prove its security. Assume that the KE protocol generates a key from $\K = \bits^\secpar$ .

Take inspiration from the relationship between DHKE and El Gamal.
h Suppose you are given a CPA-secure PKE scheme $\Sigma$ . Formally describe how to use $\Sigma$ to build a passively secure key exchange protocol (definition 13.3.3), and prove its security.

The security definition for KE says that the key should be pseudorandom, but it does not require both parties to “contribute” to the key.
Given a plaintext consisting of two group elements, it is possible to encrypt each element with El Gamal, independently (exercise 14.2). This would result in a ciphertext consisting of four group elements. Consider the following variant of El Gamal, which can encrypt two plaintext group elements to a ciphertext of three group elements:

$\begin{aligned} \M &= \G^2 \\ \C &= \G^3 \end{aligned}$

$\KeyGen(\,)$ :

$\sk_1 \gets \Z_\nmod$

$\sk_2 \gets \Z_\nmod$

$\sk := (\sk_1,\sk_2)$

$\pk := (g^{\sk_1}, g^{\sk_2})$

return $(\pk,\sk)$

$\Enc\bigl(\pk, (\ptxt_1, \ptxt_2)\bigr)$ :

$(\pk_1, \pk_2) := \pk$

$r \gets \Z_\nmod$

$\ctxt_0 := g^r$

$\ctxt_1 := \ptxt_1 \cdot (\pk_1)^r$

$\ctxt_2 := \ptxt_2 \cdot (\pk_2)^r$

return $(\ctxt_0, \ctxt_1, \ctxt_2)$

$\Dec\bigl(\sk,(\ctxt_0,\ctxt_1,\ctxt_2)\bigr)$ :

$\ptxt_1 := \ctxt_1 \cdot (\ctxt_0)^{-\sk_1}$

$\ptxt_2 := \ctxt_2 \cdot (\ctxt_0)^{-\sk_2}$

return $(\ptxt_1, \ptxt_2)$

Prove that this scheme is CPA-secure if the DDH assumption is true in $\G$ .
The scheme in the previous exercise has a longer public key than standard El Gamal. Suppose we compress the public key by letting $\sk_2 = 2 \cdot \sk_1$ , and thus $\pk_2 := (\pk_1)^2$ :

$\begin{aligned} \M &= \G^2 \\ \C &= \G^3 \end{aligned}$

$\KeyGen(\,)$ :

$\sk \gets \Z_\nmod$

$\pk := g^{\sk}$

return $(\pk,\sk)$

$\Enc\bigl(\pk, (\ptxt_1, \ptxt_2)\bigr)$ :

$r \gets \Z_\nmod$

$\ctxt_0 := g^r$

$\ctxt_1 := \ptxt_1 \cdot \hl{\pk}^r$

$\ctxt_2 := \ptxt_2 \cdot \hl{(\pk^2)}^r$

return $(\ctxt_0, \ctxt_1, \ctxt_2)$

$\Dec\bigl(\sk,(\ctxt_0,\ctxt_1,\ctxt_2)\bigr)$ :

$\ptxt_1 := \ctxt_1 \cdot (\ctxt_0)^{-\hl{\sk}}$

$\ptxt_2 := \ctxt_2 \cdot (\ctxt_0)^{-\hl{2 \cdot \sk}}$

return $(\ptxt_1, \ptxt_2)$

Show that this scheme is not CPA-secure.
Suppose you are given an El Gamal ciphertext $(\ctxt_1, \ctxt_2)$ encrypting $\ptxt$ . Show how to construct a different ciphertext encrypting the same $\ptxt$ , even if you don't know $\ptxt$ or the private key. You can assume that the public key is known.
Suppose you are given two El Gamal ciphertexts: $(\ctxt_1, \ctxt_2)$ encrypting $\ptxt$ , and $(\ctxt'_1, \ctxt'_2)$ encrypting $\ptxt'$ . Show how to construct a ciphertext encrypting $\ptxt \cdot \ptxt'$ , even if you don't know $\ptxt$ or $\ptxt'$ , or the private key. You can assume that the public key is known.
h Describe a randomized algorithm $\textsf{ReRandomize}$ with the following properties. It should take as input an El Gamal public key $\pk$ and ciphertext $\ctxt$ , and output a new ciphertext $\ctxt'$ . The output $\ctxt'$ should be distributed identically to the output of $\Enc(\pk,\Dec(\sk,\ctxt))$ . In other words, the output should be a ciphertext encrypting the same plaintext as $\ctxt$ , and distributed precisely as a fresh encryption. The $\textsf{ReRandomize}$ algorithm should do all of this without knowing $\ptxt$ or the El Gamal private key $\sk$ .

Use exercise 14.12 with $\ctxt$ and a fresh encryption of 1.
Our security proof for Fujisaki-Okamoto (theorem 14.4.5) assumes that the encryption algorithm has unique randomness. However, this assumption is not strictly necessary.
1. Prove that if $\Sigma$ is a CPA-secure PKE, then the following two libraries are indistinguishable:
  
  $(\pk,\sk) := \Sigma.\KeyGen()$
  
  $\subname{getpk}(\,)$ :
  
  return $\pk$
  
  $\subname{test}(\ptxt,\ctxt)$ :
  
  $\ctxt' := \Sigma.\Enc(\pk,\ptxt)$
  
  return $\ctxt' == \ctxt$
  
  $\indist$
  
  $(\pk,\sk) := \Sigma.\KeyGen()$
  
  $\subname{getpk}(\,)$ :
  
  return $\pk$
  
  $\subname{test}(\ptxt,\ctxt)$ :
  
  return $\myfalse$
2. Prove the security of Fujisaki-Okamoto without assuming the unique randomness property.
Below is an attempt to use the Fujisaki-Okamoto technique to construct a KEM, rather than a PKE:

$\Encaps^*(\pk)$ :

$S \gets \bits^\secpar$

$\ctxt := \Sigma.\Enc(\pk, S; \ro(S))$

return $(\ctxt, S)$

$\Decaps^*(\sk,\ctxt)$ :

$S := \Sigma.\Dec(\sk,\ctxt)$

if $\ctxt \ne \Sigma.\Enc(\pk,S;\ro(S))$ :

return $\myerr$

return $S$

Show that this construction is not a CCA-secure KEM (it's not even CPA-secure!).
Below is another attempt to use the Fujisaki-Okamoto technique to construct a KEM, rather than a PKE. It requires a random oracle $\ro$ whose outputs have length $2\secpar$ .

$\Encaps^*(\pk)$ :

$S \gets \bits^\secpar$

$\ptxt \| R := \ro(S)$

$\ctxt := \Sigma.\Enc(\pk, S; R)$

return $(\ctxt, \ptxt)$

$\Decaps^*(\sk,\ctxt)$ :

$S := \Sigma.\Dec(\sk,\ctxt)$

$\ptxt \| R := \ro(S)$

if $\ctxt \ne \Sigma.\Enc(\pk,S;R)$ :

return $\myerr$

return $\ptxt$

This KEM is more efficient that construction 14.4.3 because it uses $\Sigma.\Enc$ to encrypt a plaintext of length $\secpar$ instead of $2\secpar$ .
1. Prove that this construction is a CCA-secure KEM in the random oracle model, if $\Sigma$ is CPA-secure.
2. Even though the end result of this construction is a KEM, it requires the underlying scheme $\Sigma$ to be a PKE, not a KEM. What is the difficulty of applying the Fujisaki-Okamoto technique to an underlying KEM?
$\star$ Construct a PKE and SKE which both have (real-or-random) CCA security, but whose combination as a hybrid encryption scheme does not have (real-or-random) CCA security (claim 14.5.3).
1. Given a (real-or-random) CCA-secure PKE, construct a new one that is also CCA-secure, and that has the property that a uniformly chosen ciphertext will raise a decryption error with high probability. Prove that your new PKE is CCA-secure.
2. Given a (real-or-random) CCA-secure SKE, construct a new one that is also CCA-secure, but in which the $\Dec$ algorithm never raises an error. Prove that your new SKE is CCA-secure.
3. Show that the combination of these two new schemes as a hybrid encryption scheme does not have (real-or-random) CCA security.
h $\star$ The previous exercise considered hybrid encryption where the underlying SKE never has decryption error. Suppose we instead insist that the SKE is AE-secure. Can you still construct a (real-or-random) CCA-secure PKE and (real-or-random) AE-secure SKE whose composition as a hybrid scheme is not (real-or-random) CCA-secure?

A PKE scheme can be CCA-secure and also have the property that a uniformly chosen ciphertext decrypts to a known, fixed value, like $\bit0^\secpar$ , with high probability.
Prove that hybrid encryption is (left-or-right) CCA-secure, if its underlying PKE and SKE both are (claim 14.5.4).
Formally prove claim 14.6.4 (one-time security implies many-time security, for a KEM).
Prove claim 14.6.6 (security of El Gamal KEM).
Formally describe a variant of hybrid encryption (construction 14.5.1) that uses a KEM rather than PKE to encrypt the ephemeral symmetric key. Formally prove its CPA security, using the CPA security of the underlying KEM.
Any PKE scheme can be converted into a KEM, by simply using the PKE scheme to encrypt a uniformly chosen plaintext. Formally describe this KEM construction, and prove that it is CPA-secure if the underlying PKE scheme is CPA-secure.
Consider a variant of El Gamal KEM in which the plaintext is not $\pk^r$ but $\ro(\pk^r)$ . Prove that this variant is a secure KEM in the random oracle model, assuming the CDH assumption (defined in exercise 13.8).
Let $\ro$ be a random oracle, let $\G$ be a cyclic group of order $\nmod$ , and let $g_1$ and $g_2$ be two different generators. The Kurosawa-Desmedt KEM is defined as follows:

$\KeyGen(\,)$ :

$a_1 \gets \Z_\nmod$

$a_2 \gets \Z_\nmod$

$b_1 \gets \Z_\nmod$

$b_2 \gets \Z_\nmod$

$A := g_1^{a_1} g_2^{a_2}$

$B := g_1^{b_1} g_2^{b_2}$

$\sk := (a_1,a_2,b_1,b_2)$

$\pk := (A,B)$

return $(\pk,\sk)$

$\Encaps(\pk)$ :

$(A,B) := \pk$

$r \gets \Z_\nmod$

$C_1 := g_1^r$

$C_2 := g_2^r$

$h := \ro(C_1, C_2)$

$\key := (A^h B)^r$

return $\bigl( (C_1,C_2), \key \bigr)$

$\Decaps(\sk, (C_1,C_2))$ :

$(a_1,a_2,b_1,b_2) := \sk$

$h := \ro(C_1, C_2)$

$\key := C_1^{h \cdot a_1 + b_1} C_2^{h \cdot a_2 + b_2}$
1. Show that the KEM satisfies correctness.
2. h $\star$ Show that the KEM is not CCA-secure. You can assume that the order $\nmod$ of the cyclic group is prime.
Let $\ctxt = (C_1, C_2)$ be an arbitrary ciphertext. Suppose an adversary chooses exponents $x$ and $y$ , and defines the new ciphertexts $\ctxt_x := (C_1^x, C_2^x)$ and $\ctxt_y := (C_1^y, C_2^y)$ . Show how the decapsulations of $\ctxt_x$ and $\ctxt_y$ can be used to predict the decapsulation of $\ctxt$ .
Prove that $\Sigma$ is a CPA-secure KEM if and only if the following is a passively secure KE protocol:

$\subname{alice}(\,)$ :

$(\pk,\sk) := \Sigma.\KeyGen$

send $\pk$

recv $\ctxt$

return $\Sigma.\Decaps(\sk,\ctxt)$

$\rightleftharpoons$

$\subname{bob}(\,)$ :

recv $\pk$

$(\ctxt, \ptxt) := \Sigma.\Encaps(\pk)$

send $\ctxt$

return $\ptxt$

Chapter Notes

Public-key encryption was first conceived in 1970 by James Ellis, who was employed at British GCHQ at the time [97]. As such, his involvement in the history of public-key cryptography remained classified until 1997. He called his idea “non-secret encryption,” but was not able to propose a plausibly secure mechanism. Three years later another GCHQ employee, Clifford Cocks, proposed a non-secret encryption scheme which is identical to the well-known RSA scheme (chapter 15).

In 1974, Ralph Merkle proposed an asymmetric key exchange protocol, in a proposal for an undergraduate class project [159]. His contributions to the history of public-key cryptography were not recognized until around a decade later. Diffie and Hellman were the first to receive public recognition for the invention of public-key cryptography, in 1976 [83]. Bellare, Desai, Pointcheval, and Rogaway [16] study a variety of security definitions for public-key encryption, showing separations, equivalences, and implications among them.

El Gamal encryption is named after its creator, Taher El Gamal [96]. A security proof for El Gamal, based on the DDH assumption, was first given by Tsiounis and Yung [211].

Unsurprisingly, the Fujisaki-Okamoto construction is named for its creators, Fujisaki and Okamoto [104]. See Hofheinz, Hövelmanns, and Kiltz [122] for a comprehensive analysis of the scheme and its many variants.

Hybrid encryption is a natural way to combine public-key and symmetric-key encryption schemes. Its security was first formalized by Cramer and Shoup [76].

The KEM in exercise 14.25 was proposed by Kurosawa and Desmedt [144]. The attack against its CCA security was first shown by Choi, Herranz, Hofheinz, Hwang, Kiltz, Lee, and Yung [65].

Key encapsulation schemes were first defined by Shoup [203].

Public-Key Encryption

Chapter Contents

14.1. Security definitions for PKE

14.2. One-time vs. many-time encryption

14.3. El Gamal encryption

14.4. The Fujisaki-Okamoto construction

14.5. Hybrid encryption

14.6. Key encapsulation

14.6.1. One-time vs. many-time

14.6.2. El Gamal KEM

Exercises

Chapter Notes