Paper Info
Title
A characterization of non-interactive instance-dependent commitment-schemes (NIC)
Abstract
We provide a new characterization of certain zero-knowledge protocols as non-interactive instance-dependent commitment-schemes (NIC). To obtain this result we consider the notion of V-bit protocols, which are very common, and found many applications in zero-knowledge. Our characterization result states that a protocol has a V-bit zero-knowledge protocol if and only if it has a NIC. The NIC inherits its hiding property from the zero-knowledge property of the protocol, and vice versa. Our characterization result yields a framework that strengthens and simplifies many zero-knowledge protocols in various settings. For example, applying this framework to the result of Micciancio et al. [18] (who showed that some problems, including GRAPH-NONISOMORPHISM and QUADRATIC-RESIDUOUSITY, unconditionally have a concurrent zero-knowledge proof) we easily get that arbitrary, monotone boolean formulae over a large class of problems (which contains, e.g., the complement of any random self-reducible problem) unconditionally have a concurrent zero-knowledge proof.
Year
DOI
Venue
2007
10.1007/978-3-540-73420-8_30
ICALP
Keywords
Field
DocType
commitment scheme,zero knowledge,zero knowledge proof
Discrete mathematics,Random self-reducibility,Combinatorics,Computer science,If and only if,Versa,Zero-knowledge proof,Monotone polygon
Conference
Volume
ISSN
ISBN
4596
0302-9743
3-540-73419-8
Citations 
PageRank 
References 
8
0.49
21
Authors
3
Name
Order
Citations
PageRank
Bruce M. Kapron130826.02
Lior Malka238612.65
Srinivasan Venkatesh320124.46