Join Log in
Score:4
Anakin Charles avatar Crypto

Groth16 simulate zero-knowledge proof for invalid statement

mx flag
Anakin Charles

The zero-knowledge property of the Groth16 (https://eprint.iacr.org/2016/260, page 8) non-interactive zero-knowledge argument is based on the existence of a simulator $\text{Sim}$ generating "fake" proofs for valid statements $(\phi, w) \in R$ without knowledge of the witness $w$ for statement $\phi$.

My question is whether for Groth16 there also exists a simulator $\text{Sim}'$ to generate "fake" proofs for invalid statements $\phi'$, for which no witness $w'$ with $(\phi', w') \in R$ exists. Formally, does Groth16 satisfy the following notion?

Fake zero-knowledge: For all $\lambda \in \mathbb{N}, (R, z) \gets \mathcal{R}(1^\lambda), (\phi, w) \in R$, all $\phi'$, and all adversaries $\mathcal{A}$: $Pr[(\sigma, \tau) \gets \text{Setup}(R); \pi \gets \text{Prove}(R, \sigma, \phi, w): \mathcal{A}(R, z, \sigma, \tau, \pi) = 1] = Pr[(\sigma, \tau) \gets \text{Setup}(R); \pi \gets \text{Sim}'(R, \tau, \phi'): \mathcal{A}(R, z, \sigma, \tau, \pi) = 1]$

Any answer would be helpful, including a proof for fake zero-knowledge of Groth16 or other schemes, definitions of similar but different notions, or an impossibility result.

(I'm trying to construct a security proof where generating such fake proofs seems necessary. I've never seen the notion above, but it seems to me that $\text{Sim}'$ should exist for some schemes.)

101
0 + 0
Score:3
Geoffroy Couteau avatar Crypto
cn flag
Geoffroy Couteau

"Fake zero-knowledge" always follows from the conjunction of two properties:

  • Standard zero-knowledge: there exists a Simulator Sim that can generate proofs (indistinguishable from honest proofs) for valid statements, and

  • Hard subset membership: there is a sampling algorithm for the language, and randomly sampled wrong statements are indistinguishable from randomly sampled true statements (variants of the notion also exist).

Combining the above gives the "right" notion for "fake zero-knowledge": sampling a true statement and constructing an honest NIZK for it is indistinguishable from sampling a false statement and simulating an NIZK for it.

Note 1

The notion of fake zero-knowledge in your question is different (it makes no reference to a sampling algorithm for the language): you are saying that for any true statement $(\phi, w)$ and any false statement $\phi'$, honest NIZKs with $(\phi,w)$ should be indistinguishable from simulated NIZKs with $\phi'$. This is way too strong, and it can never hold. The reason is that the attack algorithm $\mathcal{A}$ can have $\phi, \phi'$ hardcoded in its description (since the property is for all $\phi,\phi'$ and all adversaries $\mathcal{A}$) and can simply try the verification algorithm on the NIZK. Now, since the verification algorithm takes $\phi$ (or $\phi'$) as input, the adversary will always distinguish the two situations (if verification passes with $\phi'$, it was a fake proof, else it was a real proof; note that by soundness, the verification of a real proof generated by a honest prover cannot possibly succeed with respect to an invalid statement $\phi'$, hence the distinguishing attack I just described works with overwhelming probability).

Note 2

Hard subset membership is necessary for "fake zero-knowledge": if it is not hard to distinguish true statements from wrong statements, we cannot formulate any useful and non-trivial notion of fake zero-knowledge. But it holds for most cryptographic languages of interest - usually, we are interested in making NIZKs for statements that the verifier could not verify by herself anyway.

0 + 0
Anakin Charles avatar
mx flag
Anakin Charles
Thanks, I see why my proposed notion is too strong. As you say "always follows": is there a reference showing that standard-zk + hard-subset-membership allows for simulated proofs of fake statements?
0
Reply
Geoffroy Couteau avatar
cn flag
Geoffroy Couteau
I can't think of a standard reference on top of my head, it's more of a folklore direct observation. If you write the definition of hard subset membership and zero knowledge, then "fake zero knowledge" follows immediately by sequentially applying both: start with a honest proof on a true statement, first apply zero-knowledge to replace the prover by a simulator, then apply hard subset membership to indistinguishably switch the true statement to a false statement (which can be done at this stage because Sim does not require the witness).
1
Reply
Anakin Charles avatar
mx flag
Anakin Charles
I see. Yes, such a game hop proof should be easy to construct. Thanks!
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.