0
$\begingroup$

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.

Update

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

$\endgroup$
  • 1
    $\begingroup$ Grover's algorithm cannot be efficiently parallelized, so in practice, it may not be all that powerful. $\endgroup$ – forest Dec 15 '18 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 '18 at 9:04
  • $\begingroup$ @kelalaka Yep you're right. There's another answer here on Cryptography which also explains it. $\endgroup$ – forest Dec 15 '18 at 9:05
  • $\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 '18 at 17:16

Your Answer

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

Browse other questions tagged or ask your own question.