Advanced search
1 file | 452.73 KB Add to list

Provably weak instances of ring-LWE revisited

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

Downloads

  • 239.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 452.73 KB

Citation

Please use this url to cite or link to this publication:

MLA
Castryck, Wouter, et al. “Provably Weak Instances of Ring-LWE Revisited.” Lecture Notes in Computer Science, edited by Marc Fischlin and Jean-Sébastien Coron, vol. 9665, Springer, 2016, pp. 147–67.
APA
Castryck, W., Iliashenko, I., & Vercauteren, F. (2016). Provably weak instances of ring-LWE revisited. In M. Fischlin & J.-S. Coron (Eds.), Lecture Notes in Computer Science (Vol. 9665, pp. 147–167). Berlin, Germany: Springer.
Chicago author-date
Castryck, Wouter, Ilia Iliashenko, and Frederik Vercauteren. 2016. “Provably Weak Instances of Ring-LWE Revisited.” In Lecture Notes in Computer Science, edited by Marc Fischlin and Jean-Sébastien Coron, 9665:147–67. Berlin, Germany: Springer.
Chicago author-date (all authors)
Castryck, Wouter, Ilia Iliashenko, and Frederik Vercauteren. 2016. “Provably Weak Instances of Ring-LWE Revisited.” In Lecture Notes in Computer Science, ed by. Marc Fischlin and Jean-Sébastien Coron, 9665:147–167. Berlin, Germany: Springer.
Vancouver
1.
Castryck W, Iliashenko I, Vercauteren F. Provably weak instances of ring-LWE revisited. In: Fischlin M, Coron J-S, editors. Lecture Notes in Computer Science. Berlin, Germany: Springer; 2016. p. 147–67.
IEEE
[1]
W. Castryck, I. Iliashenko, and F. Vercauteren, “Provably weak instances of ring-LWE revisited,” in Lecture Notes in Computer Science, Vienna, Austria, 2016, vol. 9665, pp. 147–167.
@inproceedings{7162559,
  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.},
  author       = {Castryck, Wouter and Iliashenko, Ilia and Vercauteren, Frederik},
  booktitle    = {Lecture Notes in Computer Science},
  editor       = {Fischlin, Marc and Coron, Jean-Sébastien},
  isbn         = {9783662498903},
  issn         = {0302-9743},
  language     = {eng},
  location     = {Vienna, Austria},
  pages        = {147--167},
  publisher    = {Springer},
  title        = {Provably weak instances of ring-LWE revisited},
  url          = {http://dx.doi.org/10.1007/978-3-662-49890-3_6},
  volume       = {9665},
  year         = {2016},
}

Altmetric
View in Altmetric