13
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – Chris Peikert
    Commented Oct 24, 2015 at 13:29
  • $\begingroup$ 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. $\;\;\;\;$ $\endgroup$
    – user991
    Commented Oct 24, 2015 at 21:18
  • 3
    $\begingroup$ 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... $\endgroup$
    – Yehuda Lindell
    Commented Oct 25, 2015 at 6:23
  • $\begingroup$ @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. $\endgroup$
    – mephisto
    Commented Oct 26, 2015 at 8:22

1 Answer 1

Reset to default
7
$\begingroup$

This is in principle similar as how "normal" cryptosystems are proven. With some algorithms we can reduce them to some "hard problem", but we do not know that those problems are actually hard to solve. Only that we cannot solve them efficiently. For example, the Diffie-Hellman problem is not even known to be NP-hard, never mind the whole issue of P vs. NP.

Similarly, we know some problems that Shor's algorithm accelerates. Post-quantum algorithms avoid these and make use of problems to which Shor's algorithm does not offer an easy solution. However, that does not mean there is no other algorithm that solves them, or even that there is no way to use Shor's for them. (E.g. it is possible that the hidden subgroup problem in non-abelian groups can somehow be reduced to the HSP in abelian groups.)

In the end it is similar as with symmetric algorithms. They are not so much proved secure, but become proven after facing years of cryptanalysis.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.