Title: Trading Robustness for Correctness and Privacy in Certain Multiparty Computations, beyond an Honest Majority
Abstract: We improve on the classical results in information-theoreti- cally secure multiparty computation among a set of n participants, by considering the special case of the computation of the addition function over binary inputs in the secure channels model with a simultaneous broadcast channel. This simple function is a useful building block for other applications. The classical results in multiparty computation show that in this model, every function can be computed with information-theoretic security if and only if less than n/2 participants are corrupt. In this article we show that, under certain conditions, this bound can be overcome. More precisely, let t (p), t (r) and t (c) be the privacy, robustness and correctness thresholds; that is, the minimum number of participants that must be actively corrupted in order for privacy, robustness or correctness, respectively, to be compromised. We show a series of novel tradeoffs applicable to the multiparty computation of f(x 1, …,x n ) = x 1 + … + x n for x i ∈ {0,1}, culminating in the most general tradeoff: t (p) + t (r) = n + 1 and t (c) + t (r) = n + 1. These tradeoffs are applicable as long as t (r) < n/2, which implies that, at the cost of reducing robustness, privacy and correctness are achievable despite a dishonest majority (as an example, setting the robustness threshold to n/3 yields privacy and correctness thresholds of 2n/3 + 1). We give applications to information-theoretically secure voting and anonymous message transmission, yielding protocols with the same tradeoffs.
Publication Year: 2012
Publication Date: 2012-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot