Hidden Subgroup Problem

Interestingly, known public-key cryptosystems all seem to depend on the difficulty of the hidden subgroup problem. Suppose you have a group that can observe, and a subgroup that you cannot observe. Instead, you have a function that is constant along cosets of the group and different for different subgroups. The hidden subgroup problem is to compute a generating set for the subgroup just by evaluating the function. The problem generalizes integer factorization, the graph isomorphism problem and the problem of finding the shortest vector in a lattice. An efficient algorithm would apparently crack all known public-key cryptosystems.

Chris Lamont has a survey paper on the hidden subgroup problem in quantum computing, one that does not assume any background in quantum mechanics. Dave Bacon has some thoughts on an alternate approach.

One thought on “Hidden Subgroup Problem

  1. The US military has sponsored research by computer scientists on hidden chess — chess played where one player cannot see all the pieces of the other player, and may only learn of their location when attempting to move to the same square as a hidden piece. Even when only 1 or 2 pieces are hidden from view, the resulting uncertainty can make the game much more difficult if these pieces are important ones. The military application? Submarine warfare: you may only know the location of your enemy’s submarines when they surface or when your own submarines stumble across them.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>