Paper 2016/239

Provably Weak Instances of Ring-LWE Revisited

Wouter Castryck, Ilia Iliashenko, and Frederik Vercauteren

Abstract

In CRYPTO 2015, Elias, Lauter, Ozman and Stange described an attack on the non-dual decision version of the ring learning with errors problem (RLWE) for two special families of defining polynomials, whose construction depends on the modulus q that is being used. For particularly chosen error parameters, they managed to solve non-dual decision RLWE given 20 samples, with a success rate ranging from 10% to 80%. In this paper we show how to solve the search version for the same families and error parameters, using only 7 samples with a success rate of 100%. Moreover our attack works for every modulus q instead of the q that was used to construct the defining polynomial. The attack is based on the observation that the RLWE error distribution for these families of polynomials is very skewed in the directions of the polynomial basis. For the parameters chosen by Elias et al. the smallest errors are negligible and simple linear algebra suffices to recover the secret. But enlarging the error paremeters makes the largest errors wrap around, thereby turning the RLWE problem unsuitable for cryptographic applications. These observations also apply to dual RLWE, but do not contradict the seminal work by Lyubashevsky, Peikert and Regev.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
wouter castryck @ gmail com
History
2016-03-04: received
Short URL
https://ia.cr/2016/239
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/239,
      author = {Wouter Castryck and Ilia Iliashenko and Frederik Vercauteren},
      title = {Provably Weak Instances of Ring-LWE Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2016/239},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/239}},
      url = {https://eprint.iacr.org/2016/239}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.