Efficiency lower bounds for commit-and-prove constructions

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 blackbox 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.
Original languageEnglish
Title of host publication2017 IEEE International Symposium on Information Theory (ISIT)
Place of PublicationAachen
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages5
ISBN (Electronic)978-1-5090-4096-4
ISBN (Print)978-1-5090-4097-1
Publication statusPublished - 15 Aug 2017
Externally publishedYes
Event2017 IEEE International Symposium on Information Theory, ISIT 2017 - Eurogress Aachen Conference and Cultural Events Center, AAchen, Germany
Duration: 25 Jun 201730 Jun 2017

Publication series

NameProceedings of the 2017 IEEE International Symposium on Information Theory (ISIT 2017)
ISSN (Electronic)2157-8117


Conference2017 IEEE International Symposium on Information Theory, ISIT 2017
Abbreviated titleISIT 2017
Internet address

Fingerprint Dive into the research topics of 'Efficiency lower bounds for commit-and-prove constructions'. Together they form a unique fingerprint.

Cite this