Haitner, IftachNguyen, Minh-HuyenOng, Shien JinReingold, OmerVadhan, Salil2015-03-122009Haitner, Iftach, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, and Salil Vadhan. 2009. “Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function.” SIAM Journal on Computing 39, no. 3: 1153–1218.0097-5397http://nrs.harvard.edu/urn-3:HUL.InstRepos:14123818We give a construction of statistically hiding commitment schemes (those in which 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 that the assertion being proven is true, and no polynomial-time adversarial prover can convince the verifier of a false statement). These results resolve an open question posed by Naor et al.en-UScryptographystatistically hiding commitmentsstatistical zero-knowledge argument systemsone-way functionsinteractive hashingJournal Article2015-03-1210.1137/080725404