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 come along with zero-knowledge proofs for relations among committed values are known as commit-and-prove functionalities or notarized envelopes. An important role in this context take equality proofs among commitments. They appear in various contexts of multi-party computation, circuit satisfiability or inclusion proofs. Using commit-and-prove functionalities for equality, we investigate black-box constructions of commit-and-prove functionalities for more complex relations. We are interested in the relationship between the soundness of such protocols and the number of additional commitments a protocol creates during a run. In particular, for the natural and quite general class of 3-round public-coin zero-knowledge protocols, it turns out that implementing an inequality proof, 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}$. For concreteness, we revisit a protocol for inequality that exactly matches this bound.