Efficiency Lower Bounds for Commit-and-Prove Constructions
Christian Badertscher, Sandro Coretti, 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.
BibTeX Citation
@unpublished{BCLM17,
author = {Christian Badertscher and Sandro Coretti and Chen-Da Liu Zhang and Ueli Maurer},
title = {Efficiency Lower Bounds for Commit-and-Prove Constructions},
booktitle = {2017 IEEE International Symposium on Information Theory (ISIT)},
pages = {1788--1792},
year = {2017},
month = {6},
publisher = {IEEE},
}