4
$\begingroup$

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.)

$\endgroup$

1 Answer 1

3
$\begingroup$

"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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Nov 25, 2021 at 9:52
  • 1
    $\begingroup$ 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). $\endgroup$ Nov 25, 2021 at 14:01
  • $\begingroup$ I see. Yes, such a game hop proof should be easy to construct. Thanks! $\endgroup$ Nov 26, 2021 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.