After we've concluded that 64-bit is an insecurity for classical computers, I think many would like to know, how secure in a perspective view, is 64 quantum bits security.

As we know, the Grover's algorithm halves the security strength offered by symmetric key primitives - a 128-bit-key block cipher would effectively require only $2^{64}$ trial decryption to recover key from a pair of plaintext and ciphertext on a quantum computer.

But how to put that into perspective? On classical computers, we have massively parallel processing units and hi-speed spinning fans providing air conditioning, we can have dedicatedly fabricated ASICs for extra speed up.

Q1) What equivalent can we find on a quantum computer?

We've always heard such obstacles as "quantum decoherence", and difficulty with entangling large number of particles, and some even question the possibility of even medium scale quantum computers. So

Q2) Is quantum computer really that impossible a dark art?

When NIST started their post-quantum cryptography standardization, they at first proposed having 128-bit classical security equivalent to 64 quantum bits security, they've later changed to measuring circuit depth.

Q3) What good translation between quantum security and classical security do we currently know.


Per @fgrieu, 64 quantum bits security should be defined as: require equivalent to $2^{64}$ "black-box" evaluation.

  • 1
    $\begingroup$ Grover's algorithm cannot be efficiently parallelized, so in practice, it may not be all that powerful. $\endgroup$
    – forest
    Dec 15, 2018 at 4:53
  • 1
    $\begingroup$ @forest this question' answer gives in big-Oh; Can we speed up the Grover's Algorithm by running parallel processes? with $K=2^k$ copies to $\mathcal{O}(\sqrt{N/K})$, $\endgroup$
    – kelalaka
    Dec 15, 2018 at 9:04
  • $\begingroup$ Before considering "How reassuring is 64 quantum bits security", we must define what is 64 quantum bits security. Is that 128-bit key for a good classical symmetric cryptosystem? $\endgroup$
    – fgrieu
    Dec 15, 2018 at 17:16


Your Answer

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

Browse other questions tagged or ask your own question.