Note on Hidden Shifts as Hidden Subgroups
Skip to main content
Note on Hidden Shifts as Hidden Subgroups
Get link
Other Apps
July 30, 2026
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$. It's a simple check that this forms the desired dihedral group, and it fundamentally allows us to change a 'hidden shift' into a 'hidden subgroup'.<br>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) $$<br>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!<br>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.
cryptanalysis<br>quantum computing
Get link
Other Apps
Comments
Post a Comment
Popular posts from this blog
Decrypting config.bin files for TP-Link WR841N, WA855RE, and probably more…
January 01, 2020
Notice - moved from medium.com, as their pricing model is just plain wrong... This is also hosted here , but updated below. Tl;Dr — it’s basically the same as it always was, except they added a compression step. YOLO. These devices are still Amazon’s ‘Choice’ when you search for ‘router’ to buy, so they’re pretty popular. Shut up, just gimme the script: If you want to read a config file from one of these (or similar) devices, just use the following script: # First strip the header: dd bs=1 skip=144 if=config.bin of=config1.bin # Now decrypt the file - same key as before! openssl enc -d -des-ecb -nopad -K 478DA50BF9E3D2CF -in config1.bin >tmp.bin # However you also need to decompress it with zlib: zlib-flate -uncompress config.json The contents of the config.json file is now the plaintext JSON config data for your router. Woo! :-D What data can you get? WiFi Keys, MD5 of the admin password, WEP key, IP ranges in use, and a few other artefac...
Read more
Aperiodic Tilings
August 21, 2021
Intro to the How and Why of Aperiodic Tilings Tilings! Also called tessellations, patterns in the Euclidian plane, space filling arrangements of infinitely many copies of geometric shapes, or just considered to be things in photos of interior design magazines... Tilings have a rich history, from the Sumerians in 4000BC, via the Romans' geometric mosaics, through the Girih and Zellij tilings used in Medieval mosques, to the modern theorems and ideas that have lead to new materials, facts about arrangements of things and packings, and interesting YT videos on the quirkier side of 'covering the plane with shapes'... To anyone who knows me personally, or professionally, it should be no surprise that I get rather very excited when I see videos on YouTube or blog posts or book sections on tilings. The reason why might not be that well known - but I spent the years on my PhD studying the...