My remark is that if you want polynomial time, you should just try to solve SVP directly. The oracle is a distraction; SVP doesn’t have an oracle and it is already hard enough. Part of the point is that Regev’s important other reduction, from DHSP to subset sum, suggests that SVP is not all that much easier than all of DHSP.

I like your suggestion to think of a quantum algorithm as a communication result. I’m a bit puzzled by what you said next. Since DHSP is an oracle problem by definition, I’m not sure what it would mean to remove the oracle from it. I would have said that Regev’s result meant that we can’t beat classical algorithms if we only use of the oracle in the usual way (coset sampling) - the only way we know - and for this reason “we’ve all been robbed of ideas.” Did you mean something stronger (or different)?

Oh sorry, I can say something about this. Every quantum algorithm that I know of is in a sense a communication result: it manages to extract a miraculous amount of information from a classically unyielding oracle. If you’re asking about polynomial-time algorithms for DHSP, then Regev has at least removed the oracle from the problem. So it is hard in the sense that we’ve all been robbed of ideas. There are no reduction results that indicate that it is hard, except for Regev’s two reductions that go in a circle.

On the other hand, there is an important reduction that indicates that SHSP (symmetric group HSP) is hard. Namely, HSP for a group G is at least as hard as HSP for any subgroup H of G. For example, the symmetric group contains huge dihedral groups, so SHSP is DHSP-hard. I (and others) conjecture that SHSP is much harder than graph isomorphism, which its famous special case.

Well, there is a reduction result for DHSP that isn’t all that conclusive. DHSP can be defined as the abelian hidden shift problem with a single shift. It is therefore at least as hard as any problem with multiple hidden shifts, which includes among other cases some other near-abelian hidden subgroup problems.

More “related to” than “based on”. Sadly, that is about all I can say in response to your good questions.

Thanks for the information; I hadn’t known that your result was based on ideas from classical lattice algorithms. (I looked at your paper when it first appeared on the arXiv, but hadn’t noticed your extended version until now.)

For clarity I should have said any _polynomial time_ quantum algorithm would break these lattice based systems. Your algorithm for the DHSP, together with Regev’s improvement, is the best quantum algorithm we have so far but it is still superpolynomial so doesn’t break lattice based systems. My main concern about the Ajtai-Dwork algorithm and its successors is that I believe they have unwieldy key sizes; I should check that myself but if you or someone else knows for what key size these give the same level of security as RSA for example let me know! The lattice based approach still seems like the most promising candidate for the development of a practical public key encryption system safe from quantum attack, but I wouldn’t count on it yet; apart from the key size issue, the DHSP problem certainly seems hard, but I’m not ready to say it won’t fall to a novel quantum attack. Should I be?

Hi Eleanor!

Note that my algorithm does apply to coset sampling, even cosets with moderate spurious superposition. (Cosets with the other kind of error, too little superposition, are poison.) However, my algorithm combined with Regev’s paper has roughly the same complexity as good classical lattice algorithms. (And “roughly the same” probably means moderately worse rather than moderately better, on top of the fact that classical algorithms don’t need a quantum computer.) The gist of my result is that some of the ideas for good lattice algorithms also give you good DHSP algorithms. The gist of Regev is that DHSP and lattice problems are quantumly polynomially equivalent. However, his polynomial equivalence does not preserve “good” in the weak sense of my paper.

Kurt: My views on quantum gravity can be bought. My views about the hardness of NP-complete problems are not for sale to anyone.

Smolin’s statement is correct for _practical_ asymmetric (public key) encryption systems whose security is widely agreed upon by the cryptographic community. (It is too strong because quantum algorithms haven’t touched the security of symmetric key encryption systems.)

McEliece is not practical; according to The Handbook of Applied Cryptography, for the recommended security parameters the public key size is 2^19 bits, which will be unwieldy for most applications for the foreseeable future (also the data expansion factor is about 1.6). Also because of its impracticality its security has received less scrutiny.

NTRU: According to Koblitz and Menezes’s A Survey of Public Key Cryptosystems (http://citeseer.ist.psu.edu/695523.html), “a history of successful attacks on various versions of NTRU makes many people hesitant to endorse its use.”

My impression is that the Ajtai-Dwork lattice based system, and its successors, also have impractically large public keys, even after the improvement by Regev. Can anyone confirm this? (Also Regev has shown that these systems would be broken by any quantum algorithm for the dihedral HSP involving coset sampling. So these systems depend on a problem closely related to those Shor’s algorithm solved, though that problem has proven difficult.) Does anyone know the relation between these lattice based systems and NTRU?

Koblitz and Menezes’s A Survey of Public Key Cryptosystems also discuss PKE cryptosystems based on braid groups which are widely believed to be insecure. They also mention systems based on hidden monomials. Anyone know the status of those? Many versions of knapsack based PKE cryptosystems were broken so that people are pessimistic about using this problem as the basis for a PKE system. Many other types of PKE cryptosystems have been developed and then broken.

Given the historic difficulty of creating practical PKE cryptosystems based on problems other than factoring or discrete log, here’s a question I believe is open to debate: which will come first, the building of a quantum computer capable of breaking existing factoring and discrete log PKE cryptosystems or the development of a practical PKE cryptosystem which is widely believed to be secure against quantum and classical attacks?