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[7]=2 \cdot e_B \cdot s_B=2 \cdot 2=4$.

Now, calculating $sk_B[n-1]=sk_B[7]=\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 1


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$.

  • 2
    $\begingroup$ Please prefer editing your question rather than answering your own question. $\endgroup$
    – Bissi
    Jun 20, 2019 at 14:26
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 25, 2019 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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