[zb3]

> to create a powerful new tool in cryptography.

What is that new powerful tool in cryptography, then?

> He wanted to build zero-knowledge proofs that weren’t interactive. Thirty years earlier, Goldreich and Oren had established that such proofs are impossible.

I'm not sure what "interactive" means here, but I thought ZK-SNARKs were already non-interactive.

It seems the article has nothing to do with anything practical..

[twotwotwo]

The fielded systems require something that wasn't there in the original model of zero-knowledge proofs. That could be as little as a trusted-enough public source of randomness: the prover makes their initial commitments, plays the verification game with a verifier whose challenges are controlled by the next outputs of the public RNG, and as long as the other party trusts that the RNG and prover aren't in cahoots, that's enough. Doing a trusted setup process beforehand is another tool used by a bunch of deployed systems.

That doesn't mean anything's practically wrong with the fielded ZK proof systems, just that's how you reconcile the article's "no non-interactive proofs under these assumptions" with people out in the real world using non-interactive proofs.

This paper brings up another logical possibility, that there could be a non-interactive proof with no RNG or setup that doesn't meet the precise original definition of zero-knowledge proofs but is zero-knowledge practically speaking. I don't know whether we'll actually see better fielded ZK proof systems come out of this approach!

[Ar-Curunir]

The result is indeed theoretical, but is a big advancement in theory.

zkSNARKs (and other “non-interactive” proof systems) are actually secretly interactive because they all require a setup phase, which effectively counts as the first verifier message. The provers response is then the second message, making the entire process interactive.

This work eliminates that setup phase entirely, leaving only the provers message. The resulting protocol is hence truly non interactive

[less_less]

Cryptographer here, but this is not my area and I've only skimmed the paper. As far as I can tell, it's a purely theoretical result but a really cool one. Wall of text that might be wrong, as a rough summary of the result as I understand it:

There are different definitions of "zk", of "proof". Eg do "proofs" of false statements not exist, or are they just hard to find? If they exist but are hard to find, then it's often called an "argument" instead, which is the "AR" in zk-SNARKs and zk-STARKs.

One common definition of zero-knowledge protocols is that you can make an efficient simulator that makes convincing transcripts of the protocol without knowing the relevant secret (up to and including whether the statement to be proved/argued is even true). For interactive proofs, the simulator is usually supposed to output a transcript of the messages sent between the prover and the verifier, and the trick to making the simulator work is to choose later messages before earlier ones (e.g. challenges before commitments). But in non-interactive proofs, there's only one message, so that trick doesn't work and the simulator would have to output the proof itself.

The Goldreich-Oren result shows that this definition of ZK conflicts with soundness, unless the type of problem you're doing ZK proofs for was easy to begin with. IIUC this is for a simple reason: if a simulator can efficiently output a convincing proof of any true statement of the type your zk proof system covers (this is the zero-knowledge property); and if for false statements there is no proof that will convince the verifier (soundness); then you have an efficient algorithm for checking whether the statement is true or not, which is just to check whether your simulator convinces the verifier. This means that the underlying problem is by definition easy, so there's not much point to having zk proofs for it.

Goldreich-Oren doesn't apply to zk-SNARKs or zk-STARKs, because they are not perfectly sound, and in particular because you can get around the impossibility using the trusted setup in zk-SNARKs (essentially a secret key that lets you efficiently prove false statements) and/or by messing around with the random oracle model (pretend that the hash functions are replaced by magic, and then let the simulator tinker with that magic). Also zk-S?ARKs are arguments of knowledge (not just e.g. "a discrete log of this point exists" but "the prover knows the discrete log") which also changes the model.

As I understand it, the new result is basically to make your proof a NIWI-proof ("Non-Interactive Witness Indistinguishable proof", a weaker notion of zk-proof) that:

* Either [real statement you're trying to prove]

* or else [false statement that's almost impossible to prove false], e.g. "there are contradictions in your axiom system".

Such a proof can be made perfectly sound, since NIWI can be perfectly sound, and the second half is supposed to be false. There's no simulator, but if the false statement were true then there would be a simulator, where you always feed the NIWI eg a contradiction in the axiom system, instead of a proof of the real statement. (The definition of NIWI is that it should be hard to distinguish the proof resulting from these two cases.) The new paper also argues that this result, where there's no simulator but it's hard to prove that there's no simulator, is almost as good as the simulator actually existing.

Probably in practice you wouldn't do this, but you would instead try to make sure that a zk-SNARK, zk-STARK, NIWI etc is good enough in your use case.

[Ar-Curunir]

Goldreich-Oren still applies to NIZKs and SNARKs; the setup phase is the first verifier message. Even in SNARKs with transparent setup (eg, STARKs), the randomness used in the setup phase counts as the firstverifier message.

[less_less]

Ah, thanks for the correction. Do I have the soundness bit right? I guess it might apply even if the proof system is only computationally sound, since the simulator has to be efficient, right?

[realo]

Ah... Purely theoretical result.

Thank you!

I was searching for the github repo with a cool example encrypt/decrypt.

Silly me.

[newsicanuse]

Typical of Quanta magazine

[calmbonsai]

You are correct. I suspect Quanta just needed some sort of "math filler".