Welcome to the resource topic for 2021/562
Title:
A fusion algorithm for solving the hidden shift problem in finite abelian groups
Authors: Wouter Castryck, Ann Dooms, Carlo Emerencia, 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 somewhat 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.
ePrint: https://eprint.iacr.org/2021/562
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .