Hidden Shift (problem 5)
Hidden shift on where and are periodic under unary oracle cost. AimPL: Quantum algorithms for analysis of public-key crypto
Background
In the standard hidden-shift setup, a known subgroup of a group is given, and is constant on right cosets of and injective on the quotient. The second function is a translate, for an unknown shift . On an abelian group such as , this makes the shift problem closely related to hidden-subgroup algorithms. The question's use of periodic functions points toward this framework, but does not specify the period subgroup or the other promises on the functions. The hidden subgroup problem for infinite groups (arXiv:2507.18499)
Oracle cost matters on an infinite group: a query at a large integer vector can have small binary description but large magnitude. In the cost model discussed for integer-group problems, charging polynomial cost in the vector's -norm corresponds to writing its coordinates in unary, with input length . The hidden-shift approaches cited in the recent lattice work build on subexponential algorithms for the dihedral hidden subgroup problem, including Regev's polynomial-space algorithm, and on earlier work by Kuperberg, Regev, and Peikert. The hidden subgroup problem for infinite groups (arXiv:2507.18499) A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.