Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Can we say that HSP is the decisional version subgroup problem as presented here: goo.gl/wOiCzR (The BGN cryptosystem) –  curious Oct 16 '13 at 8:54
    
@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. –  Ninefingers Oct 18 '13 at 12:58
add comment

3 Answers 3

up vote 8 down vote accepted

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".

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.