# How is “post-quantum security” proven/shown?

Due to growing concerns over the threat of quantum computing to asymmetric cryptography (RSA, ECC, etc), a number of "quantum resistant" replacements have been proposed (SPHINCS, McBits, and many more). How are these cryptosystems proven (or argued) to be secure in the presence of quantum computers?

Are the schemes only proven secure against some finite set of quantum algorithms (Shor's algorithm, Grover's algorithm, etc), or are they proven secure against all quantum algorithms possible in some theoretical model of quantum computing?

• It's the former. We don't know how to unconditionally prove security against classical algorithms, so doing so for quantum algorithms is also out of the question. But we can find and use problems that don't succumb to any known quantum algorithms/techniques. – Chris Peikert Oct 24 '15 at 13:29
• Aside from interactive arguments of work with a super-constant number of rounds, I'm not aware of any proof that there is a scheme which is secure infinitely-often against (classical) rational-uniform TC0 adversaries. $\;\;\;\;$ – user991 Oct 24 '15 at 21:18
• One of the big problems is that there aren't many people doing "quantum cryptanalysis", so it's unclear how confident we should be in something just because Shor's algorithm doesn't work... – Yehuda Lindell Oct 25 '15 at 6:23
• @YehudaLindell At least more confident than in something for which we know that Shor's algorithm works. But indeed it is a problem that there is only little work on quantum cryptanalysis. Most works so far barely apply Grover's search algorithm to some intermediate search step in the classical algorithms. – mephisto Oct 26 '15 at 8:22