Attacks on Integer-RLWE

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=2k . 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=233 , we reduce the estimated complexity of the attack from 2288 to 2164 . We also present reproducible experiments confirming our theoretical results.