Non-interactive and reusable non-malleable commitment schemes

ABSTRACT

We consider non-malleable (NM) and universally composable (UC) commitment schemes in the common reference string (CRS) model. We show how to construct non-interactive NM commitments that remain non-malleable even if the adversary has access to an arbitrary number of commitments from honest players - rather than one, as in several previous schemes. We show this is a strictly stronger security notion. Our construction is the first non-interactive scheme achieving this that can be based on the minimal assumption of existence of one-way functions. But it can also be instantiated in a very efficient version based on the strong RSA assumption. For UC commitments, we show that existence of a UC commitment scheme in the CRS model (interactive or not) implies key exchange and - for a uniform reference string - even implies oblivious transfer. This indicates that UC commitment is a strictly stronger primitive than NM. Finally, we show that our strong RSA based construction can be used to improve the most efficient known UC commitment scheme so it can work with a CRS of size independent of the number of players, without loss of efficiency.

REFERENCES

• 1: 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
• 2: 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
• 3: 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
• 4: Ran Canetti , Yehuda Lindell , Rafail Ostrovsky , Amit Sahai, Universally composable two-party and multi-party secure computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509980]
• 5: Richard Crandall and Carl Pomerance: Prime Numbers: A Computational Perspective; pp. 34--35, Springer Verlag, 2001.
• 6: 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]
• 7: 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
• 8: Ivan Damgård , Jesper Buus Nielsen, Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.581-596, August 18-22, 2002
• 9: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 10: Marc Fischlin, On the Impossibility of Constructing Non-interactive Statistically-Secret Protocols from Any Trapdoor One-Way Function, Proceedings of the The Cryptographer's Track at the RSA Conference on Topics in Cryptology, p.79-95, February 18-22, 2002
• 11: 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
• 12: 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]
• 13: R. Impagliazzo , S. Rudich, Limits on the provable consequences of one-way permutations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.44-61, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73012]
• 14: Moni Naor: Bit Commitment Using Pseudorandomness; pp. 151--158, Journal of Cryptology, vol. 4(2), 1991.
• 15: 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:
  E. Data
  E.m MISCELLANEOUS

General Terms:
Algorithms, Security, Theory

Keywords:
commitment, non-malleability, one-way function, signature, universal composability