[Resource Topic] 2020/1007: Attacks on Integer-RLWE

Welcome to the resource topic for 2020/1007

Attacks on Integer-RLWE

Authors: Alessandro Budroni, Benjamin Chetioui, Ermes Franch


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.

ePrint: https://eprint.iacr.org/2020/1007

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .