Quantum LLL with an Application to Mersenne Number Cryptosystems

Marcel Tiepelt and Alan Szepieniec

Abstract

In this work we analyze the impact of translating the well-known LLL algorithm for lattice reduction into the quantum setting. We present the first (to the best of our knowledge) quantum circuit representation of a lattice reduction algorithm in the form of explicit quantum circuits implementing the textbook LLL algorithm. Our analysis identifies a set of challenges arising from constructing reversible lattice reduction as well as solutions to these challenges. We give a detailed resource estimate with the Toffoli gate count and the number of logical qubits as complexity metrics. As an application of the previous, we attack Mersenne number cryptosystems by Groverizing an attack due to Beunardeau et. al that uses LLL as a subprocedure. While Grover's quantum algorithm promises a quadratic speedup over exhaustive search given access to a oracle that distinguishes solutions from non-solutions, we show that in our case, realizing the oracle comes at the cost of a large number of qubits. When an adversary translates the attack by Beunardeau et al. into the quantum setting, the overhead of the quantum LLL circuit may be as large as $2^{52}$ qubits for the text-book implementation and $2^{33}$ for a floating-point variant.

Available format(s)
Publication info
Published elsewhere. Minor revision.LATINCRYPT 2019, LNCS 11774
DOI
10.1007/978-3-030-30530-7_1
Keywords
quantum attacklattice reductionGrover's algorithmMersenne number cryptosystems
Contact author(s)
tiepelt @ dev-nu11 de
History
2020-02-07: revised
See all versions
Short URL
https://ia.cr/2019/1027

CC BY

BibTeX

@misc{cryptoeprint:2019/1027,
author = {Marcel Tiepelt and Alan Szepieniec},
title = {Quantum LLL with an Application to Mersenne Number Cryptosystems},
howpublished = {Cryptology ePrint Archive, Paper 2019/1027},
year = {2019},
doi = {10.1007/978-3-030-30530-7_1},
note = {\url{https://eprint.iacr.org/2019/1027}},
url = {https://eprint.iacr.org/2019/1027}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.