Secure Computation with Honest-Looking Parties
Ran Canetti, Rafail Ostrovsky
Abstract: How much can parties be trusted in secure multi-party computation? In the classic formulation of the secure computation problem the parties are trusted to exactly follow the prescribed protocol, except for a limited number of parties that are corrupted by a centralized adversary and are allowed to deviate from the protocol in an arbitrary way. However, we must also take into account the possibility that even an ``honest'' party would deviate from its protocol --- if it is guaranteed impunity by the fact that its external input/output behavior is indistinguishable from an honest one. Consequently, we consider the situation where all parties (even uncorrupted ones) may deviate from their protocol in arbitrary ways, under the sole restriction that the uncorrupted parties are not ``caught cheating'' by the other parties.
The question whether secure protocols exist in this scenario was raised in the past, and solutions for very limited deviations from the protocol (i. e., refraining from erasing data) were given. Yet, solving the general problem was believed hard, if at all possible. Contrary to this belief, we show that if secure communication channels are provided (and one-way functions exist) then any polynomial function can be securely computed even in this scenario.
comment: To appear in Proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99)
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |