[Crypto] Period finding for Quantum Computers

Solution 1:

Can quantum computer find the period of any given function efficiently? Are there any requirements towards the function?

Well, the function has to be periodic; that is, we have, for some $c > 0$, $f(x) = f(x+c)$, for all $x$ [1].

For both factoring and discrete log, we have such a function; and we know how finding the period of that function will give us the answer.

However, postquantum algorithms, we don't have such a way. For code-based schemes, no periodicity is apparent. For lattice-based schemes, there is (periodicity is inherent in the idea of a lattice), however we don't know how to convert finding such a periodicity into (say) an answer to the shortest vector problem.

---

[1]: Actually, I believe Shor's algorithm will work even if the above relation holds for most $x$; however for the functions of interest, true periodicity holds...

---

Solution 2:

There are a few limitations on the function that you may or may not consider obvious.

The image of the function $f$ has to be a finite set. The function $f$ has to be computable and the efficiency depends on how well $f$ can be implemented as a quantum circuit. Arguably, you also need some sort of bound on the period so that you know how big the quantum Fourier transform needs to be (alternatively you could keep running the algorithm doubling the size of the QFT until it is successful).

A fuller generalisation of Shor's algorithm is the hidden subgroup problem for Abelian groups, where the cyclic group structure of iterative evaluation is generalised to the action of a general Abelian group. All post-quantum algorithms should be designed so that there is no instance of this problem that helps to crack the cryptosystem. "Noisy" algorithms seem to be a good way to avoid hidden abelian subgroup structure.

It's worth noting that the hardness of short/close vector problems in lattices can be attacked if we can efficiently solve the hidden dihedral subgroup problem (though we don't know of a polynomial time quantum algorithm for solving this).