1
$\begingroup$

Quantum computation is based on the superposition principle of quantum physics. Bits in a normal computer are either 0 or 1. Quantum physics allows bits to be in a superposition of 0 and 1, in the same way, Schrödinger’s cat can be in a superposition of “alive” and “dead.” [http://nautil.us]

My question is: Can public key cryptography survive quantum computers?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ I believe this has been answered in various questions here already. The gist of the answer is that public key cryptography like RSA and ECC will not survive, whereas symmetric cryptography like AES and SHA-256 will survive simply by doubling their key lengths. $\endgroup$
    – forest
    Commented Sep 11, 2018 at 9:34
  • 1
    $\begingroup$ @forest: Your summary is way too radical for me. While RSA, and Discrete-Logarithm-based ECC public key cryptographic schemes (including ECDH, ECDSA, EdDSA) would not survive large general-purpose quantum computers, 1) such computers are hypothetical, thus these schemes might well turn out to survive all quantum computers that humanity will build 2) other public-key cryptographic schemes (including some ECC-based, e.g. SIKE), are conjectured to resist even hypothetical large general-purpose quantum computers. $\endgroup$
    – fgrieu ♦
    Commented Sep 11, 2018 at 9:56
  • 1
    $\begingroup$ @fgrieu You're right. I should have said that current public key cryptography will not survive. $\endgroup$
    – forest
    Commented Sep 11, 2018 at 9:59
  • 1
    $\begingroup$ Note that these kind of dupes are great end points for search engines to look up the dupes. As such they have a function of their own, even if other Q/A's are dupes. This would be lost when questions are merged; merging is hard if the questions are asked differently. $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 4, 2020 at 8:42

2 Answers 2

Reset to default
4
$\begingroup$

Can public key cryptography survive quantum computers?

Yes.

All current PKC implementations might sooner or later be insecure due to sufficiently powerful quantum computer running Shor's algorithm.

But there already exists an algorithm for post-quantum-PKC: Supersingular isogeny key exchange. This is a likely candidate for post-quantum-PKC, probably this or a smiliar algorithm will be used once powerful quantum computers exist.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I would agree with might sooner or later, but will? $\endgroup$
    – fgrieu ♦
    Commented Sep 11, 2018 at 10:02
  • 1
    $\begingroup$ You're right, we don't know for certain. But I assume that more and more powerful quantum computers will come along because they have a wide range of applications, like simulating complex systems in chemistry, biology, physics, etc. $\endgroup$
    – AleksanderCH
    Commented Sep 11, 2018 at 10:06
  • 1
    $\begingroup$ it is much more likely to happen soon that some breed of quantum computers becomes useful to "simulating complex systems in chemistry, biology, physics" or solving some applied optimization problems, than it is that they become capable of running Shor's algorithm to solve a problem that a classical computer can not. There's very little real progress towards the later, when one screens out the bogus claims, unless I missed something when/since writing this. $\endgroup$
    – fgrieu ♦
    Commented Sep 11, 2018 at 10:16
  • 2
    $\begingroup$ No you're completly right, there is very little progress in implementing shor's algorithm. I was thinking on a scale of decades if not centuries. $\endgroup$
    – AleksanderCH
    Commented Sep 11, 2018 at 10:25
5
$\begingroup$

Current commonly used public key cryptography systems are based on the hardness assumption of factorization and/or discrete lograrithm.

Both these problems are solved efficiently using Shor's algorithm using a quantum computer.

Should someone build a quantum computer capable of running the algorithm with thousands of qbits and the ability to apply enough operations on them without decoherence, then it would break RSA and diffie-hellman including elliptic curvre variants.

This breaks all commonly used public key cryptography but does not break all known public key cryptography. There are other asymmetirc algorithms, for example those based on lattice problems which are currently believed to be secure even in the face of quantum computers.

Improve this answer
$\endgroup$

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