ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Efficiency Lower Bounds for Commit-and-Prove Constructions

Christian Badertscher and Sandro Coretti and Chen-Da Liu Zhang and Ueli Maurer

Commitment schemes that admit zero-knowledge proofs for relations among committed values are known as commit-and-prove functionalities or notarized envelopes. An important role in this context play equality proofs among commitments. They appear in various contexts of multi-party computation, circuit satisfiability or inclusion proofs. Using commit-and-prove functionalities admitting equality, we investigate black-box constructions of commit-and-prove functionalities admitting more complex relations. Typically, these constructions have to create commitments to additional values to achieve a certain level of soundness. An important efficiency measure is the number of such additional commitments. We prove that, for the natural and quite general class of 3-round public-coin zero-knowledge protocols, implementing the inequality relation, or any of the relations NAND, NOR, or XOR, essentially requires at least $2n$ additional commitments in order to achieve a soundness of $2^{-n}$. A folklore protocol shows that this bound is tight for inequality.