Paper 2021/562
A fusion algorithm for solving the hidden shift problem in finite abelian groups
Wouter Castryck and Ann Dooms and Carlo Emerencia and Alexander Lemmens
Abstract
It follows from a result by Friedl, Ivanyos, Magniez, Santha and Sen from 2014 that, for any fixed integer $m > 0$ (thought of as being small), there exists a quantum algorithm for solving the hidden shift problem in an arbitrary finite abelian group $(G, +)$ with time complexity poly$( \log |G|) \cdot 2^{O(\sqrt{\log |mG|})}$. As discussed in the current paper, this can be viewed as a modest statement of Pohlig-Hellman type for hard homogeneous spaces. Our main contribution is a simpler algorithm achieving the same runtime for $m = 2^tp$, with $t$ any non-negative integer and $p$ any prime number, where additionally the memory requirements are mostly in terms of quantum random access classical memory; indeed, the amount of qubits that need to be stored is poly$( \log |G|)$. Our central tool is an extension of Peikert's adaptation of Kuperberg's collimation sieve to arbitrary finite abelian groups. This allows for a reduction, in said time, to the hidden shift problem in the quotient $G/2^tpG$, which can then be tackled in polynomial time, by combining methods by Friedl et al. for $p$-torsion groups and by Bonnetain and Naya-Plasencia for $2^t$-torsion groups.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- hidden shiftcollimation sievehard homogeneous space
- Contact author(s)
- wouter castryck @ esat kuleuven be,ann dooms @ vub be,carlo emerencia @ vub be,alexander lemmens @ esat kuleuven be
- History
- 2021-05-27: revised
- 2021-05-03: received
- See all versions
- Short URL
- https://ia.cr/2021/562
- License
-
CC BY