Rafail Ostrovsky - Publications

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