## Cryptology ePrint Archive: Report 2006/185

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

Minh-Huyen Nguyen and Shien Jin Ong and Salil Vadhan

Abstract: We show that every language in NP has a *statistical* zero-knowledge argument system under the (minimal) complexity assumption that one-way functions exist. In such protocols, even a computationally unbounded verifier cannot learn anything other than the fact that the assertion being proven is true, whereas a polynomial-time prover cannot convince the verifier to accept a false assertion except with negligible probability. This resolves an open question posed by Naor, Ostrovsky, Venkatesan, and Yung (CRYPTO 92, J. Cryptology 98).

Departing from previous works on this problem, we do not construct standard statistically hiding commitments from any one-way function. Instead, we construct a relaxed variant of commitment schemes called "1-out-of-2-binding commitments," recently introduced by Nguyen and Vadhan (STOC `06).

Category / Keywords: foundations / one-way functions, zero knowledge, bit commitment, complexity theory

Date: received 19 Jun 2006, last revised 19 Jun 2006

Contact author: salil at eecs harvard edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Short URL: ia.cr/2006/185

[ Cryptology ePrint archive ]