Trying to implement ring-LWE KE to understand the concept

Question

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.

Answer 1

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.