Welcome to the resource topic for 2020/1007
Title:
Attacks on Integer-RLWE
Authors: Alessandro Budroni, Benjamin Chetioui, 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.
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 .