Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Approximate Short Vectors in Ideal Lattices of \(\mathbb {Q}(\zeta _{p^e})\) with Precomputation of \({\text {Cl}}(\mathcal {O}_K)\)
verfasst von : Jean-François Biasse
Erschienen in: Selected Areas in Cryptography – SAC 2017
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let a, b be constants such that \(b\le 7a - 2\) and \(\frac{2}{5}< a < \frac{1}{2}\). We present a classical heuristic PIP resolution method that finds a generator of any input \(\mathfrak {I}\) such that \(\mathcal {N}(\mathfrak {I})\le 2^{n^b}\) in time \(2^{n^{a + o(1)}}\) given a one time classical precomputation of cost and size \(2^{n^{2-3a+o(1)}}\).
We also present a quantum variant of this PIP algorithm with precomputation. Let \(1/3< a < 1/2\). With a quantum coprocessor running Shor’s algorithm, our algorithm solves the \(\gamma \)-ideal-SVP for \(\gamma = 2^{n^{1/2+o(1)}}\) in time \(2^{n^{a + o(1)}}\) using \(\tilde{O}(n^{2-a})\) qubits and a one time classical precomputation on \(\mathbb {Q}(\zeta _{p^e})\) of cost \(2^{n^{2-3a+o(1)}}\). This is a superpolynomial improvement over the best classical method relying on the BKZ reduction, and it uses asymptotically fewer qubit than the quantum polynomial time method relying on the PIP algorithm of [BS16] which requires \(\varOmega (n^3)\) qubits.