# Complete Attack on RLWE Key Exchange with reused keys, without signal leakage

I am studying a research paper "Complete Attack on RLWE Key Exchange with reused keys, without signal leakage" . On page number 21 to 28, there is toy example explaining the scheme.

I am unable to get the desired value of $$\mathcal B$$ as described in column 3 of table 1 on page number 22. My calculation is as follows:

$$s_B=(2,3,0,0,-5,2,3,1), \qquad e_B=(0,0,0,0,0,0,0,1)$$

$$e_B \cdot s_B=(x^7)\cdot(2+3x-5x^4+2x^5+3x^6+x^7)$$

$$e_B \cdot s_B=-3+5x^3-2x^4-3x^5-x^6+2x^7$$

So, coefficient of $$k_B[n-1]=k_B=2 \cdot e_B \cdot s_B=2 \cdot 2=4$$.

Now, calculating $$sk_B[n-1]=sk_B=\mathsf{Mod}_2(k_B[n-1],w_B[n-1])$$

$$=\mathsf{Mod}_2(4,1)= \left( 4+1 \cdot \dfrac{257-1}{2} \mod 257 \right) \mod 2=\left(4+128 \mod \ 257 \right) \mod 2=0$$

Thus, $$sk_A=sk_B$$ and value of oracle $$\mathcal B$$ must be $$1$$ (as keys get matched) but it is given $$0$$ (in column 3 of table 1 on page number 22).

## 1 Answer

There is a condition that is not considered, that is, the value after modulo 257 should be in $$\mathbb Z_q$$. When $$q = 257, \mathbb Z_q = \{ -128, ... , 128 \}$$, so, $$(4+128)\mod 257$$ should be $$-125$$ rather than $$132$$ . And $$-125 \mod 2 = 1$$. Thus, $$sk_a \neq sk_b$$ and the output of oracle $$\mathcal B$$ is $$0$$.

• Please prefer editing your question rather than answering your own question. – Bissi Jun 20 '19 at 14:26
• Why so? If he found the answer to his question, posting the answer for everyone to see it seems much more appropriate than editing his own question to include the answer there. – Geoffroy Couteau Jun 25 '19 at 15:04