Information Security and Cryptography Research Group

Efficiency Lower Bounds for Commit-and-Prove Constructions

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

2017 IEEE International Symposium on Information Theory (ISIT), IEEE, pp. 1788–1792, Jun 2017.

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},
}

Files and Links