Two contributions to the Hidden Subgroup Problem

06 May 2010

Today, I have finished the preliminary version of my report on the Hidden Subgroup Problem (HSP). For those who have never heard about it before, we are given a finite group $G$ , a subgroup $H$ and a function $f : G \to S$ . This function is constant on each (left) coset of $H$ but takes different values on distinct cosets. Said otherwise we have:

$\forall g_{1}, g_{2} \in G, f (g_{1}) = f (g_{2}) \Leftrightarrow g_{1} H = g_{2} H$ The purpose is to identify the "hidden" subgroup $H$ (for instance we can return a generating set) with a complexity polynomial in $\log ∣ G ∣$ . Although it may seem really abstract, this problem allows to describe various quantum algorithms exponentially faster than their known classical versions. This includes the famous Shor's algorithm for integer factorization, which can break the ubiquitous RSA cryptosystem. Shor's algorithm uses a solution to HSP over a cyclic group but we have quantum algorithms for the larger class of dedekindian groups as well as miscellaneous other groups. Unfortunately, these algorithms are not enough to solve HSP over the dihedral group or the symmetric group. These two cases are particularly interesting since the former could solve a lattice problem used in cryptography to establish security proofs while a solution to the latter provides an efficient algorithm for the graph isomorphism problem.

For the moment, I have essentially reviewed the major results on dedekindian, dihedral and symmetric groups. Even if there is not many new things for researchers working on that topic, I hope it could serve as an introduction to the subject and be a useful review of the state-of-the-art. In particular, I plan to complete the Table of Hidden Subgroup Problems which gives a good overview. There are at least two contributions I brought to the topic that I would like to discuss briefly in this blog post.

First, I have studied how Regev's algorithm works. As stated in his paper, we have a solution to the $poly (\log N)$ -uniqueSVP if we can find a hidden subgroup $H = ⟨ (d, 1) ⟩$ in the dihedral group $D_{N}$ using coset sampling on the whole group. This point is often overlooked in several papers, where the reader could understand that an arbitrary solution to the dihedral HSP works. Fortunately, Regev's algorithm is sufficiently close to the coset sampling procedure so that we can modify it to include some kinds of recursive algorithm. With such a modification, a solution like Kuperberg's algorithm (where we apply coset sampling on subgroups of $D_{N}$ ) becomes acceptable. Actually, we can also modify the algorithm to work with the generalized dihedral group. Another remark is about the degree of the approximation given by Regev's algorithm: I have shown that we have a solution to the $Θ (n^{\frac{1}{2} + 2 D})$ -uniqueSVP if the query complexity of the HSP algorithm used is $O ({(\log N)}^{D})$ , thus providing a more accurate statement.

Recently, I have considered a general approach to the HSP using the classical description of finite group via composition series and simple groups. The idea is that if $N$ is a non-trivial normal subgroup of $G$ we can split the problems on two HSPs over $\frac{G}{N}$ and $N$ . We can repeat the procedure until we reach simple groups. Because the length of a composition series is polynomial in $\log ∣ G ∣$ , we get a solution to the general HSP under two conditions: we have algorithms for HSP over simple groups and we can build efficient oracles on the "reduced" groups. I've succeeded to find an alternative algorithm for the abelian case based on that framework but for the dihedral/symmetric, it seems that the two previous assumptions are exactly what we are stuck on. However, it could still be useful to solve HSP over other groups.

Now, my priority is to review the results we have for some semidirect products but I hope to have time to study various open issues such that HSP over simple groups, HSP-based algorithms etc