and Statistical Zero-Knowledge Arguments

from Any One-Way Function

Iftach Haitner,
Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, and

We give a construction of statistically hiding commitment schemes (ones where the hiding property holds against even computationally unbounded adversaries) under the minimal complexity assumption that one-way functions exist. Consequently, one-way functions suffice to give statistical zero-knowledge arguments for any NP statement (whereby even a computationally unbounded adversarial verifier learns nothing other than the fact the assertion being proven is true, and a polynomial-time adversarial prover cannot convince the verifier of a false statement). These results resolve an open question posed by Naor, Ostrovsky, Venkatesan, and Yung (CRYPTO `92, J. Cryptology `98).

This paper supersedes Statistical Zero-Knowledge Arguments for NP from Any One-Way Function.

- Manuscript, November 2007. [ps][pdf][powerpoint show]
*SIAM Journal on Computing*39 (3), pp. 1153-1218, 2009. [pdf][SIAM page]