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

    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