Creating Your Own Proof Primitives¶
You can also define your own proof primitives and use them in new proofs. The library uses this technique to define several proof primitives. In this guide we will see how to define our own primitives.
A Primitive for Proving Knowledge of an ElGamal Plaintext¶
We start with a simple new primitive. Consider an additive ElGamal ciphertext
for a group with generator \(G\) and public key \(H = xG\). The owner of the private key \(x\) can decrypt the ciphertext by computing
and then finding \(m\) through trial and error, a lookup table, or a discrete-logarithm finding algorithm such as the baby-step giant-step algorithm.
We construct a new primitive that proves that the creator of the ciphertext \(c\) knows the encrypted message \(m\) and the randomizer \(r\). In Camenisch-Stadler notation:
The first step in defining a new primitive is to determine its inputs and
secrets. In this case, the public input is the ciphertext \(c\) and a public
key pk
containing the points \(G\) and \(H\). Moreover, the prover
has two secrets, the message \(m\) and the randomizer \(r\). To define a
new primitive with these parameters, we inherit from zksk.extended.ExtendedProofStmt
. The
constructor simply stores the values we pass.
class AdditiveElgamalPlaintextProof(ExtendedProofStmt):
def __init__(self, ctxt, pk, msg, randomizer):
self.ctxt = ctxt
self.pk = pk
self.msg = msg
self.randomizer = randomizer
Next, we define which statement corresponds to our new primitive.
def construct_stmt(self, precommitment):
part1 = DLRep(self.ctxt[0], self.randomizer * self.pk.g)
part2 = DLRep(self.ctxt[1], self.randomizer * self.pk.h + self.msg * self.pk.g)
return part1 & part2
Which is a direct translation of the Camenisch-Stadler notation defined above. This function must
take an extra argument precommitment
. But this argument is not used here.
A Primitive for Proving Inequality of Discrete Logarithms¶
The previous primitive was very simple. We can also define more complicated primitives. In this section we show how to construct a primitive for proving that two discrete logarithms are not equal:
\[PK\{ (x): H_0 = x \cdot h_0 \land H_1 \neq x \cdot h_1 \}\]
or in words, that the discrete logarithm of \(H_0\) with respect to \(h_0\) is not equal to the discrete logarithm of \(H_1\) with respect to \(h_1\).
Let \(x\) be the private input of the prover such that \(H_0 = x \cdot h_0\). To prove the above statement in zero-knowledge, we must proceed as follows [HG13]:
The prover picks a blinding factor \(r\), computes the auxiliary commitment \(C = r (x h_1 - H_1)\), and sends \(C\) to the verifier.
The prover and the verifier then engage in the zero-knowledge proof
\[PK\{ (\alpha, \beta): 1 = \alpha \cdot h_0 + \beta \cdot H_0 \land C = \alpha \cdot h_1 + \beta \cdot H_1 \},\]where the prover uses \(\alpha = x r \mod q\) and \(\beta = -r \mod q\).
Finally, the verifier accepts if the proof in step 2 succeeds, and if the commitment \(C \neq 1\).
This protocol is indeed a zero-knowledge proof. And, by combining steps 1 and 3
into step 2, can be seen as a Sigma protocol. Internally, we still use a
standard sigma protocol. However, we notice two major changes. First, the prover
precomputes a commitment, that then becomes part of the constructed proof
statement. Second, after verifying the constructed proof, the verifier needs to
perform another verification. The zksk.extended.ExtendedProofStmt
class allows us to define
the extra steps.
We again first determine the inputs to the primitive. The public inputs are the
pairs \((H_0, h_0)\) and \((H_1, h_1)\). The prover takes as private
input the secret \(x\) such that \(H_0 = x \cdot h_0\). Again we
override zksk.extended.ExtendedProofStmt
and store the inputs:
class DLNotEqual(ExtendedProofStmt):
def __init__(self, valid_tuple, invalid_tuple, x):
self.lhs = [valid_tuple[0], invalid_tuple[0]]
self.generators = [valid_tuple[1], invalid_tuple[1]]
self.x = x
# The internal ZK proof uses two constructed secrets
self.alpha, self.beta = Secret(), Secret()
Note that the constructor also defines the secrets alpha
and beta
that
will be used in the constructed proof from step 2 above. To compute the
commitment \(C\) we override the precommit(self)
method to compute a
precommitment containing \(C\):
def precommit(self):
order = self.generators[0].group.order()
blinder = order.random()
# Set the value of the two internal secrets
self.alpha.value = self.x.value * blinder % order
self.beta.value = -blinder % order
precommitment = blinder * (self.x.value * self.generators[1] - self.lhs[1])
return precommitment
Recall from before that the secrets \(\alpha\) and \(\beta\) depend on the user’s secret \(x\) and the randomizer \(r\) we use to compute the commitment. Since we now know all these values, we can compute the real values of the constructed secrets \(\alpha\) and \(\beta\), and store them.
For simplicity, precommitment
is a single group element here. However, in
bigger primitives, it might make more sense to define it as a dictionary
instead. In fact, any object would work, as long as it is serializable.
The precommit(self)
method is only called by the prover. The verifier will
integrate the precommitment from the prover before constructing the proof
statement. As above, we override construct_stmt(self, precommitment)
to
define how to do so:
def construct_stmt(self, precommitment):
infty = self.generators[0].group.infinite()
p1 = DLRep(infty, self.alpha * self.generators[0] + self.beta * self.lhs[0])
p2 = DLRep(precommitment, self.alpha * self.generators[1] + self.beta * self.lhs[1])
return p1 & p2
Note that the constructed proof is a straightforward interpretation of the zero-knowledge proof from step 2 above. When using our new primitive, the prover and verifier will now automatically prove respectively verify the constructed proof that we just defined.
Finally, the verifier must ensure that the commitment \(C\) is not the
identity element. To ensure that, we additionally override validate(self)
:
def validate(self, precommitment):
if precommitment == self.generators[0].group.infinite():
raise ValidationError("Invalid precommitment")
If defined, the verifier will run the checks in validate
before accepting
the proof. And that is it, our new primitive can now be used in bigger proofs.
The full implementation in the library of
zksk.primitives.dl_notequal.DLNotEqual
is a little bit more
complicated. Note that in the above protocol, the secret x
is not actually
used directly in the proof. The full version allows explicit binding of the
secret x
.
Enabling Simulations¶
If a new primitive only overrides construct_stmt
then simulations are automatically enabled.
However, the library cannot always compute a legitimate precommitment by itself. Therefore, it is
necessary to override simulate_precommit(self)
to enable proper simulations.
For example, in the above proof of inequality of discrete logarithms the commitment \(C\) is just a random group element. Therefore, we can set:
def simulate_precommit(self):
group = self.generators[0].group
precommitment = group.order().random() * group.generator()
return precommitment
- HG13
R. Henry and I. Goldberg, “Thinking inside the BLAC box: smarter protocols for faster anonymous blacklisting,” in Proceedings of the 12th ACM workshop on Workshop on privacy in the electronic society. ACM, 2013, pp. 71–82.