Paper 2020/1007

Attacks on Integer-RLWE

Alessandro Budroni, Benjamin Chetioui, and Ermes Franch

Abstract

In 2019, Gu Chunsheng introduced Integer-RLWE, a variant of RLWE devoid of some of its efficiency flaws. Most notably, he proposes a setting where $n$ can be an arbitrary positive integer, contrarily to the typical construction $n = 2^k$. In this paper, we analyze the new problem and implement the classical meet-in-the-middle and lattice-based attacks. We then use the peculiarity of the construction of $n$ to build an improved lattice-based attack in cases where $n$ is composite with an odd divisor. For example, for parameters $n = 2000$ and $q = 2^{33}$, we reduce the estimated complexity of the attack from $2^{288}$ to $2^{164}$. We also present reproducible experiments confirming our theoretical results.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. ICICS 2020
Keywords
Post-quantum cryptographyMeet-in-the-middleLattice-based attackI-RLWE
Contact author(s)
alessandro budroni @ uib no
benjamin chetioui @ uib no
ermes franch @ uib no
History
2020-08-22: received
Short URL
https://ia.cr/2020/1007
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1007,
      author = {Alessandro Budroni and Benjamin Chetioui and Ermes Franch},
      title = {Attacks on Integer-RLWE},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1007},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1007}},
      url = {https://eprint.iacr.org/2020/1007}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.