Topic: 1 quantum computer == 1000 ASICs? (Read 848 times)
Thank you. Now it makes sense to me.
Why does then http://pqcrypto.org/ state that hash-based crypto is QC-resistant? QC number factorization takes O(sqrt(N)) as well.
(1) O(sqrt(N)) is not "broken". It's like saying that O(N2) is crackable but O(N3) is not. They're both polynomial. You just double your key/block sizes once, and you've forever stunted QCs back to where classical computers were. It's quantum-resistant because it's still easy to choose key/block sizes that are secure.
(2) QC number factorization is a different process, and the gains are much more powerful. It's actually turning a super-polynomial problem into a polynomial problem. I.e. factoring numbers on classical computers isn't quite exponential, it's about O(ecuberoot(N)), but is about O(N3) on a quantum computer. The O(ecuberoot(N)) is prohibitive, as it's easy to pick reasonable key sizes that would take billions of years for a classical computer to crack. But O(N3) can't really be outrun. A crypto system that relies on O(N3) being hard is broken.
Why does then http://pqcrypto.org/ state that hash-based crypto is QC-resistant? QC number factorization takes O(sqrt(N)) as well.
From http://arxiv.org/abs/1108.2316 (Merkle Puzzles in a Quantum World):
Bitcoin mining algo can be used as Merkle's Puzzle. Does it mean that a quantum computer can find a nonce much faster (sqrt[X] vs X for a classical computer)? I can't find that paper to check this by myself.
Quote
We showed in an earlier paper that Merkle's schemes are completely insecure against a quantum adversary...
Bitcoin mining algo can be used as Merkle's Puzzle. Does it mean that a quantum computer can find a nonce much faster (sqrt[X] vs X for a classical computer)? I can't find that paper to check this by myself.
Yes, a QC can do a brute force search that normally takes O(N) in O(sqrt(N)). But QCs are going to be a long way from exploiting that advantage until they (1) exist, and (2) are good enough to actually execute "guesses" that fast.
Consider for example that you need approximately 108 operations to brute-force guess something (in this case find a nonce that gives a particular target when hashed). Perhaps your ASIC does 108 guesses/sec, so it takes 1 second. It may only take 104 operations for your QC... but if it can only do 100 ops per sec, you're still far better off with your ASIC.
Of course the math and the scales are far from that simple, but you get the point -- even getting a real QC that has enough qubits and gates to do the calculation may be decades off... and it may be far longer before it can even exploit such an advantage.
(On the other hand, it has a far greater advantage than that against breaking crypto schemes, so even a minimal QC might take minutes/hours/days to break a key, but it's better than the 1032 years it would take a classical computer)
From http://arxiv.org/abs/1108.2316 (Merkle Puzzles in a Quantum World):
Bitcoin mining algo can be used as Merkle's Puzzle. Does it mean that a quantum computer can find a nonce much faster (sqrt[X] vs X for a classical computer)? I can't find that paper to check this by myself.
Quote
We showed in an earlier paper that Merkle's schemes are completely insecure against a quantum adversary...
Bitcoin mining algo can be used as Merkle's Puzzle. Does it mean that a quantum computer can find a nonce much faster (sqrt[X] vs X for a classical computer)? I can't find that paper to check this by myself.
Jump to: