Why are zk-STARK quantum secure?

Question

I have a rough idea of how STARK work, but I want to know which part makes them quantum secure. Is it because when the prover generates the proof they use the random number from the Merkle root, which cannot be guessed by a quantum algorithm?

Answer 1

The only cryptographic primitive required for a zk-STARK is a cryptographically secure hash function, which we will denote $H$. Known quantum vulnerable forms of cryptography all depend on some other cryptographic primitive.

To prevent the generation of invalid proofs, the hash function $H$ needs to be pre-image resistant i.e. for a target output $y$ it should be hard to find an input $x$ such that $H(x)=y$. Now, if we know nothing about the function $H$ beyond the outputs that it produces, this is an example of an unstructured search problem that can be solved by Grover's algorithm on a sufficiently large and stable quantum computer in time roughly proportional to the square root of the image space. Indeed we know that Grover's algorithm is essentially the best possible approach to such problems. However, Grover's algorithm is highly non-parallelisable (to perform the search in 1/10 of the time we have to use 100x quantum computers) and it is argued that searching for solutions to 256-bit image spaces is not going to be possible for any reasonable projection of quantum computing capability.

In practice, a hash function such as SHA256 is used in zk-STARKs for which we know the full computational details. Nevertheless, no-one has been able to demonstrate any structure within SHA256 that will lead to an approach superior to the Grover approach. Faith in the strength of SHA256 is such that it is used as one of the benchmarks in the NIST post-quantum cryptography process (level 2 security is defined as taking no less resources to break than finding a SHA256 collision; see the call for proposals section 4.A.5).

Even if SHA256 did display evidence of structure that allows superior attacks to Grover, there are many other hash functions that could be easily integrated into the zk-STARK framework. For all of these reasons, there is high confidence in the quantum safety of the zk-STARK framework.