| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

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.