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?
1
-
1$\begingroup$ Related question: Are cryptographic hash functions quantum secure? $\endgroup$– Geoffroy CouteauCommented Sep 30, 2021 at 8:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
answered Aug 30, 2021 at 16:32
-
$\begingroup$ @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. $\endgroup$– ponchoCommented Aug 30, 2021 at 17:14
-
$\begingroup$ 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? $\endgroup$– JamesCommented Aug 30, 2021 at 23:36
-
$\begingroup$ 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. $\endgroup$– JamesCommented Aug 30, 2021 at 23:38
-
$\begingroup$ @James These notes 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, which is (roughly) what you are alluding to. $\endgroup$– Mark Schultz-Wu ♦Commented Aug 30, 2021 at 23:56
-
$\begingroup$ @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. $\endgroup$– ponchoCommented Aug 31, 2021 at 2:40