Cryptology ePrint Archive: Report 2009/461

A Framework for Non-Interactive Instance-Dependent Commitment Schemes (NIC)

Bruce Kapron and Lior Malka and Venkatesh Srinivasan

Abstract: Zero-knowledge protocols are often studied through specific problems, like Graph-Isomorphism. In many cases this approach prevents an important level of abstraction and leads to limited results, whereas in fact the constructions apply to a wide variety of problems. We propose to address this issue with a formal framework of non-interactive instance-dependent commitment schemes (NIC). We define NIC in both the perfect, statistical, and computational settings, and formally characterize problems admitting NIC in all of these settings. We also prove other useful lemmas such as closure properties. Consequently, results that previously applied only to specific problems are now strengthened by our framework to apply to classes of problems. By providing formal yet intuitive tools, our framework facilitates the construction of zero-knowledge protocols for a wide variety of problems, in various settings, without the need to refer to a specific problem. Our results are unconditional.

Category / Keywords: foundations / zero knowledge , commitment schemes

Publication Info: Previously published in ICALP 2007. This version is full and the results are presented from a different perspective

Date: received 17 Sep 2009, last revised 17 Sep 2009

Contact author: liorma at cs uvic ca

Available formats: PDF | BibTeX Citation

Version: 20090920:175540 (All versions of this report)

Discussion forum: Show discussion | Start new discussion