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.