Note:All the math in this answer assumes
- prime order finite field with generator
- Capital letters are group elements (EG:
- lowercase letters are scalars. (EG:
- 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 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
- Peggy: generate random list of values
- Peggy: compute
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
Consider a Pedersen commitment
Y=x*G is Victor's public key. Victor can trivially open a commitment to reveal any message but Peggy who does not know
m=Hash(T[n]) for a randomly chosen
salt = C = m*G+r*Y for a random
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
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
(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.
Q = P*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.