Paper 2021/562

A fusion algorithm for solving the hidden shift problem in finite abelian groups

Wouter Castryck, Ann Dooms, 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|)2O(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 somewhat simpler algorithm achieving the same runtime for m=2tp, 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 , which can then be tackled in polynomial time, by combining methods by Friedl et al. for -torsion groups and by Bonnetain and Naya-Plasencia for -torsion groups.

Metadata
Available format(s)
PDF
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
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/562,
      author = {Wouter Castryck and Ann Dooms and Carlo Emerencia and Alexander Lemmens},
      title = {A fusion algorithm for solving the hidden shift problem in finite abelian groups},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/562},
      year = {2021},
      url = {https://eprint.iacr.org/2021/562}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.