Rafail Ostrovsky - Publications

Efficient and Non-interactive Non-malleable Commitment

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


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 {\em near-optimal communication} for arbitrarily-large messages and are {\em 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.

comment: Appeared in Proceedings of Advances in Cryptology, (EUROCRYPT-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to the Rafail Ostrovsky publication list or to the Rafail Ostrovsky main page.