Attacks on Integer-RLWE

摘要

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.