Score:1

Crypto

Are zk-STARKs really quantum resistant?

James

12/30/22, 12:38 PM

I see lots of mention that zk-STARK proofs that are being developed notably for use in blockchain networks are labelled as "quantum resistant". Many articles and reports that state this, claim such based on the idea that zk-STARKs rely on collision-resistant hashes. My understanding though is that there can never be a perfectly collision-resistant hash - and that it would be trivial for a quantum computer to attempt to find a collision in any hash. Is there some part that I do not understand that does make zk-STARKs quantum resistant?

274

1 + 0

hash

zero-knowledge-proofs

cryptocurrency

Geoffroy Couteau

1/30/23, 8:12 AM

Related question: [Are cryptographic hash functions quantum secure?](https://crypto.stackexchange.com/questions/44386/are-cryptographic-hash-functions-quantum-secure/44390#44390)

Score:1

Crypto

Mark

12/30/22, 4:32 PM

For many hash functions, the best known quantum attacks are based on Grover Search. This speeds up an $O(N)$ operation to $O(\sqrt{N})$, so is a speedup, but only by a "polynomial" factor (it does not speed up an $O(2^N)$ operation to $O(N)$, or something like that).

My understanding though is that there can never be a perfectly collision-resistant hash - and that it would be trivial for a quantum computer to attempt to find a collision in any hash.

The part you do not understand is the second statement. If you have a particular attack in mind (that beats things based on Grover search), you should try working out the details, as it would be a quite nice result.

0 + 5

poncho

12/30/22, 5:14 PM

@James: note that Grover's search is provably within a constant factor (not far from 1) of the provably optimal value, if you view the hash function as an opaque object. Hence, any result you can get significantly better than Grover's will depend on the internals of the hash function itself.

James

12/30/22, 11:36 PM

As classical computers can find a random collision for a hash function in $O(\sqrt{N})$, does that mean both classical and quantum computers take approximately the same number of steps to perform this? Or would Grover's search take $O(\sqrt{\sqrt{N}})$ steps instead for finding a random collision?

James

12/30/22, 11:38 PM

I was also under the impression that quantum computers are able to check more possible outputs per a step dependent on the number of qubits - though my exact knowledge of this area is a bit on the fuzzy side.

Mark

12/30/22, 11:56 PM

@James [These notes](https://www.scottaaronson.com/qclec/24.pdf) make it seem like the answer is $O(N^{1/3})$. Regardless of the precise exponent, quantum computing is not known to get a super-polynomial improvement here. And your second impression is a common misunderstanding of quantum computers. See for example [myth 2 of this article](https://cacm.acm.org/magazines/2019/4/235578-cyber-security-in-the-quantum-era/fulltext), which is (roughly) what you are alluding to.

poncho

12/31/22, 2:40 AM

@Mark: for a collision search, the answer is known to be between $O(N^{1/3})$ and $O(N^{1/2})$. If you count only Oracle queries, then the lower bound is known to be achievable; however that comes with rather high circuitry cost (so high that for practical hash functions, it'd be cheaper to parallelize with an $O(N^{1/2})$ algorithm). It's not known whether there exists a less costly algorithm that achieves (or comes close) to the lower bound.