International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Non-interactive and Reusable Non-malleable Commitment Schemes

Ivan Damgård
Jens Groth
Search ePrint
Search Google
Abstract: We consider non-malleable (NM) and universally composable (UC) commitmentschemes in the common reference string (CRS) model. We show how to construct non-interac\-tive 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.
  title={Non-interactive and Reusable Non-malleable Commitment Schemes},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Commitment, non-malleability, universal composability,},
  note={To appear in STOC 2003 12220 received 29 Apr 2003, last revised 17 Jun 2003},
  author={Ivan Damgård and Jens Groth},