Attacks on Integer-RLWE
Journal article, Peer reviewed
MetadataShow full item record
Original versionLecture Notes in Computer Science (LNCS). 2020, 12282, 528-542 https://doi.org/10.1007/978-3-030-61078-4_30
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.