Welcome to the resource topic for 2016/351
Title:
How (Not) to Instantiate Ring-LWE
Authors: Chris Peikert
Abstract:The \emph{learning with errors over rings} (Ring-LWE) problem—or more accurately, family of problems—has emerged as a promising foundation for cryptography due to its practical efficiency, conjectured quantum resistance, and provable \emph{worst-case hardness}: breaking certain instantiations of Ring-LWE is at least as hard as quantumly approximating the Shortest Vector Problem on \emph{any} ideal lattice in the ring. Despite this hardness guarantee, several recent works have shown that certain instantiations of Ring-LWE can be broken by relatively simple attacks. While the affected instantiations are not supported by worst-case hardness theorems (and were not ever proposed for cryptographic purposes), this state of affairs raises natural questions about what other instantiations might be vulnerable, and in particular whether certain classes of rings are inherently unsafe for Ring-LWE. This work comprehensively reviews the known attacks on Ring-LWE and vulnerable instantiations. We give a new, unified exposition which reveals an elementary geometric reason why the attacks work, and provide rigorous analysis to explain certain phenomena that were previously only exhibited by experiments. In all cases, the insecurity of an instantiation is due to the fact that the error distribution is insufficiently well spread'' relative to the ring. In particular, the insecure instantiations use the so-called \emph{non-dual} form of Ring-LWE, together with \emph{spherical} error distributions that are much narrower and of a very different shape than the ones supported by hardness proofs. On the positive side, we show that any Ring-LWE instantiation which satisfies (or only almost satisfies) the hypotheses of the worst-case hardness of search’’ theorem is \emph{provably immune} to broad generalizations of the above-described attacks: the running time divided by advantage is at least exponential in the degree of the ring. This holds for the ring of integers in \emph{any} number field, so the rings themselves are not the source of insecurity in the vulnerable instantiations. Moreover, the hypotheses of the worst-case hardness theorem are \emph{nearly minimal} ones which provide these immunity guarantees.
ePrint: https://eprint.iacr.org/2016/351
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .