Defeating Quantum Algorithms with Hash Functions | Hacker News Reader

Defeating Quantum Algorithms with Hash Functions

research.kudelskisecurity.com

74 pointssigna1119 comments

> Furthermore, we know what the quantum collision-finding algorithm is optimal—no faster algorithm can be found.

There's two problems with this:

First, I'm not aware of any proof that Brassard et al.'s algorithm is optimal. Grover's algorithm is optimal, but it is optimal for searching for a specific output value given an arbitrary function. Obviously this optimality doesn't carry over to collision finding because Brassard et al.'s algorithm is superior to a naive use of Grover's for that purpose!

Second, even if Brassard's algorithm is optimal in the usual sense, it would be optimal if given an arbitrary function. Specific weaknesses in specific hash functions could still result in methods that would beat it.

If you could prove it was the best method for finding hash collisions, even against algorithms designed for specific hash functions, you would have to conclude that the best way to break MD5 on a quantum computer is Brassard's algorithm. That would be a big problem, since we already have better classical methods, and classical algorithms transfer trivially to quantum computers (with the same asymptotic properties). Someone's proof would have to be inconsistent, or ZFC would have to be inconsistent or something crazy like that!

"First, I'm not aware of any proof that Brassard et al.'s algorithm is optimal."

Also, it's really not clear from this post why you can't play the same kind of parallelization game.

(IE if the underlying thing it provides is a faster way to do x, why can't you parallelize that x in the same way)

Actually, it looks like bernstein points out you can do this, so the author of this post is essentially comparing a crappy technique to a good one, and saying "The good one is better".

It turns out they are the same in the end and it's just cheaper to build normal machines than quantum ones. That seems more reasonable to me than "this technique is slower than the best classical one". It's not. It's just cheaper. That's all.

He also says bernstein brilliantly explains why even better quantum algorithms will never win, but actually, bernstein just conjectures that :)

" there are several obvious ways to combine quantum search with the rho method, but I have not found any such combinations that improve performance, and I conjecture that—in a suitable generic model—no such improvements are possible."

That's a pretty easy conjecture to always make - "i haven't found a way to make this faster, so i conjecture a way to make it faster doesn't exist". These types of conjectures are often very wrong, which is why we have proofs ;)

While quantum computers are of limited use in inverting a hash function (which remains infeasible for 256-bit hash functions), they would be a tremendous boon for cryptocurrency mining on a Hashcash proof-of-work system, such as the one used in bitcoin. In fact this is an obvious application of Grover's algorithm [1] that can find an input x satisfying a predicate P(x) in time O(sqrt(N)) where N is the domain size of P. The predicate P in this case is just that SHA256(SHA256(x)) < difficulty_target, while N is about 2^70 at the current difficulty level.

This gives a nice speedup, even if the quantum computer cycle time is a million times slower. As a result, mining would centralize to outfits having the most advanced quantum hashing chips.

Of course this ignores the bigger issue bitcoin would have with its signature scheme being completely broken on quantum computers, rendering all exposed public keys unsafe (addresses, being hashes of public keys, remain safe until spent though; hence the recommendation against address re-use).

[1] https://en.wikipedia.org/wiki/Grover's_algorithm

> they would be a tremendous boon for cryptocurrency mining

Only for the miner's short-term self-interest. If quantum computers become practical (e.g. a few states and organisations have one, of sufficient size/speed to beat contemporary classical setups on some problems), then I would imagine a sharp drop in value for any cryptocurrencies whose proof-of-work is vulnerable to known quantum shortcuts.

So by a "tremendous boon to cryptocurrency mining" you actually mean completely disastrous to all known cryptocurrencies.

It will be interesting to see if someday the prospect of effective quantum computers has a definite economic effect on the value of bitcoin or its successors. I don't imagine currencies work very well when they have an expiration date.

Is this all still totally hype? Anything close to practical? Wikipedia[1] shows:

   year 2001: factor 15
   year 2011: factor 21
   year 2011: factor 143

At that rate of progress we might be able to factor something useful before we reach the heat death of the universe. But I guess the topic is good for lots of scary headlines.

[1] https://en.wikipedia.org/wiki/Quantum_computing

Since how long it's going to take to have a potent Shor's algorithm machine is mostly a matter of when and in what series a set of novel advances occur in a range of fields (physics and mathematics at least), there's a lot of uncertainty as to when that ball is going to drop. Given that, and how long it takes to get rid of legacy crypto even when we know it's dead as a doornail, and how long it takes to vet a cryptographic algorithm, I think there's no time like the present to get started on post-quantum crypto.

there's no time like the present to get started on post-quantum crypto

You present an interesting argument.

HOWEVER, the cynic in me questions why the NSA made similar arguments not too long ago. Is it because if everyone switches to new algorithms there will be myriad new code, with a plethora of new bugs? Won't it make NSA's life much much easier for years to come? How many years did it take us to find "goto fail; goto fail;"?

Nobody is arguing switching production systems to the new algorithms anytime remotely soon. The closest I've heard of is Google adding a mixed ECC/post-quantum crypto algorithm in Chrome's Canary (bleeding edge channel)[1], but the whole point of the construction is that you need to break both (or break XOR, I guess :P). As far as I can tell, we're still in the early "is this algorithm any good" stage as opposed to the "did we implement the algorithm right" stage.

More generally, its pretty easy to turn any security recommendation by the NSA into a plot (they recommend SHA-3 cause they broke it and not SHA-2!). I'd save my suspicion for cases where they (a) give advice contrary to independent experts or (b) give strangely specific guidance with no apparent rationale.

[1]: https://security.googleblog.com/2016/07/experimenting-with-p...

We are a very long way away from having quantum factorization of integers. Quantum computers will be more useful for things like chemistry problems in the near term.

Although articles like this

https://phys.org/news/2017-02-blueprint-unveiled-large-scale...

make it seem we're getting much closer...

It will be physics papers demonstrating stability that should get your hopes up, not signal delivery "blueprints", unfortunately.

Yep. If anyone is interested, here is a recent result where the electrical structure of a hydrogen molecule was simulated:

https://arxiv.org/abs/1512.06860

A lot of the "progress" is masked by a "Wirth's law"-style effect related to the requirement for quantum error-correction in order to carry out long quantum computations. Briefly, a quantum memory can never be perfectly accurate, and the limit of known physical implementations is close to 1 error in 1000 "clock cycles". In order to overcome this, error-correction is required, which creates overhead. The long-term outlook is still generally positive.

"In November 2014, it was discovered that this 2012 adiabatic quantum computation had also factored larger numbers, the largest being 56153." [1]

[1] https://en.wikipedia.org/wiki/Shor%27s_algorithm#cite_ref-10

One problem with scaling quantum computers is that while the individual qbits are small getting more and more stable, it is unclear how to miniaturize the stuff needed to read and write qubits. Those are still components you can touch with your hands without breaking them, so you can't have millions in one device.

The greatest minds in computer science worked out the math and theory long before the tech became practical.

There is value in the theory and I think some of us enjoy it, even if it's not practical.

There will be a very fast turning point when people find a way to put large numbers of qubits together

shameless plug, a 4 parts blog series on hash-based signatures: http://cryptologie.net/article/306/hash-based-signatures-par...

Reply on news.ycombinator.com