HOME / PUBLICATIONS /

An equivalence between zero knowledge and commitments.

Citation:

Ong, Shien Jin, and Salil Vadhan. “An equivalence between zero knowledge and commitments.” In R. Canetti, editor, Proceedings of the Third Theory of Cryptography Conference (TCC ‘08), 4948:482-500. Springer Verlag, Lecture Notes in Computer Science, 2008.
TCC2008.pdf572 KB

Abstract:

We show that a language in NP has a zero-knowledge protocol if and only if the language has an “instance-dependent” commitment scheme. An instance-dependent commitment schemes for a given language is a commitment scheme that can depend on an instance of the language, and where the hiding and binding properties are required to hold only on the yes and no instances of the language, respectively.

The novel direction is the only if direction. Thus, we confirm the widely held belief that commitments are not only sufficient for zero knowledge protocols, but necessary as well. Previous results of this type either held only for restricted types of protocols or languages, or used nonstandard relaxations of (instance-dependent) commitment schemes.

Publisher's Version

See also: Computational Complexity, Cryptography, Proof Systems, Guggenheim Fellowship, New Complexity-Theoretic Techniques in Cryptography (NSF CNS-0430336), Pseudorandomness and Combinatorial Constructions (US-Israel Binational Science Foundation; BSF 2002246)
Last updated on 07/14/2020