0
$\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?

$\endgroup$

marked as duplicate by fgrieu, Ilmari Karonen, Ella Rose, e-sushi Sep 14 '18 at 20:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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 Sep 11 '18 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 Sep 11 '18 at 9:56
  • $\begingroup$ @fgrieu You're right. I should have said that current public key cryptography will not survive. $\endgroup$ – forest Sep 11 '18 at 9:59
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.

$\endgroup$
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.

$\endgroup$
  • 1
    $\begingroup$ I would agree with might sooner or later, but will? $\endgroup$ – fgrieu Sep 11 '18 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$ – AleksanderRas Sep 11 '18 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 Sep 11 '18 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$ – AleksanderRas Sep 11 '18 at 10:25

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