Special | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | ALL
Diffie-Hellman key agreement | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
The Diffie-Hellman (D-H) key agreement (often called βkey exchangeβ) protocol is standardised in NIST SP 800-56A [BCR+18]. The protocol originated in the seminal 1976 paper by Whitfield Diffie and Martin Hellman [DH76], both recipients of the 2016 Turing Award (their contribution took 40 years to be recognised). Protocol between π© Alice and π§ Bob [KL21, CONSTRUCTION 11.2] in Fig. 1:
Successful completion of the protocol results in the session key . A necessary condition for preventing a probabilistic polynomial-time (PPT) eavesdropper from computing the session key is that the computational Diffie-Hellman (CDH) problem is hard: Definition 1: Computational Diffie-Hellman (CDH) problem [Gal12, Definition 20.2.1]
However, the hardness of the CDH problem is not sufficient. Just as indistinguishability plays an essential role in symmetric-key encryption, indistinguishability is key here: if the session key is indistinguishable from an element chosen uniformly at random from , then we have a sufficient condition for preventing a PPT eavesdropper from computing the session key [KL21, pp. 393-394]. The indistinguishability condition is equivalent to the assumption that the decisional Diffie-Hellman (DDH) problem is hard: Definition 2: Decisional Diffie-Hellman (DDH) problem [Gal12, Definition 20.2.3]
The DDH problem is readily reducible to the CDH problem, since any algorithm that solves the CDH can compute and compare it with ; implying the DDH problem is no harder than the CDH problem. In turn, the CDH problem is reducible to the discrete logarithm problem (DLP, see Definition 3), since any algorithm that solves the DLP can compute from , from , and hence ; implying the CDH problem is no harder than the DLP problem. Definition 3: Discrete logarithm problem (DLP) [Gal12, Definition 13.0.1]
In other words, the DDH problem can be reduced to the CDH problem, which in turn can be reduced to the DLP; solving the DLP breaks the D-H key agreement protocol. β There are multiplicative groups for which the DLP is easy, so it is critical that the right groups are used. A safe-prime group is a cyclic subgroup of the Galois field with prime order , where is called a safe prime; this subgroup has elements [BCR+18, Sec. 5.5.1.1]. NIST [BCR+18, Appendix D] refers to RFC 3526 and RFC 7919 for definitions of safe-prime groups. The D-H key agreement protocol is used in the Internet Key Exchange (IKE) protocol, which is currently at version 2 [KHN+14]. References
| ||||||||||||