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

4. Hidden Shift


    1. Add remark

      Problem 4.1.

      How fast are approximate SVP attacks via hidden shift algorithms?


        • Add remark

          Problem 4.2.

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


            • Add remark

              Problem 4.3.

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


                    • Add remark

                      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?


                        • Add remark

                          Problem 4.5.

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


                            • Add remark

                              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.