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, pp. 245--255, FOCS 2002.]]
2. Ran Canetti: Universally Composable Security: A New Paradigm for Cryptographic Protocols; pp. 136--145, FOCS 2001.]]
3. Ran Canetti and Marc Fischlin: Universally Composable Commitments; pp. 19--40, Proc. of Crypto 2001, Springer Verlag LNCS series 2139.]]
4. Ran Canetti, Yehuda Lindell, Rafail Ostrovsky and Amit Sahai: Universally Composable Two-Party and Multi-Party Secure Computation; pp. 494--503, STOC 2002.]]
5. Richard Crandall and Carl Pomerance: Prime Numbers: A Computational Perspective; pp. 34--35, Springer Verlag, 2001.]]
6. Giovanni Di Crescenzo, Yuval Ishai and Rafail Ostrovsky: Non-interactive and Non-malleable Commitment; pp. 141--150, STOC 1998.]]
7. Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky and Adam Smith: Efficient and Non-interactive Non-malleable Commitments; pp. 40-59, Proc. of EuroCrypt 2001, Springer Verlag LNCS series 2045.]]
8. Ivan Damgard and Jesper Buus Nielsen: Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor; pp. 581--596, Proc. of Crypto 2002, Springer Verlag LNCS series 2442.]]
9. Danny Dolev, Cynthia Dwork and Moni Naor: Non-malleable Cryptography, SIAM J.Computing, vol. 30, pp. 391--437, 2000. (Earlier version STOC 1991.)]]
10. Marc Fischlin: On the Impossibility of Constructing Non-interactive Statistically-Secret Protocols from Any Trapdoor One-Way Function, CT-RSA 2002, pp. 79--95, 2002.]]
11. Marc Fischlin and Roger Fischlin: Efficient Non-malleable Commitment Schemes; pp. 413--431, Proc. of Crypto 2000, Springer Verlag LNCS series 1880.]]
12. Shafi Goldwasser, Silvio Micali and Charles Rackoff: The Knowledge Complexity of Interactive Proof Systems, SIAM J.Computing, vol. 18, pp. 186--208, 1989.]]
13. Russell Impagliazzo and Steve Rudich: Limits on the Provable Consequences of One-Way Permutations; pp. 44--61, STOC 1989.]]
14. Moni Naor: Bit Commitment Using Pseudorandomness; pp. 151--158, Journal of Cryptology, vol. 4(2), 1991.]]
15. John Rompel: One-Way Functions are Necessary and Sufficient for Secure Signatures; pp. 387--394, STOC 1990.]]

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures