This is a purely theoretical question. Everyone is talking about quantum cryptography being the next big thing as quantum computers will be much faster than the computers we have today.

So, from my understanding, quantum computers will have a much larger computation speed.

My question is, instead of looking for new algorithms to beat the computation speed of quantum computer, why can't we just use huge sized keys to encrypt data?

  • 1
    $\begingroup$ Quantum computers are not inherently faster than classical computers. They can do some operations efficiently that classical computers cannot do efficiently. It is definitely not that case that arbitrary algorithms run faster or even as fast on quantum computers compared to on classical computers. $\endgroup$ Jul 7 '18 at 0:07

For symmetric cryptography, it is highly plausible that doubling the key size compared to current practice (say from 128 to 256-bit) provides more than adequate protection against hypothetical quantum computers capable of running Grover's algorithm (or similar) on large inputs. It requires $O(2^{n/2})$ effort for $n$-bit key, compared to $O(2^n)$ for brute force key search on classical computers.

Many asymmetric cryptographic algorithms, including all those commonly used (RSA encryption and signature, Diffie–Hellman key exchange, ElGamal encryption, Schnorr signature, DSA, ECDH, ECDSA, ECIES, EdDSA..) are in principle vulnerable to an hypothetical quantum computer capable of running Shor's algorithm on large inputs, which uses resources and work only polynomial in the number of key bits $n$. That does not work on symmetric cryptography because Shor's algorithm derives the private key from the public key under assumption of arithmetic relations between them, which do not exist between symmetric key and the rest of what an adversary is expected to know in symmetric cryptography. Due to the polynomial growth, demonstrably high security would require impractically large RSA or even ECC keys; this is made quantitative in the two RSA entries of the NIST Post-Quantum Cryptography round 1.

Still, increasing the key size of common asymmetric cryptosystems does increase their resistance to hypothetical quantum computers usable for cryptanalysis (Cryptographically Relevant Quantum Computer in NSA terminology). At least, that makes it necessary to use proportionally more coherent qubits, which is a hurdle. We are so far from having quantum computers useful for anything crypto-related that predictions are hard.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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