Efficient and Non-interactive Non-malleable Commitment
Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, 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 {\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