Non-malleability amplification

ABSTRACT

We show a technique for amplifying commitment schemes that are non-malleable with respect to identities of length t, into ones that are non-malleable with respect to identities of length Ω(2^t), while only incurring a constant overhead in round-complexity. As a result we obtain a construction of O(1)^{log* n}-round (i.e., "essentially" constant-round) non-malleable commitments from any one-way function, and using a black-box proof of security.

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: 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]
• 4: . Damgå rd. Efficient Concurrent Zero-Knowledge in the Auxiliary String Model. In EuroCrypt2000, LNCS 1807, pages 418--430, 2000.
• 5: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 6: . Feige and A. Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In phCrypto86, Springer LNCS 263, pages 181--187, 1987.
• 7: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 8: 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]
• 9: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 10: 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]
• 11: 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]
• 12: . Naor. Bit Commitment using Pseudorandomness. Jour. of Cryptology, Vol. 4, pages 151--158, 1991.
• 13: 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]
• 14: Rafael Pass , Alon Rosen, New and improved constructions of non-malleable cryptographic protocols, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060670]
• 15: Alon Rosen, A Note on the Round-Complexity of Concurrent Zero-Knowledge, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.451-468, August 20-24, 2000
• 16: . Goldwasser, and S. Micali. Probabilistic Encryption. JCSS 28(2), pages 270--299, 1984.
• 17: Omkant Pandey , Rafael Pass , Vinod Vaikuntanathan, Adaptive One-Way Functions and Applications, Proceedings of the 28th Annual conference on Cryptology: Advances in Cryptology, August 17-21, 2008, Santa Barbara, CA, USA [doi>10.1007/978-3-540-85174-5_4]
• 18: . Katz, R. Ostrovsky, and A. Smith. Round Efficiency of Multi-Party Computation with a Dishonest Majority. In phEuroCrypt03, Springer LNCS 2656, pages 578--595, 2003.
• 19: . Lin, R. Pass, and M. Venkitasubramaniam. Concurrent Non-Malleable Commitments from One-way Functions. In ph5th TCC, pages 571--588, 2008.
• 20: Huijia Lin , Rafael Pass , Muthuramakrishnan Venkitasubramaniam, A unified framework for concurrent security: universal composability from stand-alone non-malleability, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536441]
• 21: Rafael Pass , Alon Rosen, Concurrent Non-Malleable Commitments, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.563-572, October 23-25, 2005 [doi>10.1109/SFCS.2005.27]
• 22: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001

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:
commitment, cryptography, non-malleability, round complexity