← All problems

Hidden Shift (problem 5)

Hidden shift on Zd\mathbb Z^d where f0f_0 and f1f_1 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 HH of a group GG is given, and f0f_0 is constant on right cosets of HH and injective on the quotient. The second function is a translate, f1(xs)=f0(x)f_1(xs)=f_0(x) for an unknown shift ss. On an abelian group such as Zd\mathbb Z^d, 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 11-norm corresponds to writing its coordinates in unary, with input length Θ(∥v∥1+d)\Theta(\lVert v\rVert_1+d). 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

References

Progress summary

Never refreshed

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.