Statistically Hiding Commitments
and Statistical Zero-Knowledge Arguments
from Any One-Way Function

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


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.


 [ back to Salil Vadhan's research]