New and improved constructions of non-malleable cryptographic protocols

ABSTRACT

We present a new constant round protocol for non-malleable zero-knowledge. Using this protocol as a subroutine, we obtain a new constant-round protocol for non-malleable commitments. Our constructions rely on the existence of (standard) collision resistant hash functions. Previous constructions either relied on the existence of trapdoor permutations and hash functions that are collision resistant against sub-exponential sized circuits, or required a super-constant number of rounds.Additional results are the first construction of a non-malleable commitment scheme that is statistically hiding (with respect to opening), and the first non-malleable protocols that satisfy a strict polynomial-time simulation requirement. The latter are constructed by additionally assuming the existence of trapdoor permutations.Our approach differs from the approaches taken in previous works in that we view non-malleable zero-knowledge as a building-block rather than an end goal. This gives rise to a modular construction of non-malleable commitments and results in a somewhat simpler analysis.The techniques that we use to construct our zero-knowl-edge protocol are non black-box, but are different than the non black-box techniques previously used in the context of non-malleable coin-tossing.

REFERENCES

• 1: B. Barak (Machtey Award Co-winner), How to Go Beyond the Black-Box Simulation Barrier, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.106, October 14-17, 2001
• 2: Boaz Barak, Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.345-355, November 16-19, 2002
• 3: Boaz Barak , Oded Goldreich, Universal Arguments and their Applications, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.194, May 21-24, 2002
• 4: Boaz Barak , Yehuda Lindell, Strict polynomial-time in simulation and extraction, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509979]
• 5: Ran Canetti , Marc Fischlin, Universally Composable Commitments, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.19-40, August 19-23, 2001
• 6: Ivan Damgard , Jens Groth, Non-interactive and reusable non-malleable commitment schemes, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780605]
• 7: Ivan B. Damgård , Torben P. Pedersen , Birgit Pfitzmann, On the existence of statistically hiding bit commitment schemes and fail-stop signatures, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.250-265, January 1994, Santa Barbara, California, United States
• 8: Alfredo De Santis , Giovanni Di Crescenzo , Rafail Ostrovsky , Giuseppe Persiano , Amit Sahai, Robust Non-interactive Zero Knowledge, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.566-598, August 19-23, 2001
• 9: Giovanni Di Crescenzo , Jonathan Katz , Rafail Ostrovsky , Adam Smith, Efficient and Non-interactive Non-malleable Commitment, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.40-59, May 06-10, 2001
• 10: Giovanni Di Crescenzo , Yuval Ishai , Rafail Ostrovsky, Non-interactive and non-malleable commitment, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.141-150, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276722]
• 11: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 12: Uriel Feige , Dror Lapidot , Adi Shamir, Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions, SIAM Journal on Computing, v.29 n.1, p.1-28, Feb. 2000 [doi>10.1137/S0097539792230010]
• 13: U. Feige , A. Shamir, Witness indistinguishable and witness hiding protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.416-426, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100272]
• 14: Marc Fischlin , Roger Fischlin, Efficient Non-malleable Commitment Schemes, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.413-431, August 20-24, 2000
• 15: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 16: Oded Goldreich , Yehuda Lindell, Session-Key Generation Using Human Passwords Only, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.408-432, August 19-23, 2001
• 17: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 18: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 19: S. Goldwasser and S. Micali. Probabilistic Encryption. JCSS, Vol. 28(2), pages 270--299, 1984.
• 20: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 21: 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]
• 22: Joe Kilian, A note on efficient zero-knowledge proofs and arguments (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.723-732, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129782]
• 23: Yehuda Lindell, Bounded-concurrent secure two-party computation without setup assumptions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780641]
• 24: P. D. MacKenzie, M. K. Reiter, K. Yang: Alternatives to Non-malleability: Definitions, Constructions, and Applications. TCC 2004, pages 171--190, 2004.
• 25: Silvio Micali, Computationally Sound Proofs, SIAM Journal on Computing, v.30 n.4, p.1253-1298, 2000 [doi>10.1137/S0097539795284959]
• 26: M. Naor. Bit Commitment using Pseudorandomness. Jour. of Cryptology, Vol. 4, pages 151--158, 1991.
• 27: 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]
• 28: M. Nguyen and S. Vadhan. Simpler Session-Key Generation from Short Random Passwords. In 1st TCC, p.428--445, 2004.
• 29: Rafael Pass, Bounded-concurrent secure multi-party computation with a dishonest majority, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007393]
• 30: Rafael Pass , Alon Rosen, Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.404, October 11-14, 2003
• 31: Amit Sahai, Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.543, October 17-18, 1999

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

General Terms:
Theory

Keywords:
cryptography, man-in-the-middle, non black-box simulation, non-malleability, round-complexity, zero-knowledge