Cryptology ePrint Archive: Report 2020/1007

Attacks on Integer-RLWE

Alessandro Budroni and 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.

Category / Keywords: public-key cryptography / Post-quantum cryptography, Meet-in-the-middle, Lattice-based attack, I-RLWE

Original Publication (with minor differences): ICICS 2020

Date: received 20 Aug 2020

Contact author: alessandro budroni at uib no, benjamin chetioui@uib no, ermes franch@uib no

Available format(s): PDF | BibTeX Citation

Version: 20200822:215246 (All versions of this report)

Short URL: ia.cr/2020/1007


[ Cryptology ePrint archive ]