Rafail Ostrovsky - Publications

On Necessary Conditions for Secure Distributed Computation.

Rafail Ostrovsky and Moti Yung.

Abstract: What assumptions are required to achieve an unconditionally secure distributed circuit evaluation in a fully connected network? This question was addressed with respect to the allowed number of malicious players, given that every channel is unconditionally secure. In this paper we investigate whether the security of all channels is also a necessary condition. We show that in some cases the perfect security of multi-party protocols in a fully connected network requires all the channels to be physically secure. In particular, we show a simple protocol (for three parties) for which if privacy of even one channel is compromised, the protocol can not be computed securely.

comment: Appeared In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 2. 1990. Proceedings of a DIMACS workshop, October 4-6, 1989, pp. 229-234.

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

Back to Publications List