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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ I'd assume a protocol is quantum-secure if it secure against standard polynomial attackers and attackers with quantum computing abilities. $\endgroup$– SEJPMNov 24, 2016 at 10:25
-
$\begingroup$ Related: How will Cryptography be changed by Quantum Computing? $\endgroup$– CodesInChaosNov 24, 2016 at 11:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Nov 24, 2016 at 11:55
-
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$– kasperdNov 24, 2016 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$ Nov 25, 2016 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, 2019 at 12:45