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.