28 February 2023

Speedrunner: Ying Tong

Title: ZKBoo: Faster Zero-Knowledge for Boolean Circuits
Authors: Irene Giacomelli, Jesper Madsen, Claudio Orlandi
Links: [paper], [code]
TL;DR: ZKBoo is a zero-knowledge protocol that makes use of the MPC-in-the-head paradigm [IKOS07] to achieve fast proving times for Boolean circuits. Experimental benchmarks in the paper show that the ZKBoo prover runs approximately 1000 times faster than Pinocchio's [PHGR16] for the SHA-1 circuit.

is the first efficient instantiation of the MPC-in-the-head paradigm [IKOS07]. Compared to pairing-based SNARKs, it achieves a concretely fast prover for large Boolean circuits such as hash computation, at the cost of a linear-size proof. (A later optimisation ++ [Chase⁺ 2016] reduces this proof size by more than half.)

Since its introduction, has been used to construct post-quantum signature schemes [Chase⁺ 2016], blind certificate authorities [Wang⁺ 2019], and cross-domain zero-knowledge proofs [Backes⁺ 2019].

Construction

To prove the correct computation of a function , the prover decomposes it such that subsets of the computation can be checked, without revealing any information about the input. (In a normal MPC protocol, each subset of the computation would be performed on a separate server.) The zero-knowledge proof protocol involves generalising the "commit-challenge-response" (i.e. -protocol) structure described in IKOS [IKOS07] to work for circuit decompositions.

(2,3)-function decomposition

Given a boolean circuit that computes , creates an --- circuit decomposition of three branches. This decomposition must satisfy 2-privacy, which means that revealing the views of any two players does not leak information about the witness .

Let , and be three uniformly random tapes corresponding to players , and respectively. The decomposition consists of the algorithms:

• : samples random shares , which are the initial views for each player, such that .
• : computes the wire values for the next gate and updates the view accordingly.
• : takes as input the final view, , and outputs the player 's output share, .
• : takes as input the three output shares and reconstructs the circuit's final output .

The gate-specific operations are adapted here from [Chase⁺ 2016]. The notation refers to the value of the -th wire in 's view:

Gate: Addition by constant

Only updates their view in the case of addition by constant:

Correctness
To see that this is a correct decomposition, observe that:

Gate: Multiplication by constant

Multiplication by constant can be done locally by each player, without requiring other players' shares:

Correctness
To see that this is a correct decomposition, observe that:

Gate: Binary addition

Binary addition can be done locally by each player, without requiring other players' shares:

Correctness
To see that this is a correct decomposition, observe that:

Gate: Binary multiplication

This is the only gate that requires input from multiple parties.

where is the -th output of a pseudorandom generator seeded with .

Correctness
To see that this is a correct decomposition, observe that:

NB: The trick is to recall that index values are computed : when going from the first line to the second line of the derivation, note that .

IKOS protocol ( variant)

The IKOS [IKOS07] protocol instantiates a zero-knowledge protocol for the relation , by having the prover simulate its corresponding MPC protocol virtually "in-the-head". The number of repetitions of the protocol is chosen to achieve negligible soundness error, such that it would be infeasible for the prover to cheat without getting caught in at least one of the runs. We describe here the non-interactive variant of the IKOS protocol:

• : The prover performs the emulated computation in the (2,3)-decomposed circuit defined above. After the computation, he computes the commitments to each of the three produced views.
• : The verifier challenges the prover to open two of the three committed views. Because of the 2-privacy property, opening two views for each run does not leak information about the witness. In the non-interactive version of the protocol, this challenge is derived from the view commitments.
• : The prover opens the requested commitments, and the verifier accepts if and only if:
  • (1) the output of each of the three views reconstructs to ;
  • (2) each of the two opened views were computed correctly; and
  • (3) the challenge was computed correctly.

Soundness

The soundness error for each repetition of the ZKBoo protocol is : in other words, a cheating prover escapes undetected with probability . To see intuitively why this is true, notice that by opening two views, we only fully check the execution of one player. To achieve a desired soundness of bits, we must execute repetitions of the protocol:

Applications

Post-quantum signature schemes ( and ) [Chase⁺ 2016]

