Paper 2003/080

Non-interactive and Reusable Non-malleable Commitment Schemes

Ivan Damgård and Jens Groth

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.

Note: Minor change: Phil MacKenzie and Ke Yang pointed out that Lemma 5 of the original paper was too strongly formulated. We have now restated Lemma 5 correctly. Nothing else has changed.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. To appear in STOC 2003
Keywords
Commitmentnon-malleabilityuniversal composability
Contact author(s)
jg @ brics dk
History
2003-06-17: revised
2003-04-30: received
See all versions
Short URL
https://ia.cr/2003/080
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/080,
      author = {Ivan Damgård and Jens Groth},
      title = {Non-interactive and Reusable Non-malleable Commitment Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2003/080},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/080}},
      url = {https://eprint.iacr.org/2003/080}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.