Post-Quantum Resistance

Do quantum computers exist? Is there a teapot flying in outer space? Is "Grover" Godzilla's secret pet name? Discuss here!
Post Reply
circuit
Posts: 2
Joined: Wed Aug 16, 2017 7:16 pm

Thu Aug 17, 2017 4:05 am

When proving something to be post-quantum resistant, is it simply that there are no known algorithms to solve a particular assumption, or is there an inherent algebraic structure that provides resistance to a quantum adversary? If the latter, what exactly is this algebraic assumption, and if the former could such an algebraic structure be proven to exist or not?

One such problem I'm familiar with is the hidden subgroup problem https://en.wikipedia.org/wiki/Hidden_subgroup_problem which Shor's algorithm successfully solves. The abelian/non-abelian structure is the main difference, and I'm curious if there's an abstraction that applies to all types of problems.

DefuseSec
Posts: 3
Joined: Wed Aug 16, 2017 12:09 am

Wed Oct 25, 2017 5:20 pm

It's exactly the same sort of situation with pre-quantum cryptography. Nobody knows that classical computers can't factor numbers quickly, we just think that they can't because lots of people have tried and failed to figure out how. Similarly, for post-quantum crypto, it's just that nobody has (yet) found a quantum algorithm to break the scheme. To get a stronger security guarantee, we'd first need to know how to prove P!=NP, since as long as P=NP is a theoretical possibility, there might not be any secure cryptosystems at all.

Post Reply