Why agree on a key?
Symmetric encryption requires the parties to have a common secret. If Alice and Bob have never met, sending that secret over the same public channel defeats its purpose. Diffie–Hellman instead lets them compute a common group element while sending only public group elements. This changes the problem: it does not, by itself, establish who is at the other end.
Definition 10.2.1
(Diffie–Hellman exchange)
Let be a publicly specified cyclic group of prime order , written multiplicatively. Exponents are taken modulo . Everyone knows , and the generator ; Alice and Bob choose their exponents independently and uniformly in and keep them secret. The idealized exchange is:
- Alice sends ; Bob sends .
- Alice computes ; Bob computes .
- Both obtain , since .
The equality establishes correctness, not secrecy. An eavesdropper sees , and must compute or distinguish information about without knowing the exponents. In a practical system the raw group element is input to a suitable key-derivation function, along with a protocol-specific encoding of the transcript; it should not simply be treated as an arbitrary-length encryption key.
Worked example 10.2.2
(An exchange modulo 23)
In the nonzero residues modulo , the element has order : , and its order is not . Work in the subgroup . Alice chooses and sends ; Bob chooses and sends . Alice computes , and Bob computes . Equivalently . This tiny group makes arithmetic visible and provides no practical security.
What a passive security claim actually says
Definition 10.2.3
(Computational and decisional Diffie–Hellman)
The computational Diffie–Hellman problem (CDH) asks for given for independent uniform . The decisional Diffie–Hellman assumption (DDH) says that an efficient randomized observer cannot distinguish
where are independent uniform elements of . The intended statement concerns a family of suitably chosen groups as a security parameter grows: every probabilistic polynomial-time distinguisher has negligible difference between its two output probabilities. It is not a statement that the two distributions are identical. An unbounded observer can recover exponents and test the relation.
From discrete logarithms to CDH
The discrete logarithm problem asks for from . Knowing is sufficient to recover the shared element, but it is not part of the honest protocol: Alice already knows her own exponent. A passive attacker might try to recover it from the public value.
Theorem 10.2.4
(A discrete-log solver gives a CDH solver)
Suppose group operations and exponentiation are efficient. An algorithm that recovers the discrete logarithm of a uniform with probability at least yields a CDH algorithm with success probability at least on independent uniform .
Proof
(From a logarithm to the shared element)
Given , run the logarithm algorithm on to obtain a candidate , then output . Whenever modulo , this output is . Thus the CDH algorithm succeeds at least whenever the logarithm algorithm does. Its extra work is an exponentiation.
Common mistake
(Discrete-logarithm hardness does not give DDH)
This is a one-way reduction: it says that an efficient discrete-log algorithm would make CDH easy, not that every CDH algorithm must recover an exponent. In particular, difficulty of discrete logarithms alone does not establish the DDH assumption.
Worked example 10.2.5
(Recovering an exponent in the toy group)
An eavesdropper sees and modulo . Enumerating , , and reveals ; then . Exhaustive search is feasible in this tiny group. This example illustrates an attack, not a general claim that enumeration is the best algorithm in every group.
Theorem 10.2.6
(The raw shared element is pseudorandom under DDH)
In the ideal exchange above, a passive efficient observer given cannot distinguish it with non-negligible advantage from an observer given with independent uniform , assuming DDH for the group family.
Proof
(Identification of the two experiments)
Since for a uniform , the first experiment supplies precisely a DDH tuple and the second precisely a random tuple. A distinguisher for the stated experiments is therefore itself a DDH distinguisher with exactly the same difference in output probabilities.
Proof X-ray
Why the forwarding reduction loses nothing
Three hypotheses are used, each at one point. Passivity means the observer only reads and never chooses a public value, so a DDH challenge contains its entire view; an adversary that substitutes its own value for would need an answer the reduction cannot compute without an exponent. The exponents must be exactly uniform on , zero included, because the DDH tuples are defined with that distribution. The key move is that with uniform is uniform in , so the random experiment and the random DDH tuple are the same distribution, not merely close ones.
Since the views coincide exactly in both cases, the reduction's advantage equals the observer's advantage, and the argument closes by contraposition: a non-negligible observer would be a DDH distinguisher with the same advantage and essentially the same running time. If the exponents are instead sampled from nonzero residues, the views differ by at most in each experiment, and the equality becomes the bound of derived below.
The ideal choice includes exponent zero: if , then and is publicly known. This occurs with probability and is negligible in an appropriate large-order family, but is dangerous as a deliberate input. Implementations commonly reject the identity and use nonzero private exponents. Conditioning both exponents on being nonzero changes the ideal transcript distribution; any proof for that variant must account for this conditioning. The toy protocol is not a specification for production.
Experiments, advantage and the reduction
In a passive experiment the exchange is honest: the observer does not choose or replace either public message. First choose independent uniform . In the real experiment give the observer ; in the random experiment give it . The observer returns a bit, interpreted as its guess that the tuple is real. If its probabilities of outputting 1 are and , define its distinguishing advantage here as . Other texts may divide this quantity by two when measuring success in a random guessing game, so the convention matters.
The reduction takes a challenge tuple from the DDH experiment and passes precisely to the observer. It returns the observer's bit unchanged. If the challenge is real, the observer sees exactly the honest real experiment; if random, it sees exactly the random experiment. The reduction needs neither discrete logarithm, and introduces no simulation error. Its advantage is exactly the observer's advantage under the convention above. Thus a non-negligible observer advantage for a growing family would contradict DDH for that family, provided the observer and the forwarding reduction run in probabilistic polynomial time and the public group description is supplied in both experiments.
The third element is deliberately given to the observer in this experiment: the question is whether it looks independent and uniform even alongside the public transcript. It is not a protocol instruction to reveal a real session key. Actual encryption security additionally depends on how the element is encoded, derived into keys, and used. Computational indistinguishability does not imply statistical closeness or perfect independence. To see the distinction, consider the set of triples . A real tuple is always in this set, whereas a random tuple is in it with probability : once the first two components are fixed, exactly one third element fits. Thus an unbounded observer can distinguish with gap , even though DDH says efficient observers have only negligible advantage.
Concept lensAlgebraic
A rank question hidden in the exponent
Record the exponents of as a matrix over the field :
The tuple is a Diffie–Hellman tuple exactly when this matrix is singular, that is, has rank one, and a uniform makes it singular with probability , the count used above. DDH says that an efficient observer, who sees the entries only in the exponent, cannot tell rank one from rank two.
Worked example 10.2.7
(A visible distinguishing gap in the toy group)
In the order- group above, consider the observer that outputs 1 precisely when the third element is the identity. In the real experiment, exactly when modulo . This happens with probability . In the random experiment, with probability . The advantage of this observer is therefore . This simple test already distinguishes the distributions in the tiny group; it does not contradict asymptotic DDH when the analogous gap is negligible in the security parameter; for example, this holds when for security parameter . An efficient way to see this event is to compare the received element with the group identity.
If instead both exponents are sampled uniformly from the nonzero residues, their joint distribution is the original uniform distribution conditioned on and . The probability of the excluded event is . Consequently, for either real or random experiment, conditioning changes the probability of any fixed observer event by at most ; a triangle inequality bounds the change in its distinguishing advantage by at most . This is a conservative bound, but makes the changed hypothesis explicit. It does not justify accepting the identity as an adversarial public input.
Counterexample mode
Without prime order the shared element leaks a bit
Claim: DDH may be assumed in any cyclic group, such as the full multiplicative group modulo a prime . Modulo , the element has order . By Euler's criterion, exactly when is a square, and is a square exactly when is even. So is a square exactly when or is. The observer that outputs 1 when the third element obeys this rule has and , an advantage of for every such . For example give , , , none of them squares. The repair is the prime order in the definition: in the order- subgroup every element is a square, so this test learns nothing.
An active attacker can replace both messages
Suppose an attacker Eve can intercept and replace public messages. Alice sends and Bob sends , but Eve chooses nonzero , sends to Alice in place of , and sends to Bob in place of . Alice computes ; Eve can compute that from the intercepted and her . Bob computes , which Eve also computes. Alice and Bob have generally obtained different keys, each shared with Eve. If subsequent communication is encrypted without an effective authentication mechanism, Eve can decrypt on one side and re-encrypt on the other, subject to the properties of that encryption.
Counterexample mode
Small-group substitution
Use the preceding modulo- exchange. Eve sends to both sides. Alice obtains and Bob obtains modulo . Eve independently obtains and . Both substituted elements are valid nonidentity members of : checking subgroup membership alone cannot authenticate their sender.
To stop substitution, the parties need an authenticated protocol: for example, a verified signature over a context-bound transcript that includes both identities and public values, together with a trusted binding between the verification key and the intended peer. A signature with an unauthenticated public key merely moves the substitution problem. Protocol design must also specify roles, encodings, key confirmation where needed, and how failures are handled; these notes do not establish a complete authenticated key-exchange proof.
Group and public-value checks
A public element outside the intended subgroup may leak information through the response in protocols that use an unchecked shared element. For instance, in the full multiplicative group modulo , the element has order two. If the implementation represents by its integer in and computes , the result reveals that integer’s parity whenever the attacker can recognize it. Parity is not intrinsic to a residue modulo odd ; the representative matters when the input is outside . This is a small-subgroup attack illustration, not an attack on the passive DDH experiment above, whose inputs are sampled in .
For the prime-order subgroup in the example, a residue is in exactly when . A practical protocol must also define the field-element encoding, reject malformed or prohibited values, and use parameters and checks appropriate to its actual group. These checks protect the group assumptions; they do not prove the identity of the sender.
Checking an input by hand
Worked example 10.2.8
(Valid subgroup value versus an order-two value)
For and , let a receiver check . Squaring successively gives , , and modulo . Hence . Also , so this value passes both subgroup and nonidentity checks. But passing these checks does not tell the receiver who supplied it: an adversary can send too.
Now consider . Since is odd, , so the subgroup check rejects it. If a vulnerable implementation nevertheless exponentiates it, private representatives and produce and respectively. An attacker who can distinguish the resulting behavior learns which parity occurred. This leak depends on a response or later observable behavior revealing information about that computed element; merely sending does not automatically reveal the private exponent.
For a nonzero residue modulo , the test identifies the order- subgroup: by Lagrange's theorem, the subgroup supplies 11 roots, and a nonzero polynomial of degree 11 over the field has at most 11 roots. The test includes , hence a protocol requiring a nonidentity input needs the separate check. The same criterion should not be copied into another group without checking its representation and protocol rules.
Exercises with solutions
Quick check
(In the subgroup above, Alice uses and Bob uses . Find the two public values and their common element.)
Compute and modulo , then one exponentiation.
Solution · Answer
, , and ; also .
Quick check
(A receiver accepts . What shared element results for any private exponent? Why is this different from an authenticated exchange?)
Raise to any power.
Solution · Answer
, which is public. The value carries no proof of the sender's identity, and a known shared element cannot provide a secret key.
Quick check
(Explain why an always-correct CDH solver gives a DDH distinguisher, and calculate its distinguishing gap for independent uniform in a group of order .)
Compare the third component with the solver’s output.
Solution
Compute with the solver and output “real” exactly when the third component equals . Assuming an always-correct solver, the output probability is for a real tuple and for a random tuple, giving gap . An imperfect solver requires its own success analysis.
Quick check
(In the attack above, why can Eve compute without knowing ? Does replacing only Bob's message necessarily let Eve learn Bob's key as well?)
Write and as powers of .
Solution
Exponentiation of the public by the known is enough: . If only the message to Alice is replaced, Bob still computes from Alice's genuine value, so Eve has no general method from this substitution alone to obtain Bob's key.
Quick check
(Show that fails the subgroup test modulo , and explain what that test cannot establish.)
Use and the parity of .
Solution · Answer
, so . The test rules out this value from ; even a passing value might have been sent by an attacker rather than the intended peer.
Quick check
(In the toy group, evaluate the real and random identity-test probabilities if the exponent distribution is uniform on . Why does the answer show that the two distributions are not identical?)
Reuse the identity-test computation.
Solution · Answer
The probabilities are and , respectively. They differ by , so the two distributions are not identical; computational indistinguishability is an asymptotic claim, not equality.
Quick check
(Verify that passes the subgroup test, and explain why it still does not authenticate a peer.)
Use repeated squaring.
Solution · Answer
As above, , and . Anyone can send this valid value, so membership is not evidence of identity.