The Evolution of Diffie-Hellman Hard Problems

The Evolution of Diffie-Hellman Hard Problems

So who has made the greatest contribution to Cybersecurity? Well, possibly it is Whitfield Diffie and Martin Hellman and who, in 1976, published their classic paper [here]:

Since then most secure connections we make over the Internet involves some form of their original method, and where Bob and Alice can determine the same encryption key, without anyone else finding it out. It all started with discrete logs, and where the Diffie-Hellman method defined:

Alice generates a, Bob generates b.

Alice passes g^a, and Bob passes g^b. They then calculated the shared secret of g^{ab}.

The hard problem is:

Given g, and g^x, it is difficult to find x. [here]

We then advanced to ECDH (Elliptic Curve Diffie Hellman), and where we have a base point (P).

Alice generates a, Bob generates b.

Alice passes aP and Bob passes bP. They then calculate the shared secret of abP. The hard problem is:

Given P, and xP, it is difficult to find x. [here]

Both discrete log and elliptic curve methods can be cracked with quantum computers, so we need to rethink.

With R-LWE (Ring Learning With Errors), we have a ring (R) and a prime number q. Alice has a polynomial (A) and a secret (a) with an error polynomial (eA):

bA=A×a+eA

Bob has a polynomial (A) and a secret polynomial (sB) with an error polynomial (eB):

bB=A×b+eB

Alice passes bA, and Bob pass bB, Alice calculates sA(bB) and Bob calculates sB(bA).

Given polynomial a, and xa+e, it is difficult to find x. [here]

With LWE, we uses matrices. We have a matrix A. Alice creates a secret (a) and calculates aA, and add an error matrix:

sA = aA + eA

Bob creates a secret (b) and calculates A, and add an error matrix:

sB = bA + eB

Bob and Alice exchange values, and Alice multiplies with her secret, and Bob does the same. The result is:

Shared = abA

Given a matrix A, and xA+e, it is difficult to find x. [here]

With SIDH (Supersingular Isogenies Diffie-Hellman), we create elliptic curves which have isogenies (and where one curve can map to another curve). Alice takes a random walk from a curve E and produces PHIa(E), and Bob does a random walk and produces PHIb(E). They share their curves, and follow the same paths, and will end up with the same curve, which they can use for the shared key.

Given E and PHIa(E), it is difficult to find PHI [here].

And there you go. Since 1976, the Diffie-Hellman method has evolved, and is now providing new solutions for a post-quantum world.