Are There Post-Quantum Secure SNARKS?

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?

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.

3 Likes

small nit: we do have proofs of security in the QROM for IOP-based SNARKs: Cryptology ePrint Archive: Report 2019/834 - Succinct Arguments in the Quantum Random Oracle Model

2 Likes