Converting NewHope/LWE key exchange to a Diffe-Hellman-like algorithm

Question

By a “Diffe-Hellman-like” algorithm, I mean one that has the same API as Curve25519, etc (disregarding trivial differences such as the size of parameters): a function

$$F: (P_\text{other}, S_\text{self}) \rightarrow \text{Shared secret}$$

where $S_\text{self}$ can be used arbitrarily many times with different values of $P_\text{other}$.

Answer 1

It has been folklore (since at least 2010) that you can do what you propose, but less efficiently than the "key transport" method of any Ring-LWE based encryption scheme or KEM.

So here is what you can do: there is a public polynomial $a\in Z_q[X]/(X^n+1)$ that is shared by everyone. It needs to be uniformly random, so it can be set to XOF(1), where XOF is something like SHAKE. This way, it's "random" and we're pretty sure there are no planted trap-doors in $a$.

Then person $i$ selects two polynomials $s_i,e_i\in Z_q[X]/(X^n+1)$ with small coefficients and publishes his key $b_i=as_i+e_i$. Now if party $i$ and $j$ want to share a key, party $i$ computes $s_ib_j = as_is_j+s_ie_j$ and party $j$ computes $s_jb_i= as_is_j+s_je_i$. Since $s_ie_j$ and $s_je_i$ are products of polynomials with small coefficients, the coefficients of the products themselves are bounded (say by $\beta$).

So what we would really like is that the coefficients of $s_ie_j$ do not affect the higher order bits of $as_is_j$. This could happen if $q$ is much larger than $\beta$. Basically, if $q=2^k \beta$, then the probability of the higher order bit not being affected is around $1-2^{-k}$. So by setting $q$ large enough, the way to retrieve a shared key would be to compute HighOrderBits$(s_ib_j)$.

So why isn't this done? Because you would need to set $q$ quite large and the underlying hard lattice problem becomes easier the larger the gap between $q$ and the coefficients of $s_i,e_i$ are. So you would have to increase the dimension of your ring to compensate. It is possible to set such parameters, but I would estimate that achieving similar security as regular Ring-LWE encryption / key exchange schemes would result in keys that are around 20 - 40 times larger than in Ring-LWE based schemes. So something around 20KB - 40KB could be expected.