Statistically-hiding commitment from any one-way function

ABSTRACT

We give a construction of statistically-hiding commitment schemes (ones where the hiding propertyholds information theoretically), based on the minimal cryptographic assumption that one-way functions exist. Our construction employs two-phase commitment schemes, recently constructed by Nguyen, Ong and Vadhan (FOCS '06), and universal one-way hash functions introduced and constructedby Naor and Yung (STOC '89) and Rompel (STOC '90).

REFERENCES

• 1: Joan F. Boyar , Stuart A. Kurtz, A discrete logarithm implementation of perfect zero-knowledge blobs, Journal of Cryptology, v.2 n.2, p.63-76, 1990
• 2: Gilles Brassard , David Chaum , Claude Crépeau, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, v.37 n.2, p.156-189, October 1988 [doi>10.1016/0022-0000(88)90005-0]
• 3: J. Carter and M. Wegman. Universal classes of hash functions. J. CSS, 1979.
• 4: I. Damgard, M. Pedersen, and B. Pfitzmann. On the existence of statistically hiding bit commitment schemes and all fail-stop signatures. JCRYPTOLOGY, 1997.
• 5: O. Goldreich. Randomized methods in computation - lecture notes. 2001.
• 6: O. Goldreich and A. Kahan. How to construct constant-round zero-knowledge proof systems for all NP. JCRYPTOLOGY, 1996.
• 7: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 8: I. Haitner, O. Horvitz, K.J., C. Koo, R. Morselli, and R. Shaltiel. Reducing complexity assumptions for statistically-hiding commitment. In EUROCRYPT, 2005.
• 9: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 10: R. Impagliazzo and M. Luby. One-way functions are essential for complexity-based cryptography. In 30 FOCS, 1989.
• 11: J. Katz and C. Koo. On constructing universal one-way hash functions from arbitrary all one-way functions. ePrint, Report 2005/328, 2005.
• 12: Y. Lindell. Parallel coin-tossing and constant-round secure two-party all computation. JCRYPTOLOGY, 2003.
• 13: M. Naor. Bit commitment using pseudorandomness. J. CRYPTOLOGY, 1991.
• 14: M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung. Perfect zero-knowledge arguments for NP using any one-way all permutation. J. CRYPTOLOGY, 1998.
• 15: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 16: Minh-Huyen Nguyen , Shien Jin Ong , Salil Vadhan, Statistical Zero-Knowledge Arguments for NP from Any One-Way Function, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.3-14, October 21-24, 2006 [doi>10.1109/FOCS.2006.71]
• 17: Minh-Huyen Nguyen , Salil Vadhan, Zero knowledge with efficient provers, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132559]
• 18: J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100269]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation

General Terms:
Theory

Keywords:
cryptography, one-way functions, statistically hiding and computationally binding commitment