8
$\begingroup$

This is regarding the number post-quantum key exchange protocol New-Hope (https://eprint.iacr.org/2015/1092.pdf). In the paper, we can see that the number of samples generated by the protocol is $2n$ where $n$ is $1024$, the rank of matrix $a$. Once in server side $b\leftarrow as+e$ and once in client side $u\leftarrow as'+e'$. But the authors in the paper (page 18 appendix B) says that the number of samples in each instantiation of the protocol is $5n$.

I can't understand why. Also, as far as I know the LWE samples are related when the matrix $a$ and the secret $s$ remains same. But, in the protocol the secret changes $s$ and $s'$.

Can someone please explain this? Thank you in advance.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

They're actually sampling $5n$ elements from $\Psi_{16}$. Perhaps Protocol 2 on page 5 shows this most clearly, where $\textbf{s}, \textbf{e} \stackrel{\$}{\leftarrow} \Psi_{16}^n$ and $\textbf{s}', \textbf{e}', \textbf{e}'' \stackrel{\$}{\leftarrow} \Psi_{16}^n$ are sampled (on line 3 on Alice' side, and line 1 on Bob's).

This probably also answers part of your follow-up question, but for completeness: the values $\textbf{s}$ and $\textbf{s}'$ are sampled independently by Alice and Bob, and are thus not at all related. The final shared secret is neither $\textbf{s}$ nor $\textbf{s}'$, but the reconciled $v$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh, I see. I mixed up LWE samples and noise samples. I get it now. $\endgroup$
    – Rick
    Commented Mar 30, 2017 at 14:57

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.