Note on Hidden Shifts as Hidden Subgroups

 On of the key insights I acquired in the talks at QCPQA this last week was that a hidden shift over some finite abelian $A$ (usually $\mathbb{F}_2^n$) can be recast as a hidden dihedral subgroup problem via $$ \mathsf{Dih}(A) = A \rtimes \mathbb{Z}_2 \cong \mathbb{Z}_2^{n+1} $$ This notation was a little new to me, but I knew that $$ \mathbb{Z}_2 = \{0,1\} $$ Here, $A \rtimes  \mathbb{Z}_2$ is the twisted product, and $Dih(A)$ is the dihedral group of $A$ from that product. The product itself allows nontrivial elements of $\mathbb{Z}_2$ to act on elements of $A$ by by inversion $$ a \mapsto a^{-1} $$ and so as a set we would get $$ Dih(A) = A \times \mathbb{Z}_2 $$ however we have to twist the multiplication such that for $a,b \in A$ and $\epsilon, \delta \in \mathbb{Z}_2$, we let $\eta = (-1)^\epsilon$ and use the product $$ (a,\epsilon)(b, \delta) = (ab^{\eta}, \epsilon \otimes \delta) $$ where $\alpha \otimes \beta$ is XOR which for bits is just addition $\alpha + \beta \mod 2$. The word 'twisted' comes from the fact that under this product, $$ \epsilon a = a^{-1} \epsilon$$ It's a simple check that this forms the desired dihedral group, and note that for $A = \mathbb{Z}_n$ $$ \mathsf{Dih}(A) \cong D_{2n} $$ for the usual dihedral group of order $2n$. It fundamentally allows us to change a 'hidden shift' into a 'hidden subgroup' in the following way...

The twisted product here means that for two injective functions $f_0, f_1 : A \rightarrow S$ we can construct an oracle $$F(x,b) = f_b(x) \text{ for }(x,b) \in A \rtimes \mathbb{Z}_2$$ Running Simon's algorithm on $F$ we can find the hidden subgroup $H_\Delta = \{(0,0), (-\Delta,1) \}$. Indeed, $$ (x,0)(-\Delta,1) = (x-\Delta,1) $$ thereby $$ F(x-\Delta, 1) = f_1(x-\Delta) = f_0(x) = F(x,0) $$ Similarly $$ (x,1)(-\Delta,1) = (x+\Delta,0) $$ and so $$ F(x+\Delta,0) = f_0(x+\Delta) = f_1(x) = F(x,1) $$ with injectivity ensuring that these are exactly the collisions we are looking for. Finding non-trivial $(-\Delta, 1)$ recovers $\Delta$, noting that there's a rather pleasing `trick' amongst this which is that arbitrary-order translation $\Delta$ becomes an involution $$ (-\Delta, 1)^2 = (0,0) $$

So essentially, $$\boxed{\text{Hunting Hidden Shifts} \cong \text{Hunting Hidden Dihedral Subgroups} } $$ or perhaps more usefully $$ \boxed{\text{Hidden shift over } A \rightarrow \text{order-2 HSP over } \mathsf{Dih}(A) } $$ Recall that Simon's Algorithm is a quantum method precisely to find hidden subgroups in functions using quantum computers!

This doesn't 'break PQC' right away, but it really frames what the 'right question' might be when considering different cryptosystems such as HQC. Very handy fact, indeed. So in all, the challenge seems to reduce to down to extracting $\Delta$ from the non-abelian coset states in a system such as HQC. That's really neat (at least, to me!), and is what Prof Daniel Shiu is working on.