On Wikipedia, a lot of the subjects that are said to be different key exchange methods are often just protocols that incorporate the Diffie-Hellman algorithm into them. The only other key exchange algorithm I know of besides DH is Algebraic Eraser, of which I don't know much about. Are there any others? And I don't mean key exchange schemes based on symmetric key primitives.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I think there is some super singular elliptic curve isomorphism thingy. No idea how practical it is. $\endgroup$– CodesInChaosCommented Apr 2, 2016 at 11:13
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
Using lattices/ring-LWE, there is Lattice Cryptography for the Internet (by me), which inherits from Ring-LWE encryption, and has been implemented by Bos et al. with further improvements by Alkim et al.
The underlying mechanism is conceptually DH-like, but uses completely different mathematics. We start with a uniformly random $a \in R_q = R/qR$, which can be chosen by one of the parties or by a trusted third party. Here $R$ is an appropriate choice of ring, e.g., $R=\mathbb{Z}[X]/(X^n+1)$ for power-of-two $n$ (in the few hundreds, for current security estimates).
The basic protocol works as follows (oversimplifying a bit): to establish a key, the first party chooses a "short" random $e \in R$, and announces $E \approx e \cdot a \in R_q$, where the approximation hides some short random error. Similarly, the second party chooses a short $f \in R$, and announces $F \approx a \cdot f \in R_q$. The first party can then compute $e \cdot F \approx e \cdot a \cdot f \in R_q$, and the second party can compute $E \cdot f \approx e \cdot a \cdot f \in R_q$. The parties then use some kind of "reconciliation" mechanism to extract a common secret key from their shared "noisy" versions of $e \cdot a \cdot f$.
The above mechanism can be proved secure against passive eavesdroppers assuming the hardness of the corresponding Ring-LWE problem (which itself can be proved quantumly as hard as worst-case problems on ideal lattices, for appropriate parameters). Of course, in reality we need authenticated key exchange and other properties; these can be obtained using additional techniques that originated in the DH setting (see the first link for details).
answered Apr 2, 2016 at 13:50
-
$\begingroup$ My layman's question: If an adversary is capable to tap exactly all bits that are being transferred between the communication partners, wouldn't he be able to employ the same "reconciliation" mechanism to obtain the common secret key? $\endgroup$ Commented Apr 3, 2016 at 11:53
-
$\begingroup$ No, because the eavesdropper sees only $a, E,F$. There's no apparent way to get anything close to $e \cdot a \cdot f$ from this: e.g., $E \cdot F$ doesn't work (just expand it out). In fact, one can prove that the reconciled key is indistinguishable from uniform to the eavesdropper, under the Ring-LWE assumption. $\endgroup$ Commented Apr 3, 2016 at 12:12
-
1$\begingroup$ I don't understand the math behind lattices. Diffie-Hellman is very simple, requiring only a few operations learned by me as early as sixth grade. $\endgroup$– MelabCommented Apr 6, 2016 at 9:06
-
$\begingroup$ If you know how to add and multiply polynomials, you can understand this KE protocol. $\endgroup$ Commented Apr 6, 2016 at 11:28
-
$\begingroup$ @ChrisPeikert That I do know how to do, but I'm guessing that this requires a more exotic form of them. Polynomials, for one thing, are not numbers, so there much be some sort of novel mapping between integers and polynomials in this system. What are the key sizes necessary for strength levels of 128, 192, and 256 bits? $\endgroup$– MelabCommented Apr 7, 2016 at 4:35
