1 quantum computer == 1000 ASICs?

[Come-from-Beyond]

From http://arxiv.org/abs/1108.2316 (Merkle Puzzles in a Quantum World):

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.

[etotheipi]

From http://arxiv.org/abs/1108.2316 (Merkle Puzzles in a Quantum World):

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 10⁸ operations to brute-force guess something (in this case find a nonce that gives a particular target when hashed).  Perhaps your ASIC does 10⁸ guesses/sec, so it takes 1 second.  It may only take 10⁴ 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 10³² years it would take a classical computer)

[Come-from-Beyond]

Why does then http://pqcrypto.org/ state that hash-based crypto is QC-resistant? QC number factorization takes O(sqrt(N)) as well.

[etotheipi]

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(N²) is crackable but O(N³) 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(e^cuberoot(N)), but is about O(N³) on a quantum computer.  The O(e^cuberoot(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(N³) can't really be outrun.  A crypto system that relies on O(N³) being hard is broken.

[Come-from-Beyond]

Thank you. Now it makes sense to me.