Motivation
A public encryption rule must let anyone construct ciphertexts without giving everyone the ability to decrypt them. Deterministic encryption immediately creates a problem: an observer can encrypt two guessed messages and compare the results with a challenge. Randomness prevents this direct comparison, but saying that a ciphertext looks random is not a proof. We need a specified experiment and an explicit assumption connecting the experiment to a difficult mathematical task.
ElGamal provides a clean example. Its decryption equation follows from the commutative law for exponents in a cyclic group. Its secrecy argument uses a stronger, separate assertion: a particular shared group element should be computationally indistinguishable from an independent uniform one. Replacing that shared element by a random mask makes the challenge message disappear from its distribution.
We prove this conditional statement, including the implementation of random exponents with a fixed bounded number of fair bits. The plaintexts here are group elements. We do not construct an arbitrary-string encoding, an authenticated system or a deployed parameter set. Those require further definitions and constructions.
Definitions
For each positive security parameter , suppose a cyclic group of prime order is supplied. Its descriptions and fixed-length canonical element encodings have polynomial length in . Multiplication, inversion, membership tests and exponentiation by a binary integer take polynomial time. The bit length of is polynomially bounded. These are explicit family assumptions; this chapter does not construct such a family or prove its hardness.
Definition 4.2.1
(Decisional Diffie–Hellman assumption)
Discrete logarithm asks for from . Computational Diffie–Hellman asks for from . The decisional Diffie–Hellman assumption, DDH, says that no bounded probabilistic polynomial-time algorithm can distinguish the distributions
with nonnegligible advantage, where are independently uniform in . Advantage is the absolute difference between output-one probabilities. A function is negligible if, for every positive integer , it is eventually at most . The ideal distributions are mathematical experiments; exact sampling from an odd-sized set is not being claimed possible with a bounded fair-bit tape.
Definition 4.2.2
(ElGamal encryption)
The ideal encryption rules are
with . For correctness any are allowed. The bounded-bit implementation samples both secret and each fresh nonce by the procedure proved below.
Concept lensStructural
A Diffie–Hellman exchange followed by a group one-time pad
ElGamal is an ephemeral Diffie–Hellman exchange composed with a multiplicative pad. The fresh and the public determine the shared element , which the sender computes as and the receiver as . The message is masked as , a one-time pad in the group , and unmasked by . The security proof replaces the shared element by an independent uniform one; at that point the pad hides perfectly.
Definition 4.2.3
(Chosen-plaintext indistinguishability experiment)
In the chosen-plaintext indistinguishability experiment, the adversary receives , chooses two valid group messages , and retains arbitrary polynomial-size state. The challenger chooses a fresh fair bit , encrypts with a fresh nonce, and lets the adversary guess . Its advantage is . The adversary may perform any polynomial number of public encryptions itself; no secret encryption oracle is needed for this public-key experiment. No decryption oracle is provided.
Theorem/proposition
Theorem 4.2.4
(Correctness and bounded-bit exponent sampling)
ElGamal decrypts every valid ciphertext produced by its encryption rule to its original group message. Moreover, if , reducing an -bit uniform integer modulo gives a distribution within of uniform on in total variation, with a fixed polynomial running-time bound.
Theorem 4.2.5
(Chosen-plaintext secrecy follows from DDH)
For every bounded probabilistic polynomial-time chosen-plaintext adversary , there is such a DDH distinguisher with
for the bounded-bit implementation above. Thus DDH implies negligible chosen-plaintext advantage. This theorem asserts confidentiality in the specified experiment; it does not assert chosen-ciphertext security or ciphertext integrity.
Proof sketch or proof idea
Correctness is an algebraic identity
Proof
(The exponent identity)
For a valid ciphertext, . Hence . No logarithm is computed during decryption. The secret exponent permits exponentiation of the received first component; it is not a recipe for extracting an exponent from an arbitrary group element. The formula remains correct when either exponent is zero, although those rare choices can expose a message and must be included in the security experiment's probability accounting.
Approximate uniform exponents with bounded fair bits
Proof
(Counting preimages and comparing experiments)
Let . Each residue modulo has either or preimages among the integers. Its probability therefore differs from by less than . By the definition of total variation as half the sum of absolute differences, the resulting distance is at most . Drawing fair bits and performing integer division have bounded polynomial cost under the stated size assumptions.
We also use two elementary consequences of total variation. Applying a deterministic or randomized common postprocessing cannot increase it: for any output event, average its conditional probability, a number between zero and one, against the two input distributions. Replacing two independent draws, each within of its ideal law, changes the joint law by at most , by replacing one draw at a time and applying the triangle inequality. These statements hold even when later messages depend on the earlier draw.
Apply them to the key exponent and challenge nonce. Couple or compare the two entire experiments using the same adversary code, its coins, and challenge bit. The transcript and final success event differ in probability by at most . Public encryptions performed internally by the adversary are simply part of the same randomized postprocessing, so no unmentioned exact non-dyadic sampling is needed there.
Embed the adversary in a DDH test
Proof
(A wrapper that turns an adversary into a distinguisher)
First analyze the ideal exponent experiment. Give a tuple from either DDH distribution. It sends as the public key to , obtains its two messages and state, chooses a fresh fair bit , and gives the ciphertext . The distinguisher outputs one exactly when guesses correctly. All wrapper operations are efficient, and never computes the unknown exponents.
For a real Diffie–Hellman tuple, and . Thus the simulated ciphertext has exactly the ideal encryption distribution, and outputs one with that experiment's success probability.
For the independent tuple, is uniform in the group and independent of the public key, , the selected messages and adversary state. Conditional on those data and on either value of , multiplication by is a bijection of the group. Consequently is uniform with the same law for both choices. The complete view reveals no information about the fresh bit, and every guessing strategy has success probability exactly one half. The difference between the two output-one probabilities is therefore exactly the ideal chosen-plaintext advantage, under our absolute-value convention.
Finally compare the bounded-bit implementation with the ideal experiment using the previous bound. The triangle inequality gives the theorem. The additive statistical term is negligible, as is the DDH advantage under the assumption; their sum is negligible. A probability bound on average over generated keys is the statement proved here, not a promise that every possible key has identical secrecy.
Proof X-ray
The reduction does not solve Diffie–Hellman
Each component of the challenge tuple has one job. becomes the public key and the first ciphertext component, so the adversary sees a key and a nonce with exactly their ideal laws. The third component is used only as the message mask; the wrapper never needs , or , which is why it runs efficiently and why it proves nothing about solving Diffie–Hellman.
The key move is the random branch. Independence of from , , the chosen messages and the adversary's state makes uniform for both values of , so success there is exactly one half; marginal uniformity of alone would not suffice. The argument closes by subtraction: the distinguisher's advantage equals the ideal chosen-plaintext advantage, and bounded-bit sampling adds through the triangle inequality.
Worked examples
Worked example 4.2.6
(A complete toy encryption and decryption)
Work modulo twenty-three in the subgroup generated by two. Since and two is not one, this subgroup has prime order eleven. Take secret , public key , message and nonce . Then , , and . The ciphertext is .
Decryption computes . Its inverse modulo twenty-three is twelve, so , the original message. Exhaustive search over eleven exponents breaks this toy group immediately. It illustrates algebraic correctness only and supplies no evidence of the asymptotic DDH assumption.
Worked example 4.2.7
(Reusing a nonce reveals a message ratio)
With that same key and nonce, encrypt messages four and eight. The ciphertexts are and . Their second-component ratio is , equal to the message ratio . In general reused gives . If one message is known, the other is recovered by multiplication. Independent fresh nonces are an explicit part of the experiment; correctness of decryption does not repair a failed randomness assumption.
Worked example 4.2.8
(A deliberate ciphertext modification)
Change to by multiplying the second component by two. It decrypts to eight, twice the original message. More generally decrypts to for every known .
This gives a chosen-ciphertext attack: after receiving a challenge , choose and ask a decryption oracle about the distinct ciphertext . Dividing its answer by reveals the challenge message and hence the selected bit for distinct messages. The query is different from the prohibited challenge ciphertext, so simply forbidding that exact query does not prevent the attack. The chosen-plaintext theorem remains valid because its game supplies no such oracle.
Common mistakes
Counterexample mode
A message outside the masked group
The uniform-mask argument uses multiplication as a bijection of the exact message group. Suppose messages from the ambient group were allowed in the toy example above, where has order eleven. Choose and . Since , the element is not in . Every ciphertext has with , so when and when , whatever the key and nonce. One exponentiation recovers with certainty. The repair is the hypothesis of the theorem: both challenge messages must lie in . Arbitrary bit strings require a separately analyzed encoding or hybrid construction.
Common mistake
(DDH is computational, not statistical)
DDH is a computational indistinguishability assumption, not the claim that a Diffie–Hellman tuple is statistically uniform: an unbounded observer can recover the exponents and check it. Also, a discrete-log solver yields a shared-secret solver, which yields a decisional test; those easy directions do not prove converse equivalences. Finally, an authenticated communication system needs further protection against modifications, as the explicit attack demonstrates.
Common mistake
(Fresh does not mean never repeating)
Fresh randomness means a new independent sample, rather than a promise that a value can never recur. Under ideal uniform sampling, two nonce draws agree with probability ; a union bound over draws gives collision probability at most . Deliberately reusing a stored nonce is a different process, and the independence argument no longer applies.
Summary
The encryption equation proves correctness for every exponent. A precisely stated DDH assumption proves chosen-plaintext confidentiality through a wrapper that replaces a shared value by a uniform group mask. Bounded-bit exponent generation introduces an explicitly negligible statistical error. None of these statements prevents the multiplicative ciphertext modification or solves the remaining encoding and authentication problems.
Exercises
Quick check
(Explain why deterministic, publicly computable, correct encryption fails the two-message challenge experiment for distinct plaintexts.)
Solution
Encrypt both chosen messages and compare the challenge with those two outputs. Correct decryption implies the two ciphertexts are different: otherwise one ciphertext would have to decrypt to both messages. The comparison therefore recovers the bit with certainty, giving advantage one half under our convention.
Quick check
(What happens to an ElGamal ciphertext when the secret exponent is zero? Why does that observation not alone refute the averaged-key theorem?)
Solution
The public key is one and the second component equals the plaintext. Under the ideal distribution this key occurs with probability , which is negligible. The theorem is averaged over generated keys and can allow a negligible exceptional set. It does not establish safety for a deliberately selected zero key.
Quick check
(Why must the proof require that the replacement mask be independent of the public key and challenge first component, rather than merely marginally uniform?)
Solution
Marginal uniformity need not survive conditioning. For instance a uniform mask equal to another public uniform group element is completely known after that element is observed. The random DDH experiment supplies the stronger independence needed for the conditional uniform-mask argument.
Quick check
(If each exponent sampler is within of uniform, what statistical term replaces in the theorem?)
Solution
Replace the key draw and the challenge-nonce draw one at a time. The triangle inequality and contraction under the common adversary computation give a total success-probability change at most . Thus the same reduction yields the DDH advantage plus ; negligibility follows only if this statistical term is itself negligible.