Corresponds to Katz & Lindell, Introduction to Modern Cryptography, Chapters 10–11. (The random-oracle model and OAEP are Chapter 13; see the pending section at the end.)

Motivation: secrecy without a shared secret

IntuitionThe asymmetric setting

The receiver generates $(pk, sk)$ and makes $pk$ available. Any sender can encrypt to it, and only $sk$ decrypts. The receiver can either send $pk$ when a sender appears (over a public but authenticated channel) or publish it in advance: on a webpage, a business card, or a directory, before even knowing who will write. Either way the adversary knows $pk$ , so all security rests on $sk$ .

	Private-key	Public-key
Secrecy needed	the whole key	only $sk$
Key distribution	needs a secret channel	an authenticated public channel suffices
Direction	symmetric (either party encrypts)	one-way: many senders to one receiver
Receiver’s storage with $U$ senders	$U$ keys	one $sk$ ; senders needn’t be known in advance
Speed	fast	2–3 orders of magnitude slower (hard on smartcards and RFID tags)

Rule: if a secret key can be shared, use private-key encryption. Even in the public-key setting, long messages are encrypted with private-key cryptography (hybrid encryption).

WarningActive attacks on key distribution are out of scope here

If an adversary can substitute $pk'$ for Alice’s $pk$ (in transit, or in a directory), it decrypts everything sent to “Alice”, and without prior shared information or a trusted third party nobody can detect it. (In the shouting-across-a-room scenario, voices and faces serve as that prior shared information.) These chapters assume senders hold the legitimate $pk$ . That separates encryption from key distribution, which is solved by certificates and PKI (digital-signatures-and-pki, §12.7). Same root cause as DH’s man-in-the-middle.

Definitions

DefinitionPublic-key encryption scheme (Def. 10.1)

Ppt algorithms:

$(pk,sk)\leftarrow\mathrm{Gen}(1^n)$ , each of length at least $n$ , with $n$ recoverable from them;
$c\leftarrow\mathrm{Enc}_{pk}(m)$ , for $m$ in a plaintext space that may depend on $pk$ ;
$m := \mathrm{Dec}_{sk}(c)$ , deterministic, possibly outputting $\perp$ .

Correctness: $\mathrm{Dec}_{sk}(\mathrm{Enc}_{pk}(m)) = m$ . Unlike private-key keys, $pk$ isn’t just a random string. When the plaintext space is something like $\mathbb Z_N$ , specify an efficient, reversible encoding of bit strings (for example, $(n-1)$ -bit strings as integers below $N$ ).

Eavesdropping security is CPA security

Definition $\mathrm{PubK}^{\mathrm{eav}}$ and $\mathrm{PubK}^{\mathrm{cpa}}$ (Defs. 10.3–10.4)

Eavesdropping: $(pk,sk)\leftarrow\mathrm{Gen}$ ; $\mathcal A(pk)$ outputs equal-length $m_0, m_1$ ; it receives $c\leftarrow\mathrm{Enc}_{pk}(m_b)$ and guesses $b$ . Secure if $\Pr[\text{success}]\le\frac12 + \mathrm{negl}$ . The only change from Definition 3.9 is that $\mathcal A$ gets $pk$ .

CPA: additionally give $\mathcal A$ an $\mathrm{Enc}_{pk}(\cdot)$ oracle.

TheoremProposition 10.5 — In the public-key setting, eavesdropping security = CPA security

Knowing $pk$ , $\mathcal A$ can encrypt anything itself: the encryption oracle comes for free. (In the private-key world, EAV security does not imply CPA security: Claim 3.20.)

WarningTwo impossibilities

No perfect secrecy (Exercise 10.1), however long the keys or short the messages. By correctness, the supports of $\mathrm{Enc}_{pk}(0)$ and $\mathrm{Enc}_{pk}(1)$ are disjoint. An unbounded adversary with $pk$ simply checks which support contains $c$ .
No deterministic scheme is secure (Theorem 10.6). Compute $\mathrm{Enc}_{pk}(m_0)$ and compare with $c$ . Worse, a small message space is fully recoverable (Exercise 10.2): a professor encrypting a grade from $\{A,B,C,D,F\}$ leaks it in five trial encryptions. Many early systems used deterministic public-key encryption; Goldwasser–Micali’s insistence on probabilistic encryption (and the definition above) was a turning point.

Multiple encryptions, and arbitrary lengths

TheoremTheorem 10.10 — single-message security ⇒ multi-message security

If $\Pi$ is EAV-secure, then for vectors $\vec M_0, \vec M_1$ of $t = \mathrm{poly}(n)$ messages, $\mathrm{Enc}_{pk}(\vec M_0)$ and $\mathrm{Enc}_{pk}(\vec M_1)$ are indistinguishable. (Assume without loss of generality exactly $t(n)$ messages: Exercise 10.4.)

ProofHybrid over positions

Let $\vec C^{(i)}$ encrypt the first $i$ messages of $\vec M_0$ and the rest of $\vec M_1$ , so $\vec C^{(t)}$ is all $\vec M_0$ and $\vec C^{(0)}$ is all $\vec M_1$ . $\mathcal A'$ picks a random $i\in[t]$ , submits $(m_0^i, m_1^i)$ , places the challenge at position $i$ , and encrypts the other positions itself using $pk$ (possible only because the key is public). If $b = 0$ it simulates $\vec C^{(i)}$ ; if $b = 1$ , $\vec C^{(i-1)}$ . Telescoping gives

