In Section 3.4 of the book Secure Multiparty Computation and Secret Sharing, it is claimed that for a secure multiparty computation problem with $n$ parties, the optimal corruption bound (concerning passive adversaries and information-theoretic security) is $n/2$, that is, at most $n/2$ passive adversaries are allowed in order to have information-theoretic security. It is claimed that this bound is optimal because there exist functions that cannot be computed securely if there are $\geq n/2$ adversaries. In particular, in the first paragraph of Section 3.4 of the book, there is one sentence: the multiplication subprotocol breaks down. The book and other papers provide analysis for Boolean functions, e.g., AND, OR and XOR functions. My question is: What is the corruption bound for secure multiparty integer sum computations? More specifically, given $n$ parties $P_1,\cdots,P_n$, each $P_i$ holds a secret integer $x_i$ (assuming that all $x_i$'s are inside a finite field $\mathbb{F}$) and they want to securely compute $S=\sum_{i=1}^nx_i$. Inside these $n$ parties, $t$ of them could be semi-honest adversaries and we are concerned with information-theoretic security. Also assuming complete communication graph. I am trying to apply the Shamir's secret sharing scheme. For this problem, is the corruption bound $t<n/2$ or $t<n$?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
For just computing a sum, the information-theoretic bound (assuming semihonest) is $t<n-1$.
Why $n-1$ and not $n$?
In the case of $t<n$, we can allegedly tolerate up to $n-1$ corrupt parties. If we are computing a sum, and the $n-1$ parties know the sum $S$ and their own inputs ($x_i$), they can simply compute the sum of their inputs and subtract that from $S$ to learn the private input of the single honest party. Therefore, there must be at least two honest parties if we are computing the sum.
-
$\begingroup$ Thanks! Is there any reference for this bound? I am confused about the explanation on why $n-1$ not $n$. In the case of $n-1$ adversaries, for sure they can determine from the sum $S$ the secret value of the only honest party. However, it seems that this does not violate the definition of security, that is, everything the adversaries can see during the execution of the algorithm can be simulated by only using their own inputs and outputs. E.g., it is mentioned in the book that the two-party secure XOR computation can be done such that each party just sends its value to the other. $\endgroup$ Commented Nov 13, 2017 at 21:41
-
$\begingroup$ Yes it does not violate the formal definition of security, but it does violate the assumed practical definition of security. I'll see if I can dig up the reference, but it is a common result in secure summation protocols in the literature. $\endgroup$– mikeazoCommented Nov 13, 2017 at 21:55
-
$\begingroup$ @ mikeazo Thanks for the answer! So now I understand that we should need two definitions: (1) definition for secure computation and (2) definition for privacy of of input data. For secure computation, the Shamir's secret sharing scheme can tolerate $n-1$ passive adversaries, while for privacy of input data, in the case of sum computation, there must be at least two honest parties. Is this conclusion correct? $\endgroup$ Commented Nov 13, 2017 at 22:46
-
-
1$\begingroup$ Technically, you can even tolerate $n$ corrupted parties while not violating the standard security notion (and considering the case of all parties being corrupted can make sense for a protocol which might become part of a larger protocol, involving more parties, so it's not entirely meaningless). $\endgroup$ Commented Nov 14, 2017 at 9:54