HOME / PUBLICATIONS /

Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function

Citation:

Haitner, Iftach, Minh Nguyen, Shien Jin Ong, Omer Reingold, and Salil Vadhan. “Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function.” SIAM Journal on Computing 39, no. 3 (2009): 1153-1218.
SIAM2009.pdf687 KB

Abstract:

Version History: Special Issue on STOC ‘07. Merge of papers from FOCS ‘06 and STOC ‘07. Received SIAM Outstanding Paper Prize 2011.

We 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. [J. Cryptology, 11 (1998), pp. 87–108].

Publisher's Version

See also: Computational Complexity, Cryptography, Proof Systems, New Complexity-Theoretic Techniques in Cryptography (NSF CNS-0430336), Pseudorandomness and Combinatorial Constructions (US-Israel Binational Science Foundation; BSF 2002246)
Last updated on 07/14/2020