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

\[c = (c_1, c_2) = (rG, rH + mG)\]

for a group with generator \(G\) and public key \(H = xG\). The owner of the private key \(x\) can decrypt the ciphertext by computing

\[T = c_2 - x \cdot c_1 = mG\]

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:

\[PK\{ (x, r) : c_1 = r G \land c_2 = r H + m G \}.\]

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 = 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 *
        part2 = DLRep(self.ctxt[1], self.randomizer * + self.msg *
        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]:

  1. The prover picks a blinding factor \(r\), computes the auxiliary commitment \(C = r (x h_1 - H_1)\), and sends \(C\) to the verifier.

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

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

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.