0
$\begingroup$

Quantum computing is at the intersection of math, physics, and computer science.

It seems so complicated that only large organizations could build such algorithms and have their own quantum computing devices and the other essentials to calculate such complicated equations.

If there is a major advance in the production of quantum computing science and its equipment becomes available to either hackers or intelligence services, can cryptography survive quantum computing?

P.S: If we could not upgrade to quantum or post-quantum signature schemes, then what happens?

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ This question is much too broad for the site. If you can narrow it down to a specific question about a specific cryptosystem, and demonstrate that you have done enough research to show that it is not already answered here, then maybe that question would be on-topic. But this site is not a repository of essay questions for business school and management consultant summaries of cryptography. $\endgroup$
    – Squeamish Ossifrage
    Jun 17 '19 at 17:07
5
$\begingroup$

It depends on the kind of quantum computer and how many logical qubits it has. Not all quantum computer designs are capable of breaking cryptographic systems. The popular adiabatic quantum computers, while very useful for certain tasks, have no cryptanalytic utility. Designs that are capable of running, say, Shor's algorithm are currently in their infancy. It isn't known how well they'll scale.

Realistically, when/if such quantum computers become mainstay, we will need to have moved from algorithms based on factorization or the discrete log problem (or any other hardness problem in the BQP complexity class) to a post-quantum variant. Key exchange algorithms must be upgraded sooner. If you need 25 years of protection, you have to discontinue vulnerable algorithms 25 years before quantum computers can attack it, because they are vulnerable to retroactive cryptanalysis.

It's not as important to upgrade to post-quantum signature schemes. You can delay upgrading a digital signature algorithm until the very day a cryptanalytic quantum computer becomes available. This is because breaking a signature must be done at the time of the attack, not after. This isn't unique to quantum computers. Someone who used PGP in the 90s with a 512-bit key doesn't need to worry about someone forging their signatures because that key has long-since expired or been revoked, so obtaining such an old private signing key is useless.

NIST is currently working on standardizing post-quantum key exchange and signature algorithms for this very reason. They have set a tentative completion date for 2024.

Improve this answer
$\endgroup$
5
  • $\begingroup$ ....and we'll need so much He3... $\endgroup$
    – b degnan
    Jun 18 '19 at 1:06
  • $\begingroup$ "breaking a signature must be done at the time of the attack, not after" but Is this also applies to military communications or sensitive cases? $\endgroup$
    – R1w
    Jun 18 '19 at 1:18
  • 1
    $\begingroup$ @R1w Yes it does. As soon as the public key for a private signing key is no longer trusted by your intended recipients, there is no danger to that private key being stolen or cracked. All you could do with it is sign a message with it, but if no one trusts that key anymore, what's the problem? It really only matters if for some reason people still need to trust the old keys (e.g. verifying something that was archived and never re-signed with a newer key by the creator). $\endgroup$
    – forest
    Jun 18 '19 at 1:29
  • $\begingroup$ @forest but, what if they capture the ciphertext and can decrypt the previous messages? $\endgroup$
    – R1w
    Jun 18 '19 at 1:32
  • 2
    $\begingroup$ @R1w That's encryption, not signing. If someone cracks the encryption key, even 50 years after the fact, they can break the messages. If someone cracks the signing key, it doesn't really matter once that key is no longer being used (and you can stop using it as soon as quantum computers are available). $\endgroup$
    – forest
    Jun 18 '19 at 1:33
0
$\begingroup$

Most modern cryptographic systems that are used in practice (RSA, DSA, ECDSA, etc.) rely on the problem of factorization or discrete logarithm, which can be solved in polynomial time on a quantum computer. So, they will be compromised. The Grover's algorithm allow reduce by 2 times the complexity of attacks on symmetric cryptosystems. Also exists several areas of cryptography that can be used in the post-quantum period: lattice-based cryptography, code-based cryptography hash-based cryptography etc. But there is no strict evidence that there is no quantum algorithm capable of compromising them in polynomial time.

Improve this answer
$\endgroup$
4
  • $\begingroup$ A brief search shows Polynomial-time quantum algorithm exists, of course for other usePolynomial-time quantum algorithmso, then what ? it is possible to compromise the modern cryptographic system? $\endgroup$
    – R1w
    Jun 17 '19 at 16:45
  • 2
    $\begingroup$ @R1w Depends on the cryptosystem. For most asymmetric cryptographic schemes that are standardized and widely used in practice, algorithms have been found that allow you to make an attack in polynomial time. Now NIST is holding a competition to create new standards. There are several promising areas for which quantum attacks are not found. What are you specifically interested in? This is a rather extensive topic. $\endgroup$
    – OneUser
    Jun 17 '19 at 21:13
  • 2
    $\begingroup$ The fact is that we do not know exactly what problems quantum computers are capable of solving. If NP = BQP, then only absolutely robust systems like “One-time pad” will remain cryptographically resistant. But most likely NP! = BQP and there are cryptosystems resistant to quantum attacks. If we talk about digital signature, then hash-based cryptography comes down to the security of symmetric crypto-primitives and can be considered the most cryptographically secure. It also seems to me very promising lattice-based cryptography (NTRU-based systems, RLWE-based systems etc.). $\endgroup$
    – OneUser
    Jun 17 '19 at 21:33
  • 1
    $\begingroup$ By two times It actually reduces it by the square root. $\endgroup$
    – forest
    Jun 19 '19 at 3:10

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