Aarhus University Seal

Non-interactive and Reusable Non-malleable Commitment Schemes

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science

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.

Original languageEnglish
Title of host publicationProceedings of the thirty-fifth annual ACM symposium on Theory of computing
Number of pages12
PublisherAssociation for Computing Machinery
Publication year2003
ISBN (print)1-58113-674-9
Publication statusPublished - 2003
EventAnnual International Symposium on Computer Architecture - San Diego, CA, United States
Duration: 9 Jun 200311 Jun 2003
Conference number: 35


ConferenceAnnual International Symposium on Computer Architecture
LandUnited States
BySan Diego, CA

    Research areas

  • Commitment, non-malleablility, one-way function, signature, universal composability

See relations at Aarhus University Citationformats

ID: 281370