1
$\begingroup$

The answer to this question might be trivial or very short, but I would like to ask it anyway. In both BCNS and NewHope Ring-LWE key-exchange protocol one party adds a secondary error to their calculated key. What is the reason? Is it just to increase entropy? Or is there another a reason behind it?

BCNS protocol (page 8): notice that $e''$ BCNS protocol

NewHope protocol (page 5): notice $e''$ NewHope protocol

Improve this question
$\endgroup$
2
  • $\begingroup$ Could you please add links to the BCNS and NewHope papers in your question? Also, I'm not sure how the extraction of $c$ (or $r$) from $v$ works, but I imagine that if $v = bs'$ without any noise, then sending $c$ (or $r$) to Alice leaks information about $s'$ to Alice (and to any observer of the channel, who can see $b$). $\endgroup$
    – TMM
    Feb 20, 2017 at 0:35
  • $\begingroup$ @TMM my question is why we need to add $e''$. If there is no $e'$ then it is trivial that security would be compromised. $\endgroup$
    – Node.JS
    Feb 20, 2017 at 3:24

1 Answer 1

Reset to default
1
$\begingroup$

If $e''$ isn't there, then $v=bs'$ in both protocols, which means it would be easy to recover $s'$ given $v$ and $b$. Since $b$ is sent in the clear over the channel, and a (randomized) function of $v$ appears in the clear as $c$ (or $r$), without using $e''$ to hide $s'$, information about $s'$ would likely be leaked both to Alice and to any eavesdropper of the channel. Even if it wouldn't immediately leak all of $s'$, any leakage is clearly bad.

Somewhat related to this is the history of lattice signatures, which initially leaked "just a little bit" about the secret key, after which full breaks of these schemes were found. These schemes were only truly fixed once a way was found to make the output distribution completely independent of the secret key, so that nothing is leaked. In this case $e''$ is used to make sure that $v = bs' + e''$ is indistinguishable from random, i.e. the distribution of $v$ is independent of $s'$, assuming R-LWE is hard. See also the security proof in the BCNS paper, where Game 1 and Game 2 are assumed to be indistinguishable under the R-LWE assumption.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thank you for the answer. But why Alice does not add some $e''$ as well? $\endgroup$
    – Node.JS
    Feb 20, 2017 at 16:35
  • $\begingroup$ Alice uses $e$ to hide her own secret $s$, just like Bob uses $e'$ to hide his secret $s'$. To agree on the key (both parties have different noise on the shared key, which they do not wish to disclose) Bob has to send this extra key reconciliation message, for which he again hides his secret $s'$ with fresh random noise $e''$. $\endgroup$
    – TMM
    Feb 20, 2017 at 17:22

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.