18
$\begingroup$

I understand my group theory (allegedly), so I can make partial sense of The Hidden Subgroup problem:

Given a group $G$, a subgroup $H \leq G$, and a set $X$, we say a function $f : G \Rightarrow X$ separates cosets of $H$ if for all $g_1, g_2 \in G$, $f(g_1) = f(g_2)$ if and only if $g_1H = g_2H$.

Hidden subgroup problem: Let $G$ be a group, $X$ a finite set, and $f : G \Rightarrow X$ a function such that there exists a subgroup $H \leq G$ for which $f$ separates cosets of $H$. The function $f$ is given via an oracle. Using information gained from evaluations of $f$ via its oracle, determine a generating set for $H$.

In English as much as possible, $G$ is a group which means it satisfies certain conditions such as there being an identity and inverse element under an operation. Here, the operation isn't specified. So then we have some set $X$ which does not necessarily have to meet these criteria, and $f$ a function that maps $G$ the group onto $X$.

Cosets e.g. $gH$ are the set of all $H$ operated on by a specific $g$, so $gH = {gh: h \in H, g}$. $Hg$ is the other ordering and exists because groups aren't required to be abelian.

So this splitting function $f$ ensures each coset is mapped uniquely if when the function is applied to the group members it and derives the same result, when applied to the relevant cosets it must also derive the same result. This establishes that each coset does essentially map to a unique set of elements in $X$ if I understand this correctly.

So, the HSP is essentially the task of finding $H$ given $G$, $f$ and $X$ if I follow that correctly.

So, the obvious one-way-problem great-if-you-know-$H$ issue aside, how does the HSP affect cryptography? Specifically, aside from the discovery of the set $H$ in $X$ I see no particular direct use for the HSP, yet I have come across it frequently in discussions on cryptography, particularly with the odd link or reference towards this paper. Finally, am I missing anything, aside from the impacts of cryptography, in my summary of the HSP?

$\endgroup$
2
  • $\begingroup$ Can we say that HSP is the decisional version subgroup problem as presented here: goo.gl/wOiCzR (The BGN cryptosystem) $\endgroup$
    – curious
    Oct 16, 2013 at 8:54
  • $\begingroup$ @curious if that's a question, feel free to fill it out a bit and ask it :) You just need to hit the ask question button. If it's an answer, I'd love to hear more of it, feel free to answer below. Even Qs with accepted answers can be improved upon. $\endgroup$
    – user46
    Oct 18, 2013 at 12:58

3 Answers 3

13
$\begingroup$

As far as I understand, the HSP is a hard problem such that:

  • some types of HSP (namely those operating in an abelian group) can (theoretically) be solved efficiently on a quantum computer (assuming one can be built);
  • many types of public key cryptosystems can be reduced to the HSP: if you can solve the HSP you can break the key.

In particular, integer factorization and discrete logarithm (in any abelian group, which includes elliptic curves) can be reduced to HSP over abelian groups, and thus easily breakable on a quantum computer. This is not really new: Shor's algorithm already does that. It just happens that Shor's algorithm is a special case of HSP.

The interesting part is that lattice reduction can be reduced to HSP over a non-abelian group, for which no efficient algorithm is known yet. So this formalism is actually giving reasons on why lattice-based algorithm may survive in the post-quantum world.

In your summary of HSP, one might add two details: "finding H" really means "finding a set of elements of G which generate H" (i.e. H is the smallest subgroup of G which contains all those elements); and: "given f" means "a black box implementing f is given, and can be invoked repeatedly on any inputs".

$\endgroup$
1
  • $\begingroup$ I would like to add that this is not just theoretical and that quantum computers solving the HSP have been built and demonstrated that the algorithm works. They're just not large enough to handle cryptographic inputs (yet) $\endgroup$
    – saolof
    Feb 2, 2022 at 8:26
3
$\begingroup$

In cryptography, you care not merely that some problem is hard but that hard instances are readily producible.

Why don't people use NP-complete problems for cryptography, for example? An NP-complete problem would give you greater confidence asymptoticly speaking for two reasons : If any NP-complete problem were collapsed to P, then factoring becomes P too. Factoring is quantum polynomial time (BQP) but no relationship between BQP and NP is known. Instead, there is a more insidious problem that many NP-complete problems have too many easy cases to quickly find hard instances.

There are many easy cases for the Hidden Subgroup Problem as well. In fact, there are interesting algorithms for identifying non-abelian finite groups that work by solving hidden subgroup problems for which polynomial time solutions exist thanks to the Classification of the Finite Simple Groups.

$\endgroup$
1
$\begingroup$

The hidden subgroup problem is very useful for developing an understanding of pairing-based non-interactive zero-knowledge proofs. You would need a suitable elliptic curve of large composite order in order to use the hidden subgroup problem securely so in practice, you probably wouldn't bother as the implementation would be very slow. However, the explanation and maths using the HSP is relatively understandable so it's useful for pedagogical purposes. See Jens Groth's talk http://research.microsoft.com/apps/video/default.aspx?id=103365

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.