Diffie–Hellman Key Agreement: Key-Indistinguishability from DDH #
The Diffie–Hellman key exchange over an abstract prime-order group, and the proof that its key-indistinguishability advantage equals the Decisional Diffie–Hellman advantage of an explicit reduction. Following Rosulek, The Joy of Cryptography (Diffie–Hellman).
We work in the group P.G₁ of a PairingGroup P — an abstract cyclic group of
prime order P.p with generator g₁ and ZMod P.p-exponentiation x ^ᵍ a. No
concrete curve is used. The DH group structure (elgamalDDH, elgamalEcdh) is
shared with CatCryptCore.Examples.ElGamal.
The protocol #
- Alice samples
a ← ZMod pand publishesg₁ ^ᵍ a. - Bob samples
b ← ZMod pand publishesg₁ ^ᵍ b. - Both parties compute the shared key
k = g₁ ^ᵍ (a·b)— Alice as(g₁^b)^a, Bob as(g₁^a)^b.
The public transcript is the pair (g₁ ^ᵍ a, g₁ ^ᵍ b).
Security (Rosulek) #
Key indistinguishability: to an eavesdropper who sees the transcript, the real
shared key g₁ ^ᵍ (a·b) is indistinguishable from a uniform group element. The
real experiment KA_Game_Real hands the distinguisher (transcript, g^{ab}); the
ideal experiment KA_Game_Ideal hands it (transcript, uniform). These two
distributions are, verbatim, the real and ideal DDH challenge distributions — so
DH key indistinguishability is DDH.
The reduction #
dhReduction D repackages a key-indistinguishability distinguisher
D : (G₁ × G₁) → G₁ → SPComp Bool into a DDH adversary
fun g_a g_b z => D (g_a, g_b) z: the DDH triple (g^a, g^b, z) is presented as a
transcript (g^a, g^b) together with a candidate key z. Because the DDH group's
keygen samples s and publishes g^s, and elgamalEcdh (g^a) (g^b) = g^{ab}
(via the discrete-log bijection), the DDH real/ideal games unfold to exactly the
DH key-agreement real/ideal experiments.
Main results #
KA_Game_Real/KA_Game_Ideal/KA_Advantage— the DH key-agreement experiments and the key-indistinguishability advantage.dhReduction— the (transcript-repackaging) DDH adversary.ka_real_eq/ka_ideal_eq— each key-agreement experiment equals the corresponding DDH game under the reduction (exact distribution equalities).ka_advantage_eq_ddh— the headline: the DH key-indistinguishability advantage equals the DDH advantage of the reduction,KA_Advantage P D = DDH_Advantage (elgamalDDH P) (dhReduction D).ka_secure_under_ddh— DH key agreement is secure under DDH: if every DDH adversary has advantage at mostε, so does every key distinguisher.
References #
- [Rosulek, The Joy of Cryptography, §14–15 (Diffie–Hellman / DDH)]
- [Boneh & Shoup, A Graduate Course in Applied Cryptography, §11.4, Def. 11.2]
CatCryptCore.Crypto.Assumptions.DDHfor the DDH games and advantage.CatCryptCore.Examples.ElGamalfor the shared DH group (elgamalDDH).CatCryptCore.Crypto.PairingGroupfor the abstract prime-order group.
The key-agreement experiments #
A key-indistinguishability distinguisher: given the public transcript
(g₁ ^ᵍ a, g₁ ^ᵍ b) and a candidate shared key, output a guess bit.
Equations
Instances For
Real DH key-agreement experiment: Alice publishes g₁ ^ᵍ a, Bob publishes
g₁ ^ᵍ b, and the shared key is the true DH secret g₁ ^ᵍ (a·b). The
distinguisher receives the transcript together with the real key.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Ideal DH key-agreement experiment: same transcript (g₁ ^ᵍ a, g₁ ^ᵍ b),
but the key is a fresh uniform group element, independent of the transcript.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Key-indistinguishability advantage: the ability to tell the real shared key from a uniform one, given the transcript.
Equations
Instances For
The reduction #
The reduction to DDH: present the DDH triple (g^a, g^b, z) as a transcript
(g^a, g^b) together with a candidate shared key z, and run the
key-indistinguishability distinguisher D.
Equations
- CatCrypt.Examples.DiffieHellman.dhReduction D g_a g_b z = D (g_a, g_b) z
Instances For
Game equalities #
The real key-agreement experiment equals the real DDH game under the reduction:
the DDH group's keygen samples s and publishes g^s, and
elgamalEcdh (g^a) (g^b) = g^{ab} is exactly the true DH shared key.
The ideal key-agreement experiment equals the ideal DDH game under the reduction: both replace the shared key with a fresh uniform group element.
Key indistinguishability equals DDH #
DH key indistinguishability is DDH. For every distinguisher D, the DH
key-agreement key-indistinguishability advantage equals the DDH advantage of the
reduction:
KA_Advantage P D = DDH_Advantage (elgamalDDH P) (dhReduction D).
This is an exact equality, not merely a bound: the two key-agreement experiments
are, verbatim, the real and ideal DDH challenge distributions (ka_real_eq,
ka_ideal_eq). Rosulek, The Joy of Cryptography (Diffie–Hellman).
DH key agreement is secure under DDH. If every DDH adversary over the group
has advantage at most ε, then every key-indistinguishability distinguisher
against the DH key exchange has advantage at most ε.