Hot answers tagged

12

It has been folklore (since at least 2010) that you can do what you propose, but less efficiently than the "key transport" method of any Ring-LWE based encryption scheme or KEM. So here is what you can do: there is a public polynomial $a\in Z_q[X]/(X^n+1)$ that is shared by everyone. It needs to be uniformly random, so it can be set to XOF(1), where XOF is ...


11

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


9

From Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process 3.12 NewHope NewHope is a KEM based on the presumed hardness of the RLWE problem. At its core is Regev’s original idea for public-key encryption from plain LWE but specialized to a power-of-2 cyclotomic ring structure, enabling smaller ciphertext and key ...


8

My name is Zhenfei Zhang. I work for Security Innovation Inc., which acquired NTRU Inc. in 2010. The R-LWE based key exchange [1] uses a public matrix $a$ which may be manipulated. For instance, if $a$ is an NTRU style public key, i.e., $a = g/f$ where $g$ and $f$ are short, then one can break the system by recovering $f$. In particular, the cited paper ...


6

Well, it turns out that a straight-forward implementation of LWE key exchanges is vulnerable to chosen ciphertext attacks, in the case that one side reuses the same private value $a$ multiple times. In this straight-forward implementation, Alice generates a private vector $a$, and sends his key share $a M + \epsilon$. Then, when Bob receives this key share,...


4

Yes the Bernstein attack is applicable but the impact of the attack is reduced because the party generating the parameter is also going to be a legitimate participant of the key exchange. Here is why the attack does indeed apply. Consider a case where Bob and Alice wish to conduct a key exchange using the New Hope Lattice-Based Key Exchange. Bob will be ...


1

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


Only top voted, non community-wiki answers of a minimum length are eligible