TY - GEN
T1 - Recovering short generators of principal ideals in cyclotomic rings
AU - Cramer, Ronald
AU - Ducas, L.
AU - Peikert, Chris
AU - Regev, Oded
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - A handful of recent cryptographic proposals rely on the conjectured hardness of the following problem in the ring of integers of a cyclotomic number field: given a basis of a principal ideal that is guaranteed to have a “rather short” generator, find such a generator. Recently, Bernstein and Campbell-Groves-Shepherd sketched potential attacks against this problem; most notably, the latter authors claimed a polynomial-time quantum algorithm. (Alternatively, replacing the quantum component with an algorithm of Biasse and Fieker would yield a classical subexponential-time algorithm.) A key claim of Campbell et al. is that one step of their algorithm—namely, decoding the log-unit lattice of the ring to recover a short generator from an arbitrary one—is classically efficient (whereas the standard approach on general lattices takes exponential time). However, very few convincing details were provided to substantiate this claim. In this work, we clarify the situation by giving a rigorous proof that the log-unit lattice is indeed efficiently decodable, for any cyclotomic of prime-power index. Combining this with the quantum algorithm from a recent work of Biasse and Song confirms the main claim of Campbell et al. Our proof consists of two main technical contributions: the first is a geometrical analysis, using tools from analytic number theory, of the standard generators of the group of cyclotomic units. The second shows that for a wide class of typical distributions of the short generator, a standard lattice-decoding algorithm can recover it, given any generator. By extending our geometrical analysis, as a second main contribution we obtain an efficient algorithm that, given any generator of a principal ideal (in a prime-power cyclotomic), finds a 2Õ(√ n)-approximate shortest vector in the ideal. Combining this with the result of Biasse and Song yields a quantum polynomial-time algorithm for the 2Õ(√ n)-approximate Shortest Vector Problem on principal ideal lattices.
AB - A handful of recent cryptographic proposals rely on the conjectured hardness of the following problem in the ring of integers of a cyclotomic number field: given a basis of a principal ideal that is guaranteed to have a “rather short” generator, find such a generator. Recently, Bernstein and Campbell-Groves-Shepherd sketched potential attacks against this problem; most notably, the latter authors claimed a polynomial-time quantum algorithm. (Alternatively, replacing the quantum component with an algorithm of Biasse and Fieker would yield a classical subexponential-time algorithm.) A key claim of Campbell et al. is that one step of their algorithm—namely, decoding the log-unit lattice of the ring to recover a short generator from an arbitrary one—is classically efficient (whereas the standard approach on general lattices takes exponential time). However, very few convincing details were provided to substantiate this claim. In this work, we clarify the situation by giving a rigorous proof that the log-unit lattice is indeed efficiently decodable, for any cyclotomic of prime-power index. Combining this with the quantum algorithm from a recent work of Biasse and Song confirms the main claim of Campbell et al. Our proof consists of two main technical contributions: the first is a geometrical analysis, using tools from analytic number theory, of the standard generators of the group of cyclotomic units. The second shows that for a wide class of typical distributions of the short generator, a standard lattice-decoding algorithm can recover it, given any generator. By extending our geometrical analysis, as a second main contribution we obtain an efficient algorithm that, given any generator of a principal ideal (in a prime-power cyclotomic), finds a 2Õ(√ n)-approximate shortest vector in the ideal. Combining this with the result of Biasse and Song yields a quantum polynomial-time algorithm for the 2Õ(√ n)-approximate Shortest Vector Problem on principal ideal lattices.
UR - http://www.scopus.com/inward/record.url?scp=84964949415&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84964949415&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49896-5_20
DO - 10.1007/978-3-662-49896-5_20
M3 - Conference contribution
AN - SCOPUS:84964949415
SN - 9783662498958
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 559
EP - 585
BT - Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Fischlin, Marc
A2 - Coron, Jean-Sebastien
PB - Springer Verlag
T2 - 35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016
Y2 - 8 May 2016 through 12 May 2016
ER -