CryptoDB
On the Quantum Complexity of the Continuous Hidden Subgroup Problem
| Authors: |
- Koen de Boer , Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands
- Léo Ducas , Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands
- Serge Fehr , Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands & Mathematical Institute, Leiden University, The Netherlands
|
| Download: |
- DOI: 10.1007/978-3-030-45724-2_12
(login may be required)
- Search ePrint
- Search Google
|
|
Conference:
|
EUROCRYPT 2020
|
| Abstract: |
The Hidden Subgroup Problem (HSP) aims at capturing all problems that are susceptible to be solvable in quantum polynomial time following the blueprints of Shor's celebrated algorithm. Successful solutions to this problems over various commutative groups allow to efficiently perform number-theoretic tasks such as factoring or finding discrete logarithms.
The latest successful generalization (Eisenträger et al. STOC 2014) considers the problem of finding a full-rank lattice as the hidden subgroup of the continuous vector space R^m, even for large dimensions m. It unlocked new cryptanalytic algorithms (Biasse-Song SODA 2016, Cramer et al. EUROCRYPT 2016 and 2017), in particular to find mildly short vectors in ideal lattices.
The cryptanalytic relevance of such a problem raises the question of a more refined and quantitative complexity analysis. In the light of the increasing physical difficulty of maintaining a large entanglement of qubits, the degree of concern may be different whether the above algorithm requires only linearly many qubits or a much larger polynomial amount of qubits.
This is the question we start addressing with this work. We propose a detailed analysis of (a variation of) the aforementioned HSP algorithm, and conclude on its complexity as a function of all the relevant parameters. Our modular analysis is tailored to support the optimization of future specialization to cases of cryptanalytic interests. We suggest a few ideas in this direction. |
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30183,
title={On the Quantum Complexity of the Continuous Hidden Subgroup Problem},
booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
series={Lecture Notes in Computer Science},
publisher={Springer},
keywords={Quantum Algorithm;Hidden Subgroup;Period Finding;Fourier Transform;Cryptanalysis},
volume={12105},
doi={10.1007/978-3-030-45724-2_12},
author={Koen de Boer and Léo Ducas and Serge Fehr},
year=2020
}
