Cryptology ePrint Archive: Report 2001/032

Efficient and Non-Interactive Non-Malleable Commitment

Giovanni Di Crescenzo and Jonathan Katz and Rafail Ostrovsky and Adam Smith

Abstract: We present new constructions of non-malleable commitment schemes, in the public parameter model (where a trusted party makes parameters available to all parties), based on the discrete logarithm or RSA assumptions. The main features of our schemes are: they achieve near-optimal communication for arbitrarily-large messages and are non-interactive. Previous schemes either required (several rounds of) interaction or focused on achieving non-malleable commitment based on general assumptions and were thus efficient only when committing to a single bit. Although our main constructions are for the case of perfectly-hiding commitment, we also present a communication-efficient, non-interactive commitment scheme (based on general assumptions) that is perfectly binding.

Category / Keywords: foundations / non-malleable, malleability, commitment

Publication Info: Eurocrypt 2001

Date: received 23 Apr 2001, last revised 26 Apr 2001

Contact author: jkatz at cs columbia edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: Revised to indicate that this is an extended version of what will appear at Eurocrypt 2001.

Version: 20010515:150540 (All versions of this report)

Short URL: ia.cr/2001/032

Discussion forum: Show discussion | Start new discussion