Are There Post-Quantum Secure SNARKS?

Beginner questions
1

I was wondering if anybody knows of post-quantum secure SNARKS. There are some amazing looking projects built on SNARKs, that seem to do much of what I want, such as Aleo, but my biggest deterrent is that I’ve heard that SNARKS are not known to be post-quantum secure.

This feels like a big potential problem. I would be afraid to invest in a cryptocurrency that might become fundamentally flawed and insecure if we discover that Quantum computers can forge proofs.

Is there any way to have a SNARK that is known to be post-quantum secure, or are STARKs the only known quantum secure zero-knowledge proof system that handles arbitrary computation?

2

To be pedantic, we don’t know any SNARKs to be post-quantum secure, just as we don’t know whether one-way functions exist. The best we can do (without a theoretical breakthrough) is state that we don’t know any quantum attacks (faster than Grover’s algorithm) against a certain scheme, or prove security within a theoretical model like the QROM.

Plausibly post-quantum secure SNARKs do exist; most of them use FRI to test polynomial identities rather than algebraic techniques. Fractal is one example. SNARKs like PLONK can be made plausibly post-quantum secure by replacing its pairing-based polynomial commitment scheme with a FRI-based scheme; that’s what we did in Plonky2.

This should be taken with a grain of salt though, since AFAIK, no proofs have been written yet to show the security of these schemes in the QROM or other setting. In fact, AFAIK FRI has no classical security proof for the non-interactive setting.

If we wanted a scheme that’s definitely secure in the QROM, ZKBoo++ has a proof, but it’s not a SNARK since it lacks succinctness.

4 Likes
3

small nit: we do have proofs of security in the QROM for IOP-based SNARKs: Succinct Arguments in the Quantum Random Oracle Model

2 Likes
4

You can say that breaking hashing with quantum computers is a big potential problem, but you can also try to quantify how big a problem it is;

The most efficient theoretical implementation of a quantum computer to detect a SHA-256 collision is actually less efficient than the theorized classical implementation for breaking the standard. The wallet file in the original Bitcoin client is using SHA-512 (a more secure version than SHA-256) to help encrypt private keys.

But besides the probability assessment, I share the conviction that SNARKs can make a difference to privacy, because you only need to share commitments to your protocol, not all protocol data.