Paper 2019/716

On the Quantum Complexity of the Continuous Hidden Subgroup Problem

Koen de Boer, Léo Ducas, and Serge Fehr

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 (Eisentraeger et al. STOC 2014) considers the problem of finding a full-rank lattice as the hidden subgroup of the continuous vector space $\mathbb{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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in Eurocrypt 2020
Keywords
Quantum AlgorithmHidden SubgroupPeriod FindingFourier TransformCryptanalysis.
Contact author(s)
K de Boer @ cwi nl
serge fehr @ cwi nl
leo ducas @ cwi nl
History
2020-02-23: revised
2019-06-18: received
See all versions
Short URL
https://ia.cr/2019/716
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/716,
      author = {Koen de Boer and Léo Ducas and Serge Fehr},
      title = {On the Quantum Complexity of the Continuous Hidden Subgroup Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2019/716},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/716}},
      url = {https://eprint.iacr.org/2019/716}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.