7
$\begingroup$

Today, after reading so much about ring-LWE key exchange, I decided to implement it in java to see if it works. Not a real world implementation, just to see if math works out. My assumption was that writing a code would be simple given some sort of Polynomial ring. My assumption turned out to be wrong. I searched internet looking for basic uni-variate polynomial ring library and I found this. It looked simple and had some jUnit test already that code was passing. I copied the parameters from here. In short, $\mathbb{Z_{2^{23}-1}} / (x^{1024} + 1)$.

I followed Regev's basic reconciliation method and ran the code. Even if there is no error, the exchanged keys did not match. Obviously, something is wrong and I am certain it is from my code not the Polynomial ring library. Maybe I did not understand some fundamentals of ring-LWE. I attached the code here:

This is the link for GitHub repository. Any help would be appreciated. I don't know what I am doing wrong.

Math: dimension = 4 (arbitrary)

$A, S, S' = [rx^3 + rx^2 + rx + r,\\ rx^3 + rx^2 + rx + r,\\ rx^3 + rx^2 + rx + r,\\ rx^3 + rx^2 + rx + r]$

s.t. $r \in \mathbb{Z_{q}}$ (randomly generate)

$B = AS + error$, $B' = AS' + error$

$Shared key = SB' = S'B \to$ I did not use any error ($error =0$) but still shared key does not match.

Pseudo-code:

dimension = 8 # arbitrary
modulus = 65537
R = PolynomialRing(GF(modulus), "X")
S = R.quotient(X^1024 + 1, "x")

A = generate_matrix(dimension, modulus)
S = generate_matrix(dimension, modulus)
S_ = generate_matrix(dimension, modulus)

B = A.transpose()*S
B_ = A.transpose()*S_

alice = S*B_
bob = S_*B

print alice == bob  # returns false

Update: I tried to write the code in sage (without any error) and still something is wrong. I am now sure my math is wrong. This is the link for sage code.

$\endgroup$
6
+100
$\begingroup$

It seems to me that the problem lies in your setup of the vector/matrix multiplication.

What you have now: $a, s, s'$ are row vectors of ring elements.

$$ \text{Alice: } sB' = sa^ts'$$ $$ \text{Bob: } s'B = s'a^ts $$

Obviously, matrix multiplication is not commutative, but multiplying the underlying ring elements isn't either, because they're, well, ring elements.

So you need to shuffle and transpose some things.

Let $B = a^ts$, and $B' = s'^ta$.

Now let Alice calculate $B'^t s^t$, and Bob calculate $s'B^t$. If you work it out, this will give Alice and Bob consistent keys.

Proof: I modified your sage script, it returns true now.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.