
## 4. Hidden Shift

1. #### Problem 4.1.

How fast are approximate SVP attacks via hidden shift algorithms?
• #### Problem 4.2.

How much noise is tolerated in hidden shift algorithms? Consider too many solutions vs. too few.
• #### Problem 4.3.

[Greg Kuperberg] Is there a fast hidden shift algorithm for Heisenberg group over $\mathbb F_p$?
1. Remark. HSP is known.
• #### Problem 4.4.

[Tanja Lange] What is the cost of hidden shift on $\mathbb Z$ where the shift $s\in [a,b]$, under binary cost of oracle?
• #### Problem 4.5.

[Greg Kuperberg] Hidden shift on $\mathbb Z^d$ where $f_0$ and $f_1$ are periodic under unary oracle cost.
• #### Problem 4.6.

[Elena Kirshanova] How does Kuperberg’s algorithm behave under multiple hidden shifts (with known relations between shifts, e.g. arithmetic progression) with Gaussians, using the work of Ivanyos, Prakash, and Santha?,

Cite this as: AimPL: Quantum algorithms for analysis of public-key crypto, available at http://aimpl.org/quantumalg.