The signature scheme uses ++ to generate a proof of knowledge of the signer's secret key, where the secret key is a pre-image of the public key with respect to the LowMC one-way function. applies the Fiat-Shamir transform to obtain an - secure signature scheme. is the same as , except that it uses the Unruh transform instead of the Fiat-Shamir transform to obtain a scheme that is provably secure in the QROM.

Blind certificate authorities [Wang⁺ 2019]

The blind certificate authority (CA) protocol allows a CA to validate ownership of an email address and issue a certificate blinding a public key to it, without learning the email address being used. To do this, they introduce an anonymous Proof of Account Ownership (PAO) protocol that outputs a cryptographic commitment to the prover's email account name. The prover then constructs an X.509 certificate for a public key of their choosing and hashes it. is then used to construct a zero-knowledge proof that demonstrates, roughly:

1. knowledge of the email account and public key to form a certificate;
2. knowledge of the email account and password in the commitment; and
3. that the account in the certificate is the same as the account in the commitment.

Cross-domain zero-knowledge proofs [Backes⁺ 2019]

-++ is a -protocol that extends ++ to prove a link between the input bits to a ++ circuit, and the bits in an algebraic commitment. Consider the example where the prover publishes , and a Pedersen commitment . To prove knowledge of , the prover:

1. computes Pedersen commitments to all bits of ;
2. proves using a Schnorr-based -protocol that each of those commitments contain a bit;
3. computes a ++ proof that there exists a such that ; and
4. computes a constant number of Pedersen commitments and compare them to the commitments from the ++ protocol to ensure

Open questions / research directions

Benchmarking against FRI-based zk-SNARK provers

The zk-STARK protocol [SBHR19] introduces a zero-knowledge proof that is also transparent, quantum-safe, with scalable proving time. It was stated in [SBHR19] that performed better than zk-STARK on small circuits; it would be worth re-running this benchmark against newer FRI-based zk-SNARKs like plonky2, which have access to optimisations such as lookup tables and smaller fields. We plan to extend our implementation to perform a SHA256 benchmark against the plonky2 prover.

Reducing proof size

Recursive proof composition has recently emerged as a technique to reduce proof sizes. By implementing the verifier in a zk-SNARK, we can produce a constant-size recursive proof for the protocol. However, since the verifier needs to redo the prover's computations, this would amount to reimplementing the boolean circuit in the zk-SNARK circuit. This is a similar problem to that faced in [BSB22], and will require careful analysis of trade-offs.

References

[Backes⁺ 2019] Backes, M., Hanzlik, L., Herzberg, A., Kate, A. and Pryvalov, I., 2019, April. Efficient non-interactive zero-knowledge proofs in cross-domains without trusted setup. In Public-Key Cryptography–PKC 2019: 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14-17, 2019, Proceedings, Part I (pp. 286-313). Cham: Springer International Publishing.

[Chase⁺ 2016] Chase, M., Derler, D., Goldfeder, S., Orlandi, C., Ramacher, S., Rechberger, C., Slamanig, D. and Zaverucha, G., 2017, October. Post-quantum zero-knowledge and signatures from symmetric-key primitives. In Proceedings of the 2017 acm sigsac conference on computer and communications security (pp. 1825-1842).

[GMO16] Giacomelli, I., Madsen, J. and Orlandi, C., 2016, August. ZKBoo: Faster Zero-Knowledge for Boolean Circuits. In USENIX Security Symposium (Vol. 16).

[IKOS07] Ishai, Y., Kushilevitz, E., Ostrovsky, R. and Sahai, A., 2007, June. Zero-knowledge from secure multiparty computation. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (pp. 21-30).

[PHGR16] Parno, B., Howell, J., Gentry, C. and Raykova, M., 2016. Pinocchio: Nearly practical verifiable computation. Communications of the ACM, 59(2), pp.103-112.

[Wang⁺ 2019] Wang, L., Asharov, G., Pass, R., Ristenpart, T. and Shelat, A., 2019, May. Blind certificate authorities. In 2019 IEEE Symposium on Security and Privacy (SP) (pp. 1015-1032). IEEE.