Rafail Ostrovsky - Publications

Secure Commitment Against Powerful Adversary: A Security Primitive based on Average Intractability.

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung.

Abstract: In this paper, we investigate the feasibility of bit commitment when one of the participants (either committer or receiver) has an unfair computational advantage. That is, we consider commitment to a strong receiver with a large computational power (requiring that despite his power he cannot ``open'' the secret commitment) or commitment by a strong committer (requiring that despite his power he can not change the value of the committed bit). We allow the strong party to use its computational resources and investigate the underlying complexity assumptions necessary for the feasibility of these primitives.

We show how to base commitment by a strong committer on any hard on the average problem. In fact, this is the first application of average case completeness to hiding information in a security primitive. We reduce complexity assumptions in the other direction as well.

comment: Appeared In Proceedings of 9th Symposium on Theoretical Aspects of Computer Science (STACS-92) (LNCS 577) Springer Verlag Ed. A. Finkel and M. Jantzen) pp. 439-448 February 13-15 1992, Paris, France.

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

Back to Publications List