Cryptology ePrint Archive: Report 2019/716

On the Quantum Complexity of the Continuous Hidden Subgroup Problem

Koen de Boer and 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 (Eisentrager 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. Incidentally, our work clarifies certain claims from the extended abstract of Eisentrager et al.

Category / Keywords: Quantum Algorithm, Hidden Subgroup, Period Finding, Fourier Transform, Cryptanalysis.

Date: received 17 Jun 2019

Contact author: K de Boer at cwi nl, serge fehr@cwi nl, leo ducas@cwi nl

Available format(s): PDF | BibTeX Citation

Version: 20190618:104745 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]