Metadata only
Date
2017Type
- Conference Paper
Abstract
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. Show more
Publication status
publishedExternal links
Book title
2017 IEEE International Symposium on Information Theory (ISIT)Pages / Article No.
Publisher
IEEEEvent
Organisational unit
03338 - Maurer, Ueli / Maurer, Ueli
More
Show all metadata