Non-Interactive and Non-Malleable Commitment
Giovanni Di Crescenzo, Yuval Ishai, and Rafail Ostrovsky
Abstract: A commitment protocol is a fundamental cryptographic primitive used as a basic building block throughout modern cryptography. In STOC 1991, Dolev Dwork and Naor in a ground-breaking paper showed that in many settings the implementation of this fundamental primitive requires a strong non-malleability security property in order not to be susceptible to a certain class of attacks. In this paper, assuming a common random string available to all players, we show how to implement non-malleable commitment without interaction and based on any one-way function. In contrast, all previous solutions required either logarithmically many rounds of interaction or strong algebraic assumptions.
comment: Appeared in Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98)
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |