What are the characteristics of quantum secure protocol, and does it always need to be information theoretic to be called as quantum secure? Are the current techniques used in bitcoins quantum secure?


Quantum computers don't attack the protocol, they attack the cryptographic primitives used in the protocol. You need to avoid primitives that can be broken by quantum computers.

Quantum computers don't break all computationally secure cryptography, so you don't have to resort to information theoretic algorithms (one-time-pad). Symmetric encryption is secure if the keys are big enough (256 bits). Hashes are secure if the output is big enough (256 bits might be enough). Popular asymmetric crypto including RSA, Diffie-Hellman and DSA (including elliptic curve equivalents) will become totally insecure, but there are replacements.

The biggest problem QCs pose for bitcoin is that it uses ECDSA to control ownership of coins. Since QCs can break DSA, everybody who learns your public-key can compute the corresponding private key and steal your coins. Keeping single-use public-keys secret until use can help somewhat, but it's still problematic.

Grover's algorithm might cause some additional issues, including faster mining, $2^{80}$ pre-image attacks against the 160-bit hashes used for bitcoin addresses and faster cracking of weak passphrases for password derived keys.

  • 1
    $\begingroup$ Can you elaborate on why you say 256 bits might be enough for the output of a hash to be secure against quantum computers. Constructing a collision for a 160 bit hash by classical brute force is within reach already today. I would expect the output needed to withstand quantum computing be twice that needed to withstand classical attacks. $\endgroup$ – kasperd Nov 24 '16 at 23:56
  • 1
    $\begingroup$ @kasperd 1) It's a meet-in-the-middle attack, so the equivalent of grover reduces the cost to $2^{1/3}$ from $2^{1/2}$, so you'd still have 85 bits of security. If you want 128 bits of security, you only need 384 bits of output, not 512. 2) Bernstein argues that the memory access circuitry for that quantum algorithm would bring up the cost beyond the cost of classic collision finders. But I don't know if he overlooked something. $\endgroup$ – CodesInChaos Nov 25 '16 at 8:05
  • $\begingroup$ @kasperd Generating a collision with a 160-bit hash can be made extremely parallel, whereas Grover's algorithm does not scale nearly as well. It only achieves the optimal speedups if run completely serial. $\endgroup$ – forest Mar 7 '19 at 12:45

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.