$\tfrac12 + \mathrm{negl}\ge\Pr[\mathcal A'\text{ wins}] = \frac{t-1}{2t} + \frac1t\Pr[\mathrm{PubK}^{\mathrm{mult}} = 1]$

so $\Pr[\mathrm{PubK}^{\mathrm{mult}} = 1]\le\frac12 + t\cdot\mathrm{negl}$ . (The multi-sample hybrid again.)

∎

TheoremProposition 10.11 — Bit-by-bit encryption

Any EAV/CPA-secure scheme for 1-bit messages gives one for $\{0,1\}^*$ : $\mathrm{Enc}'_{pk}(m) = \mathrm{Enc}_{pk}(m_1),\ldots,\mathrm{Enc}_{pk}(m_t)$ . Terminology: “CPA-secure” from now on, though proofs use the EAV experiment.

Hybrid encryption

AlgorithmHybrid encryption (Construction 10.12)

With public-key scheme $\Pi$ and private-key scheme $\Pi'$ :

$\mathrm{Enc}^{hy}_{pk}(m)$ : $k\leftarrow\{0,1\}^n$ , $c_1\leftarrow\mathrm{Enc}_{pk}(k)$ , $c_2\leftarrow\mathrm{Enc}'_k(m)$ ; output $\langle c_1,c_2\rangle$ .
$\mathrm{Dec}^{hy}$ : $k := \mathrm{Dec}_{sk}(c_1)$ , then $m := \mathrm{Dec}'_k(c_2)$ .

Public-key encryption transports a fresh key; private-key encryption carries the data. It is still a public-key scheme: nothing is shared in advance. (The modern KEM/DEM pattern.)

FormulaEfficiency

With $\alpha$ the cost to encrypt an $n$ -bit key and $\beta$ the per-bit private-key cost, the per-bit cost for a $t$ -bit message is

$\frac{\alpha + \beta t}t = \frac\alpha t + \beta\ \longrightarrow\ \beta$

and the ciphertext length is $\ell + n + \lvert m\rvert$ . Public-key functionality at private-key speed for long messages, and only useful when $\lvert m\rvert > n$ . Rough numbers for a 1 Mb email with $\beta\approx\alpha/10^6$ : hybrid costs about $\alpha/(5\cdot10^5)$ per bit, versus about $\alpha/10^3$ per bit for 1000-bit public-key blocks. That is a roughly 500× speedup and about half the ciphertext length.

TheoremTheorem 10.13 — Hybrid encryption is CPA-secure

If $\Pi$ is CPA-secure and $\Pi'$ is merely EAV-secure (one message per key), then $\Pi^{hy}$ is CPA-secure. One-time security suffices because every message gets a fresh $k$ .

ProofThree hybrids

Show $(pk,\mathrm{Enc}_{pk}(k),\mathrm{Enc}'_k(m_0))\overset c\equiv(pk,\mathrm{Enc}_{pk}(k),\mathrm{Enc}'_k(m_1))$ via

$(\mathrm{Enc}(k),\mathrm{Enc}'_k(m_0))\overset{\Pi}{\approx}(\mathrm{Enc}(0^n),\mathrm{Enc}'_k(m_0))\overset{\Pi'}{\approx}(\mathrm{Enc}(0^n),\mathrm{Enc}'_k(m_1))\overset{\Pi}{\approx}(\mathrm{Enc}(k),\mathrm{Enc}'_k(m_1))$

Steps 1 and 3 (reduce to $\Pi$ ): $\mathcal A_1$ picks $k$ itself, submits $(k,0^n)$ , and builds $\mathrm{Enc}'_k(m_0)$ with the $k$ it knows. The $\Pi$ reduction can know $k$ .
Step 2 (reduce to $\Pi'$ ): $\mathcal A'$ generates $(pk,sk)$ itself and sets $c_1 = \mathrm{Enc}_{pk}(0^n)$ , which carries no information about $k$ . That is exactly what $\Pi'$ ‘s security needs.

Summing the three inequalities, the middle terms cancel to 1, which gives the bound. (Trying to apply $\Pi'$ directly fails: $\mathrm{Enc}_{pk}(k)$ leaks information about $k$ to an unbounded analysis.)

∎

RSA encryption

Textbook RSA

AlgorithmTextbook RSA (Construction 10.14)

GenRSA gives $(N,e,d)$ with $ed\equiv1\bmod\varphi(N)$ . Public key $\langle N,e\rangle$ , private key $\langle N,d\rangle$ :

$c := m^e\bmod N,\qquad m := c^d\bmod N$

Deterministic ⇒ insecure (Theorem 10.6). All it guarantees, under RSA, is that a uniform $m\in\mathbb Z_N^*$ can’t be recovered entirely: partial information may leak, and real messages aren’t uniform. Recovering $d$ is as hard as factoring, but that says nothing about other ways to invert.

NoteRSA in practice

Encoding: $(\lVert N\rVert - 1)$ -bit strings become integers below $N$ (pad on the left, with a length indication). $m\notin\mathbb Z_N^*$ is negligibly likely, decryption still works (Exercise 7.8), and finding such an $m$ would factor $N$ ( $\gcd(m,N)$ ).
Small $e$ (for example $e = 3$ , needing $p, q\not\equiv1\bmod3$ ) makes encryption take two multiplications. Its weaknesses below are failings of textbook RSA, not of $e = 3$ .
Never small $d$ : $d < 2^{16}$ falls to brute force, and even $d\approx N^{1/4}$ is vulnerable (Wiener-type attacks).
CRT decryption: $m_p = c^{d\bmod(p-1)}\bmod p$ and $m_q = c^{d\bmod(q-1)}\bmod q$ , then recombine.

ExampleExample 10.15 ( $p = 11$ , $q = 23$ , $e = 3$ )

$N = 253$ , $\varphi = 220$ , $d = 147$ (since $3\cdot147 = 441 = 2\cdot220 + 1$ ). $m = 0111001_2 = 57$ and $c = 57^3\bmod253 = 250$ . Decryption via CRT: $8^{147\bmod10} = 8^7\equiv2\pmod{11}$ and $20^{147\bmod22} = 20^{15}\equiv11\pmod{23}$ , and indeed $57\leftrightarrow(2,11)$ . (Checked by hand.)

Attacks on textbook RSA

WarningSmall $e$ , short messages

If $e = 3$ and $m < N^{1/3}$ , then $m^3 < N$ and no reduction happens, so $m = \sqrt[3]c$ over the integers. A short message (under a third of $\lVert N\rVert$ bits) leaks immediately.

WarningHåstad’s broadcast attack

The same $m$ sent with $e = 3$ to three receivers $N_1, N_2, N_3$ (pairwise coprime, otherwise just factor them). CRT gives $\hat c\equiv m^3\bmod N_1N_2N_3$ , and since $m < \min N_i$ , $m^3 < N_1N_2N_3$ . So $m = \sqrt[3]{\hat c}$ over the integers.

AlgorithmMeet in the middle: $\sqrt L$ instead of $L$

For a random $m < 2^\ell$ (say, a hybrid encryption key), with high probability $m = r\cdot s$ with $r, s\le2^{\alpha\ell}$ ( $\frac12 < \alpha < 1$ ). Compute and sort $x_r = c/r^e\bmod N$ for $r\le T = 2^{\alpha\ell}$ , then look up $s^e$ for each $s$ . A match means $c = (rs)^e$ , giving $m = rs$ . Time is about $\ell\cdot2^{\alpha\ell}$ : an 80-bit key costs about $2^{40}$ instead of $2^{80}$ .

WarningCommon-modulus attacks

Insiders: a company giving every employee the same $N$ with different $(e_i,d_i)$ lets any employee factor $N$ from its own $(e_i,d_i)$ and compute everyone’s $d_j$ .
Outsiders: even with trusted insiders, the same $m$ sent under $(N,e_1)$ and $(N,e_2)$ with $\gcd(e_1,e_2) = 1$ falls to an eavesdropper. Bézout gives $Xe_1 + Ye_2 = 1$ , so $c_1^Xc_2^Y = m^{Xe_1+Ye_2} = m$ .

Padded RSA and PKCS #1 v1.5

AlgorithmPadded RSA (Construction 10.16)

For $m\in\{0,1\}^{\ell(n)}$ , choose random $r\in\{0,1\}^{\lVert N\rVert-\ell-1}$ and set $c = (r\Vert m)^e\bmod N$ . Decrypt and keep the low $\ell$ bits.

Padding	Security
$\ell = 2n - O(\log n)$ (tiny padding)	broken: brute-force the $\mathrm{poly}(n)$ paddings
$\ell = cn$ , $c < 2$	conjectured secure; proof only from an “ $\ell$ -padded RSA” assumption (Exercise 10.5)
$\ell = 1$	CPA-secure under RSA (Theorem 10.17), because $\mathrm{msb}\Vert\mathrm{lsb}$ is hard-core for RSA and $\mathrm{msb}(r\Vert m) = 0$ (Exercise 10.6)

DefinitionPKCS #1 v1.5 encryption

With $k$ the byte length of $N$ , a $D$ -byte message ( $D\le k - 11$ ) is encrypted as

$\big(\texttt{00}\ \Vert\ \texttt{02}\ \Vert\ r\ \Vert\ \texttt{00}\ \Vert\ m\big)^e\bmod N$

with $r$ consisting of $k - D - 3$ random nonzero bytes (so the $\texttt{00}$ separator is unambiguous). Believed CPA-secure with no proof. Broken under chosen-ciphertext attack (below), hence PKCS #1 v2 (RSA-OAEP).

ElGamal encryption

LemmaLemma 10.18 — Multiplying by a random element hides everything

For any fixed $m$ in a finite group $\mathbb G$ , $m\cdot g$ with uniform $g$ is uniform: $\Pr[m\cdot g = \hat g] = \Pr[g = m^{-1}\hat g] = 1/\lvert\mathbb G\rvert$ . With a shared random $g$ this is a perfectly secret one-time pad over $\mathbb G$ (the OTP is the case $\mathbb G = (\{0,1\}^\ell,\oplus)$ ). ElGamal’s idea: replace the shared random pad with a pseudorandom one, $h^y = g^{xy}$ , that the receiver can compute but which looks random to everyone else (DDH).

AlgorithmElGamal (Construction 10.19)

$\mathcal G(1^n)$ gives $(\mathbb G,q,g)$ . Then $x\leftarrow\mathbb Z_q$ , $pk = \langle\mathbb G,q,g,h = g^x\rangle$ , $sk = x$ .

$\mathrm{Enc}(m) = \langle g^y,\ h^y\cdot m\rangle\ (y\leftarrow\mathbb Z_q),\qquad\mathrm{Dec}(c_1,c_2) = c_2/c_1^x$

Correctness: $\frac{h^ym}{(g^y)^x} = \frac{g^{xy}m}{g^{xy}} = m$ . It is the Diffie–Hellman exchange with the receiver’s message published ahead of time as $pk$ , and the DH key used as a one-time pad (Exercise 10.3 generalises: any 2-round key exchange gives CPA-secure PKE).

TheoremTheorem 10.20 — DDH ⇒ ElGamal is CPA-secure

ProofThe DH pad versus a random pad

In $\tilde\Pi$ , the ciphertext is $\langle g^y, g^z\cdot m\rangle$ for random $z$ . By Lemma 10.18 it is independent of $m$ , so success is exactly $\frac12$ . Distinguisher $D(\mathbb G,q,g,g_1,g_2,g_3)$ : set $pk = (\ldots,g_1)$ , get $m_0, m_1$ , give $\langle g_2,\ g_3m_b\rangle$ , and output 1 iff $\mathcal A$ guesses $b$ .

On $(g^x,g^y,g^z)$ : $\mathcal A$ is in $\tilde\Pi$ , so $D$ outputs 1 with probability $\frac12$ .
On $(g^x,g^y,g^{xy})$ : real ElGamal, so $D$ outputs 1 with probability $\varepsilon$ .

DDH hardness gives $\lvert\varepsilon - \frac12\rvert\le\mathrm{negl}$ .

∎

ExampleEncoding into $\mathcal{QR}_p$ , worked (Example 10.21)

Encoding for a safe prime $p = 2q + 1$ : an $(n-1)$ -bit string $\hat m$ becomes $\bar m = \hat m + 1\in\{1,\ldots,q\}$ , then $m = \bar m^2\bmod p$ . This is one-to-one, since of the two roots $\pm\bar m$ exactly one lies in $\{1,\ldots,q\}$ . It inverts via modular square roots.

$q = 83$ , $p = 167$ , $g = 4$ , $x = 37$ , $h = 4^{37}\bmod167 = 76$ . $\hat m = 011101 = 29$ , so $\bar m = 30$ and $m = 900\bmod167 = 65$ . With $y = 71$ : $c = (4^{71}, 76^{71}\cdot65) = (132, 44)$ . Decrypt: $132^{37} = 124$ , $124^{-1} = 66$ (as $124\cdot66 = 8184 = 49\cdot167 + 1$ ), and $44\cdot66 = 2904\equiv65$ . The roots of 65 are 30 and 137, keep $30\le q$ , giving $\hat m = 29$ . (Inverse and product checked by hand.)

NoteElGamal in practice

Widely used over elliptic-curve groups. Shared parameters $(\mathbb G,q,g)$ are fine: DDH is believed hard even for whoever generated them, so each user just picks its own $x$ . With RSA, by contrast, whoever generates $N$ knows its factorisation, so moduli can’t be shared.

Chosen-ciphertext attacks

IntuitionMore realistic here than in the private-key setting

A public-key receiver expects ciphertexts from many, possibly unknown senders. An adversary can:

send $c'$ while claiming to be the honest sender $S$ (forged email “From”), then infer something from the receiver’s behaviour;
send $c'$ in its own name, a possibility unique to public-key encryption, and perhaps get the decryption back directly.

ExampleCCA scenarios

Password oracle: a bank replies “invalid password” (non-alphanumeric) versus “password incorrect”. Submitting modified ciphertexts of a user’s encrypted password and watching the errors may reveal it. Replaying $c$ itself teaches nothing (and timestamps add yet another error type).
Quoting reply: an encrypted email $c'$ gets answered with “you wrote: …”. Even an answer encrypted to the adversary hands back $\mathrm{Dec}(c')$ , so the receiver is a decryption oracle.
Malleable auction: if $\mathrm{Enc}(m)$ can be turned into $\mathrm{Enc}(2m)$ , the adversary always outbids $S$ without learning either bid. That is consistent with CPA security, and shows why non-malleability matters.

DefinitionCCA security (Def. 10.22)

$\mathrm{PubK}^{\mathrm{cca}}$ : $\mathcal A$ gets $pk$ and a decryption oracle before and after the challenge, but may not query the challenge $c$ itself. CCA-secure if success is at most $\frac12 + \mathrm{negl}$ . (No encryption oracle is needed: $pk$ provides it.) Constructions are more involved: Cramer–Shoup (DDH, about twice ElGamal’s cost) and RSA-OAEP (Chapter 13). This is the public-key counterpart of encrypt-then-MAC.

WarningEvery scheme so far falls to CCA

Textbook RSA: blinding. With random $r$ , query $c' = r^e\cdot c\bmod N$ , get $m' = rm$ , output $m = m'r^{-1}$ . This destroys even “can’t recover a random $m$ ”. Malleable: $2^ec$ decrypts to $2m$ .
PKCS #1 v1.5: Bleichenbacher (1998). A server revealing only “padding valid / invalid” is enough to recover $m$ from many adaptively chosen ciphertexts. Such oracles are easy to get in practice (TLS error messages). This drove the move to OAEP, and descendants (ROBOT, 2017) keep turning up.
ElGamal: $\langle c_1,\ c_2\cdot m'\rangle$ encrypts $m\cdot m'$ . To avoid a suspicious repeated $c_1$ , re-randomise: $\langle c_1g^{y''},\ c_2h^{y''}m'\rangle$ . CPA-secure, yet fully malleable.

Trapdoor permutations and generic public-key encryption

DefinitionTrapdoor permutation family (Def. 10.23)

$(\mathrm{Gen},\mathrm{Samp},f,\mathrm{Inv})$ : $\mathrm{Gen}(1^n)$ outputs an index $I$ and a trapdoor $td$ . Forgetting $td$ leaves a one-way permutation family, while $\mathrm{Inv}_{td}(f_I(x)) = x$ always. Example: RSA with $td = d$ . Another: Rabin squaring over $\mathcal{QR}_N$ for Blum integers (below).

DefinitionHard-core predicate for a family (Def. 10.24)

$hc_I(x)$ is hard-core if every ppt $\mathcal A$ predicts it from $(I, f_I(x))$ with probability at most $\frac12 + \mathrm{negl}$ . Every trapdoor permutation family can be modified to have one (Theorem 10.27, via Goldreich–Levin); RSA’s least-significant bit is hard-core.

AlgorithmPKE from any trapdoor permutation (Construction 10.25)

$pk = I$ , $sk = (I,td)$ . For one bit $m$ : $x\leftarrow D_I$ , ciphertext $\langle f_I(x),\ hc_I(x)\oplus m\rangle$ . Decrypt: $x = f_I^{-1}(y)$ , output $hc_I(x)\oplus m'$ . The hard-core bit is a one-bit pseudorandom pad.

TheoremTheorem 10.26 — Construction 10.25 is CPA-secure

(The book’s statement says “chosen-ciphertext”, but the proof, and the truth, is chosen-plaintext. The scheme is clearly malleable: flip the second component.)

ProofEncryption adversary ⇒ hard-core-bit predictor

Assume without loss of generality $m_0\ne m_1$ . $\mathcal A_h(I,y)$ : run $\mathcal A$ to get $m_0, m_1$ ; pick random bits $z$ (a guess for $hc(x)$ ) and $b$ ; give $\langle y,\ m_b\oplus z\rangle$ . Output $z$ if $\mathcal A$ guesses $b$ , else $\bar z$ .

If $z = hc(x)$ , $\mathcal A$ sees a real encryption of $m_b$ , so it is right with probability $\varepsilon$ .
If $z\ne hc(x)$ , it sees an encryption of $m_{\bar b}$ , so it is wrong with probability $\varepsilon$ .

Then $\Pr[\mathcal A_h = hc(x)] = \frac12(\varepsilon + \varepsilon) = \varepsilon$ , which must be at most $\frac12 + \mathrm{negl}$ .

∎

NoteShorter ciphertexts for long messages

Bit-by-bit costs one $f_I$ evaluation and one image per bit. Instead, iterate $x_{i+1} = f_I(x_i)$ and send $\langle x_{\ell+1},\ hc(x_1)\oplus m_1,\ldots,hc(x_\ell)\oplus m_\ell\rangle$ : one domain element plus $\ell$ bits. The receiver inverts backwards using $td$ . Security follows from Blum–Micali PRG ideas (Blum–Goldwasser).

Chapter 11 — Additional schemes

Quadratic residues

DefinitionQuadratic residues modulo a prime

$y$ is a quadratic residue (QR) if $y = x^2$ for some $x$ , and a non-residue (QNR) otherwise. For an odd prime $p$ , every QR has exactly two roots $\pm x$ (Proposition 11.1: $(x - x')(x + x')\equiv0$ ), so squaring is 2-to-1 and $\lvert\mathcal{QR}_p\rvert = \lvert\mathcal{QNR}_p\rvert = \frac{p-1}2$ . With a generator $g$ , the QRs are exactly the even powers $g^{2i}$ .

TheoremProposition 11.2 — Euler’s criterion

The Legendre/Jacobi symbol satisfies $\mathcal J_p(x) = x^{(p-1)/2}\bmod p\in\{\pm1\}$ (QR gives $+1$ ). Even powers give $g^{(p-1)j} = 1$ ; odd powers give $g^{(p-1)/2} = -1$ , the only square root of 1 other than 1. So residuosity mod a prime is decidable by one exponentiation. It is multiplicative, $\mathcal J_p(xy) = \mathcal J_p(x)\mathcal J_p(y)$ : QR·QR and QNR·QNR are QRs, and QR·QNR is a QNR.

TheoremQuadratic residues modulo $N = pq$ (Propositions 11.6, 11.8)

By CRT, $y\leftrightarrow(y_p,y_q)$ is a QR mod $N$ iff both components are QRs. Each QR has four roots $(\pm x_p,\pm x_q)$ , so $\lvert\mathcal{QR}_N\rvert = \varphi(N)/4$ . With $\mathcal J_N(x) = \mathcal J_p(x)\mathcal J_q(x)$ :

half of $\mathbb Z_N^*$ is in $\mathcal J_N^{+1}$ ;
$\mathcal{QR}_N\subseteq\mathcal J_N^{+1}$ ;
half of $\mathcal J_N^{+1}$ is $\mathcal{QR}_N$ , and the other half is $\mathcal{QNR}_N^{+1}$ (both component symbols $-1$ ).

$\mathcal J_N$ is multiplicative. QR·QNR $^{+1}$ is in QNR $^{+1}$ and QNR $^{+1}$ ·QNR $^{+1}$ is a QR, but two arbitrary QNRs needn’t multiply to a QR.

ExampleThe four square roots of 4 mod 15 (Example 11.7)

$2\leftrightarrow(2,2)$ , so the roots are $(2,2)\leftrightarrow2$ , $(2,1)\leftrightarrow7$ , $(3,2)\leftrightarrow8$ , $(3,1)\leftrightarrow13$ . Check: $7^2 = 49\equiv4$ , $8^2 = 64\equiv4$ , $13^2 = 169\equiv4$ .

DefinitionQuadratic residuosity assumption (Def. 11.11)

$\mathcal J_N(x)$ is computable without the factorisation (reciprocity-based algorithm), so $\mathcal J_N = -1$ certifies a non-residue. But within $\mathcal J_N^{+1}$ nobody efficiently tells QR from QNR $^{+1}$ : $\lvert\Pr[\mathcal A(N,qr) = 1] - \Pr[\mathcal A(N,qnr) = 1]\rvert\le\mathrm{negl}$ . Knowing the factors makes it easy (check $\mathcal J_p$ and $\mathcal J_q$ ). QR hardness implies factoring hardness. (A Gauss-era problem.)

Goldwasser–Micali encryption

AlgorithmGoldwasser–Micali (Construction 11.12)

$pk = \langle N, z\rangle$ with $z\leftarrow\mathcal{QNR}_N^{+1}$ (the receiver samples it by testing symbols: Exercise 11.3); $sk = (p,q)$ . For a bit $m$ :

$c = z^m\cdot x^2\bmod N\quad(x\leftarrow\mathbb Z_N^*)$

A random QR encrypts 0 and a random QNR $^{+1}$ encrypts 1 ( $zx^2$ is uniform in $\mathcal{QNR}_N^{+1}$ : Exercise 11.5). Decrypt by deciding residuosity with $p, q$ . The first provably secure (probabilistic) public-key scheme. Inefficient: one modular element per bit.

TheoremTheorem 11.13 — QR assumption ⇒ GM is CPA-secure

ProofReplace

z

with a residue

$D(N,z)$ runs $\mathcal A$ with $pk = \langle N,z\rangle$ and outputs 1 iff $\mathcal A$ guesses $b$ .

$z\in\mathcal{QNR}^{+1}$ : the real scheme, success $\varepsilon$ .
$z\in\mathcal{QR}$ : both $x^2$ and $zx^2$ are uniform in $\mathcal{QR}_N$ (Lemma 10.18 in the group $\mathcal{QR}_N$ ), so the view is independent of $b$ and success is $\frac12$ .

QR hardness gives $\lvert\varepsilon - \frac12\rvert\le\mathrm{negl}$ .

∎

ExampleVariants (Exercises 11.6–11.8, 11.12)

Blum integers ( $p\equiv q\equiv3\bmod4$ ): $-1\in\mathcal{QNR}_N^{+1}$ , since $(-1)^{(p-1)/2} = -1$ for $p\equiv3\bmod4$ . So $c = (-1)^mx^2$ needs no $z$ in the key.
Repetition: encrypt 0 as $n$ random QRs and 1 as $n$ random $\mathcal J_N^{+1}$ elements (sample $x\leftarrow\mathbb Z_N^*$ until $\mathcal J_N(x) = 1$ ). Decrypt: “0” iff all are QRs. Error $2^{-n}$ .
DDH fails in $\mathbb Z_p^*$ : Legendre symbols reveal the parities of $x$ and $y$ , hence of $xy$ . Compare with the symbol of the third element: advantage about $\frac14$ . That is why prime-order subgroups are needed.
XOR-homomorphic: $c_1c_2 = z^{m_1+m_2}(x_1x_2)^2$ encrypts $m_1\oplus m_2$ (since $z^2$ is a QR).

(Worked here.)

Rabin: square roots and factoring

Computing square roots with the factorisation

AlgorithmSquare roots modulo a prime (Algorithm 11.16)

$p\equiv3\bmod4$ : $x = a^{(p+1)/4}\bmod p$ , since $x^2 = a^{(p+1)/2} = a\cdot a^{(p-1)/2} = a$ .
$p\equiv1\bmod4$ (Tonelli–Shanks style): write $\frac{p-1}2 = 2^\ell m$ with $m$ odd, and keep the invariant $a^rb^{r'}\equiv1$ ( $r$ odd-bound, $r'$ even) using a non-residue $b$ (found by random sampling: half of all elements; no deterministic polynomial method is known). Repeatedly halve both exponents. Whenever the result is $-1$ , multiply by $b^{(p-1)/2} = -1$ to restore $+1$ . At the end, with $r$ odd, $a^{(r+1)/2}b^{r'/2}$ is a root.

ExampleWorked roots

$p = 29$ , $a = 22$ : $22^7\cdot2^{14}\equiv1$ , so the root is $22^4\cdot2^7 = 23\cdot12 = 276\equiv15$ . Check: $15^2 = 225\equiv22$ .
$p = 29$ , $a = 7$ : $7^7\equiv1$ directly (exponent odd), so the root is $7^4 = 2401\equiv23$ . Check: $23^2 = 529\equiv7$ .
$p = 17$ , $a = 4$ , $b = 3$ : $4^4 = 1$ , $4^2 = -1$ so multiply by $3^8 = -1$ ; then $4\cdot3^4\equiv1$ , so the root is $4\cdot3^2 = 36\equiv2$ .

(All checked by hand.)

NoteSquare roots modulo $N$

Find roots of $a\bmod p$ and $a\bmod q$ and combine by CRT: all four roots come from the sign choices.

Square roots ⟺ factoring

LemmaLemma 11.20 — Unrelated roots factor $N$

If $x_1^2\equiv x_2^2$ but $x_1\ne\pm x_2\bmod N$ , then $\gcd(N,x_1 + x_2)$ (or $\gcd(N,x_1 - x_2)$ ) is a prime factor of $N$ . In CRT form, $x_2\leftrightarrow(-x_{1,p},x_{1,q})$ , so $x_1 + x_2\leftrightarrow(0,2x_{1,q})$ : divisible by $p$ but not by $q$ . (The congruence-of-squares idea behind the quadratic sieve.)

TheoremTheorem 11.21 — Computing square roots is as hard as factoring

A square-root finder with success $\varepsilon$ gives a factoring algorithm with success $\varepsilon/2$ .

ProofChoose a root, ask for a root, hope for a different one

$\mathcal A_{\mathrm{fact}}(N)$ : pick $x_1\leftarrow\mathbb Z_N^*$ , set $y = x_1^2$ , and get $x_2\leftarrow\mathcal A(N,y)$ . Since $y$ is a uniform QR, $\mathcal A$ succeeds with probability $\varepsilon$ . Key point: $x_1$ is uniform among $y$ ‘s four roots from $\mathcal A$ ‘s point of view, so whichever root $\mathcal A$ outputs, it differs from $\pm x_1$ with probability exactly $\frac12$ . That gives $\varepsilon/2$ by Lemma 11.20. No assumption on how $\mathcal A$ chooses among roots is needed.

∎

DefinitionBlum integers and the Rabin trapdoor permutation

$N = pq$ with $p\equiv q\equiv3\bmod4$ . Proposition 11.22: every QR has exactly one square root that is itself a QR. ( $-1$ is a non-residue mod $p$ and mod $q$ , so exactly one sign pattern makes both components residues.) Hence

$f_N(x) = x^2\bmod N$

is a permutation of $\mathcal{QR}_N$ : one-way if factoring is hard, with trapdoor $(p,q)$ . Theorem 11.23: factoring hard ⇒ trapdoor permutations exist. (Exercise 11.10 gives a variant permuting $\{x < N/2 : \mathcal J_N(x) = 1\}$ .)

AlgorithmRabin encryption

Generic: Construction 10.25 with $\mathrm{lsb}$ , which is hard-core for Rabin.
Padded Rabin (Construction 11.24, one bit): pick $r\in\{0,1\}^{\lVert N\rVert-2}$ until $r\Vert m\in\mathcal{QR}_N$ , then $c = (r\Vert m)^2\bmod N$ . Decrypt: the unique QR root, keep its lowest bit. CPA-secure if factoring is hard (Theorem 11.25). Exercise 11.11 extends to $n$ -bit messages, using the extra bits $\mathcal J_N(x)$ and " $x < N/2$ " to make $x\mapsto(x^2,\mathcal J_N,\mathrm{half})$ injective, with no proof.

ImportantRabin versus RSA

	Rabin	RSA
Hardness	equivalent to factoring	not known to be; RSA may be easier
Forward cost	one squaring	$e$ -th power, slightly slower for large $e$
Domain	a permutation of $\mathcal{QR}_N$ only (more care)	all of $\mathbb Z_N^*$
Textbook-version CCA	reveals the private key	blinding attack, but no key recovery
Adoption	rare	dominant, largely historical accident

Textbook Rabin’s key-recovery CCA (Exercise 11.9): pick $x$ with $\mathcal J_N(x) = -1$ (so $x\notin\mathcal{QR}_N$ ) and submit $c = x^2$ . The decryptor returns the QR root $y$ , necessarily $y\ne\pm x$ (since $-x$ also has symbol $-1$ for Blum $N$ ). Then $\gcd(x - y,N)$ factors $N$ .

Paillier encryption

TheoremProposition 11.26 — The structure of $\mathbb Z_{N^2}^*$

For $N = pq$ with $p, q$ distinct primes of equal length:

$\gcd(N,\varphi(N)) = 1$ (equal length means $q\nmid p - 1$ );
$(1+N)^a\equiv1 + aN\pmod{N^2}$ (binomial theorem; terms with $N^{\ge2}$ vanish), so $1 + N$ has order $N$ ;
$\mathbb Z_N\times\mathbb Z_N^*\simeq\mathbb Z_{N^2}^*$ via $f(a,b) = (1+N)^a\cdot b^N\bmod N^2$ .

ProofWhy

f

is an isomorphism (Claims 11.27–11.29)

Sizes match: $\varphi(N^2) = N\varphi(N)$ .

Injective: $f(a_1,b_1) = f(a_2,b_2)$ gives $(1+N)^{a_1-a_2}(b_1/b_2)^N\equiv1$ . Raising to $\varphi(N)$ kills the second factor (the group order is $N\varphi(N)$ ). So $N\mid(a_1 - a_2)\varphi(N)$ , hence $a_1 = a_2$ . Then $b_1^N\equiv b_2^N\bmod N$ , and since $x\mapsto x^N$ is a permutation of $\mathbb Z_N^*$ ( $\gcd(N,\varphi(N)) = 1$ ), $b_1 = b_2$ .

Homomorphism: exponents of $1 + N$ live mod $N$ , and $(b_1b_2)^N\bmod N^2$ depends only on $b_1b_2\bmod N$ (binomial expansion of $(r + \gamma N)^N$ ).

∎

Definition $N$ -th residues and the DCR assumption (Def. 11.30)

$x\leftrightarrow(a,b)$ gives $x^N\leftrightarrow(0,b^N)$ , so the $N$ -th residues are exactly $\mathrm{Res}(N^2)\leftrightarrow\{(0,b)\}$ . Decisional composite residuosity: a random $N$ -th residue $(0,r)$ is indistinguishable from a random element $(r',r)$ : $\lvert\Pr[\mathcal A(N, r^N\bmod N^2) = 1] - \Pr[\mathcal A(N,r) = 1]\rvert\le\mathrm{negl}$ . A generalisation of quadratic residuosity.

AlgorithmPaillier (Construction 11.32)

$pk = N$ , $sk = \varphi(N)$ . For $m\in\mathbb Z_N$ , $r\leftarrow\mathbb Z_N^*$ :

$c = (1+N)^m\cdot r^N\bmod N^2\ \leftrightarrow\ (m,r)$

$\mathrm{Dec}(c) = \frac{[c^{\varphi(N)}\bmod N^2] - 1}N\cdot\varphi(N)^{-1}\bmod N$

Why decryption works: $c^{\varphi(N)}\leftrightarrow(m\varphi(N), r^{\varphi(N)} = 1)$ , i.e. $(1+N)^{m\varphi(N)} = 1 + m\varphi(N)N$ . Subtract 1, divide by $N$ , multiply by $\varphi(N)^{-1}$ . Intuition: the ciphertext is $(m,1)\cdot(0,r)$ ; DCR lets you swap the residue $(0,r)$ for a random $(r',r)$ , which pads $m$ perfectly in $\mathbb Z_N$ .

ExampleExample 11.31 ( $N = 11\cdot17 = 187$ , $N^2 = 34969$ )

$m = 175$ , $r = 83$ : $c = 188^{175}\cdot83^{187}\bmod34969 = 23911$ . With $\varphi = 160$ : $\hat c = 23911^{160}\bmod N^2 = 25620$ , so $\hat m = (25620 - 1)/187 = 137$ . Then $160^{-1}\equiv90\pmod{187}$ (as $160\cdot90 = 14400 = 77\cdot187 + 1$ ), and $137\cdot90 = 12330\equiv175$ . (Final steps checked by hand.)

TheoremTheorem 11.33 — DCR ⇒ Paillier is CPA-secure

$D(N,y)$ gives $\mathcal A$ the ciphertext $(1+N)^{m_b}\cdot y$ . If $y = r^N$ , this is real Paillier (success $\varepsilon$ ; $r$ uniform in $\mathbb Z_{N^2}^*$ or $\mathbb Z_N^*$ gives the same $r^N$ distribution). If $y$ is uniform in $\mathbb Z_{N^2}^*$ , the ciphertext is uniform (Lemma 10.18), so success is $\frac12$ . DCR gives $\lvert\varepsilon - \frac12\rvert\le\mathrm{negl}$ .

Homomorphic encryption

DefinitionHomomorphic encryption (Def. 11.34)

Plaintexts in a group $\mathcal M$ , ciphertexts in a group $\mathcal C$ , and $\mathrm{Dec}(c_1\cdot c_2) = \mathrm{Dec}(c_1)\cdot\mathrm{Dec}(c_2)$ .

Scheme	$\mathcal C$	$\mathcal M$	Operation on plaintexts
Paillier	$\mathbb Z_{N^2}^*$	$(\mathbb Z_N,+)$	addition mod $N$ (and $c^k$ gives $km$ )
ElGamal	$\mathbb G\times\mathbb G$	$\mathbb G$	multiplication
Goldwasser–Micali	$\mathbb Z_N^*$	$\mathbb Z_2$	XOR

Homomorphism is malleability by design: these schemes cannot be CCA-secure.

ExampleEncrypted voting with Paillier

The authority publishes $N$ .
Voter $i$ casts $c_i = (1+N)^{v_i}r_i^N$ with $v_i\in\{0,1\}$ (no/yes).
Everyone multiplies the ballots: $c^* = \prod c_i\bmod N^2$ , which encrypts $\sum v_i$ .
The authority decrypts only $c^*$ : the tally without any individual vote.

This assumes honest behaviour. Cheaters (for example a ballot encrypting $v = 5$ ) need zero-knowledge validity proofs, threshold decryption, and the like, which belong to the field of secure protocols.

The random oracle model, CPA/CCA RSA encryption, and OAEP

NoteModel

Proofs here treat a hash $H$ as a public random function; see the random oracle model for the methodology, its proof techniques (lazy sampling, programming, observing queries) and its caveats. All constructions work with any trapdoor permutation; RSA is the usual instance.

AlgorithmCPA-secure RSA in the ROM (Construction 13.1)

$c = \langle r^e\bmod N,\ H(r)\oplus m\rangle$ for random $r\in\mathbb Z_N^*$ ; decrypt $r = c_1^d$ , then $m = H(r)\oplus c_2$ . As efficient as textbook RSA plus one hash. Why the ROM matters: RSA only says $r$ can’t be recovered entirely; a partial leak could ruin $G(r)$ for a PRG $G$ , but $H(r)$ stays uniform until $r$ itself is queried.

TheoremTheorem 13.2 — RSA ⇒ Construction 13.1 is CPA-secure (ROM)

Let $\mathsf{Query}$ be the event that $\mathcal A$ queries $H(r)$ .

Without it, $H(r)$ is a one-time pad: $\Pr[\mathsf{Succ}\wedge\neg\mathsf{Query}]\le\frac12$ .
$\Pr[\mathsf{Query}]$ is negligible: given an RSA instance $(N,e,c_1)$ , run $\mathcal A$ with $c_2$ random, simulate $H$ lazily, and watch the queries for $x$ with $x^e = c_1$ . The view is perfect, so RSA is solved with probability exactly $\Pr[\mathsf{Query}]$ .

AlgorithmCCA-secure RSA in the ROM (Construction 13.5)

$c = \langle r^e\bmod N,\ \mathrm{Enc}'_{H(r)}(m)\rangle$ with $\Pi'$ a CCA-secure private-key scheme (encrypt-then-MAC). Construction 13.1 is this with the one-time pad, and works with any CPA-secure $\Pi'$ (Exercise 13.3).

TheoremTheorem 13.6 — RSA + CCA-secure $\Pi'$ ⇒ Construction 13.5 is CCA-secure (ROM)

Without $\mathsf{Query}$ : reduce to $\Pi'$ ‘s CCA game, implicitly setting $H(r) = k$ (the $\Pi'$ challenger’s key). Decryption queries with first component $c_1$ go to the $\Pi'$ oracle; others are decrypted with $d$ , which the reduction knows. The views agree until $\mathsf{Query}$ .
$\Pr[\mathsf{Query}]$ negligible: now there is no $d$ , so program the oracle with a table of triples $(\hat r\ \text{or}\ ?,\ \hat c_1,\ \hat k)$ . Answer a decryption query $\langle\bar c_1,\bar c_2\rangle$ with $\mathrm{Dec}'_{\bar k}(\bar c_2)$ , where $\bar k$ is the key stored for $\bar c_1$ (fresh if none: entry $(?,\bar c_1,\bar k)$ , implicitly $H(\bar c_1^{1/e}) = \bar k$ ). Answer a hash query $\bar r$ by looking up $\bar r^e$ in the second column, keeping the two consistent. The challenge gets entry $(?,c_1,k)$ ; if $\mathcal A$ ever hashes $r$ with $r^e = c_1$ , output $r$ .

AlgorithmRSA-OAEP (Construction 13.9; Bellare–Rogaway)

Two oracles $G, H : \{0,1\}^n\to\{0,1\}^n$ , $\lVert N\rVert > 2n$ , message $m\in\{0,1\}^{n/2}$ , random $r\in\{0,1\}^n$ :

$\hat m_1 = G(r)\oplus(m\Vert0^{n/2}),\qquad\hat m = \hat m_1\ \Vert\ \big(r\oplus H(\hat m_1)\big),\qquad c = \hat m^e\bmod N$

(The book’s prose says $\hat m^d$ ; the construction box correctly has $e$ .) Decrypt $\hat m = c^d$ , split it, recover $r = H(\hat m_1)\oplus\hat m_2$ , then $m' = \hat m_1\oplus G(r)$ ; output $\perp$ unless the last $n/2$ bits are zero (this redundancy check is what rejects mauled ciphertexts). A two-round Feistel-like padding: the ciphertext is one element of $\mathbb Z_N^*$ (Construction 13.5 also carries a private-key ciphertext), so it is ideal for short messages and key transport in hybrid encryption.

Security: CCA-secure under RSA with $G, H$ random oracles, for suitable $e$ including $e = 3$ ; the original proof was flawed (Shoup) and later repaired for RSA (Fujisaki–Okamoto–Pointcheval–Stern), and OAEP+ variants handle general trapdoor permutations. Standardised as PKCS #1 v2.1, the replacement for the Bleichenbacher-broken v1.5 padding. (Implementations must not leak which check failed: Manger’s attack, my addition.)

Quick reference

Object	Statement	Note
Setting	publish $pk$ ; authenticated distribution assumed	about 100–1000× slower than private-key
EAV ⇒ CPA	adversary holds $pk$	unlike private-key
Impossibilities	no perfect secrecy; no deterministic scheme	grade example
Multi-message	hybrid over positions, loss factor $t$	bit-by-bit extension
Hybrid encryption	$\langle\mathrm{Enc}_{pk}(k),\mathrm{Enc}'_k(m)\rangle$	needs only EAV-secure $\Pi'$
Textbook RSA	$m^e\bmod N$	deterministic, malleable, blindable
RSA attacks	cube root; Håstad; $\sqrt L$ ; common modulus
Padded RSA	random $r\Vert m$	$\ell = 1$ provable; PKCS #1 v1.5 heuristic
ElGamal	$\langle g^y,h^ym\rangle$	DDH ⇒ CPA; multiplicatively malleable
CCA	decryption oracle except on the challenge	all schemes above fail
Bleichenbacher	v1.5 padding oracle recovers $m$	led to OAEP
Trapdoor permutation PKE	$\langle f(x),hc(x)\oplus m\rangle$	CPA (book says CCA, a typo)
Euler criterion	$\mathcal J_p(x) = x^{(p-1)/2}$	QR mod $p$ is easy
QR mod $N$	$\frac14$ of $\mathbb Z_N^*$ ; $\frac12$ of $\mathcal J^{+1}$	4 roots
QR assumption	QR versus QNR $^{+1}$ hard without factors
Goldwasser–Micali	$z^mx^2$	first provably secure scheme
Square roots	$a^{(p+1)/4}$ ( $p\equiv3$ ); Tonelli–Shanks	CRT for $N$
Roots ⟺ factoring	unrelated roots give $\gcd$ ; success $\varepsilon/2$
Rabin	squaring on $\mathcal{QR}_N$ , Blum $N$	as hard as factoring; textbook CCA leaks key
Paillier	$(1+N)^mr^N\bmod N^2$	DCR; additively homomorphic
Voting	multiply ballots, decrypt the tally	honest-but-curious only

Facts to keep to hand

Public keys make the encryption oracle free. Eavesdropping security is CPA security, deterministic schemes are hopeless, perfect secrecy is impossible, and single-message security extends to many messages by a hybrid argument.
Real systems are hybrid. Public-key encryption moves a fresh key, private-key encryption moves the data, and the proof swaps the encrypted key for zeros so the one-time private-key scheme sees an independent key.
Textbook schemes are insecure; randomisation and structure fix CPA, not CCA. Textbook RSA leaks via small exponents, shared moduli and malleability. Padded RSA, ElGamal (DDH), Goldwasser–Micali (QR), Rabin (factoring) and Paillier (DCR) are CPA-secure, yet all are malleable. CCA needs more (Cramer–Shoup, OAEP), and padding oracles (Bleichenbacher) show the threat is practical.
Number-theoretic trapdoors drive everything. Trapdoor permutations plus hard-core bits give generic encryption. Square roots are equivalent to factoring (the Rabin advantage). $\mathbb Z_{N^2}^*\simeq\mathbb Z_N\times\mathbb Z_N^*$ yields Paillier’s additive homomorphism, useful for privacy-preserving computation such as voting.

References

Katz & Lindell, Introduction to Modern Cryptography — Chapters 10–11
Goldwasser & Micali, “Probabilistic Encryption” (1984)
ElGamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms” (1985)
Bleichenbacher, “Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1” (1998)
Paillier, “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes” (1999)

Related

Public-Key Encryption Schemes