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 \etal\xspace 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^{\tilde{O}(\sqrt{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^{\tilde{O}(\sqrt{n})}$-approximate Shortest Vector Problem on principal ideal lattices.
Category / Keywords: public-key cryptography / Ideal Lattices, Cryptanalysis Original Publication (in the same form): IACR-EUROCRYPT-2016 Date: received 6 Apr 2015, last revised 25 Feb 2016 Contact author: ducas at cwi nl Available format(s): PDF | BibTeX Citation Note: Moved appendices. Version: 20160225:160043 (All versions of this report) Short URL: ia.cr/2015/313