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.
