1
$\begingroup$

Suppose that Peggy(prover) and Victor(verifier) are running some zero knowledge proof protocol that does not rely on hidden verifier secrets. The verifier generates randomly chosen challenge values only. Such protocols can be Fiat-Shamir transformed into NI(non-interactive)ZKPs.

There is significant work on NIZKPs. Using them as-is in contexts where deniability is necessary would be nice, but as-is, a dishonest verifier can replace themselves with a deterministic random oracle (EG:Hash function, keyed HMAC, etc.) to generate a non-interactive proof and deniability is lost.

As a simple example, they might be performing the Schnorr Identification protocol where Peggy proves knowledge of a discrete logarithm for a point Y by providing a scalar s that satisfies R=eY+sG for a challenge scalar e provided by Victor.

  • P-->V Y,R
  • V-->P e
  • p-->V s
  • V(verifies R=eY+sG)

Victor could, instead of choosing e at random he computes e=SHA256(Y,R). The resulting transcript (Y,R,e,s) is a non-interactive proof that somebody knows the discrete log of Y.

How can a ZKP that can be Fiat-Shamir transformed be made deniable even when performed with a dishonest verifier?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Note:All the math in this answer assumes

  • prime order finite field with generator G
  • Capital letters are group elements (EG: P,Q)
  • lowercase letters are scalars. (EG: s,t)
  • Additive notation.

A non interactive zero knowledge proof can be forged if Peggy is allowed to modify random oracle outputs. In the case of the Schnorr identification protocol if Peggy can change e to a value of her choosing she can trivially find an (R,e) pair that satisfy the verification equation.

To provide deniability, a public coin protocol can be made deniable if Victor pre-commits to all his random challenge values. Taking the Schnorr identification protocol as an example, if Victor commits to a challenge e before the protocol starts, he can't choose it deterministically based on Peggy's initial statement R so he cannot apply the Fiat-Shamir heuristic to generate a non-interactive proof.

Deniable (mostly) non-interactive proofs

For more complex multi-round proof systems, efficiency can be improved by having Peggy produce a non-interactive proof that is easy to forge unless Victor keeps a pre-commited challenge value secret. We take a function for generating non-interactive zero knowledge proofs prove(input_data)--> proof and modify it prove_deniable(salt,input_data,T[n])-->proof. This function takes two additional parameters, a salt value to be added to the beginning of the transcript and a vector T[n] of values which modify random oracle outputs allowing forgery. In the non-interactive Schnorr proof where R=e*Y+s*G the challenge of e=SHA256(Y,R) or similar becomes e=SHA256(salt,Y,R)+T[0] to depend on the salt and allow modification using the first value in the T[n] array.

The interactive protocol operates as follows:

  • Victor: generate random salt
  • V-->P: commit(salt)
  • Peggy: generate random list of values T[n]
  • P-->V: commit(T[n])
  • V-->P: salt
  • Peggy: compute proof=prove_deniable(salt,input_data,T[n])
  • P-->V: T[n],proof

Victor's salt value is added to the beginning of the NIZKP transcript and influences all random oracle outputs. Peggy must choose and commit to her T[n] values before knowing this and so cannot forge the NIZKP. If Victor and Peggy collude, or if a forger creates a forged transcript of such a protocol, they can choose T[n] after choosing the salt value to create a forgery.

Designated verifier proofs

Designated Verifier proofs do something similar but non-interactively. A trapdoor function based on a public key held by Victor is used to allow the holder of the private key to generate T[n] independently of the salt, which is otherwise dependent on the chosen T[n] values.

Consider a Pedersen commitment C=m*G+r*Y where Y=x*G is Victor's public key. Victor can trivially open a commitment to reveal any message but Peggy who does not know x cannot.

Peggy generates m=Hash(T[n]) for a randomly chosen T[n] vector, salt = C = m*G+r*Y for a random r, and proof=prove_deniable(salt,input_data,T[n]) and sends Victor the tuple (T[n],r,proof).

Victor can choose a commitment value C=k*G find an m=Hash(T[n]) that creates a forged proof, then calculate r=(k-m)/x that opens the commitment to the chosen value m.

So either the proof is honest or Victor created a forgery.

To prevent verification by third parties who might trust Victor not to forge a proof, assuming we take the "knowledge of exponent assumption"(IE:ECDH is secure), Peggy can do something like a DH key exchange to prove knowledge of r. For a commitment C=m*G+r*Y, she calculates P=r*G sending (C,m,P) to Victor. Victor finds the value of the r*Y term in the above equation r*Y = Q = C-m*G and checks that Q = P*x.

Note: Q = P*x --> (r*Y)=(r*G)*x --> r*x*G = r*x*G.

Short lived proofs based on verifiable delay functions

Similar constructions are also possible using verifiable delay functions. This uses a trusted random number generating beacon whose output must be run through a VDF requiring n sequential computation steps to forge the proof. If Victor sees such a proof before anyone could have performed the computation on that beacon value, he knows the proof was not forged.

Reducing implementation effort by chaining deniable and non-deniable proofs

Modifying a complex proof to be deniable in the above way is hard. It's much easier from an implementation standpoint to deniably prove a simpler statement (EG:this Pedersen commitment opens to m, I know x such that P=x*H, etc.). If the values used in the complex proof are homomorphic this can be used to make that proof deniable.

Instead of doing a range proof that 0≤x<2^64 for the Pedersen commitment C=x*G+r*H prove knowledge of p such that P=p*H deniably and do the range proof on C'=C+P. Without knowing P was generated honestly the range proof on C' is worthless. This makes re-using existing proof code much easier. I wouldn't want to mess around with the code for bulletproofs for example but the above is very simple to implement.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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