|
Abstract : |
Abstract. We consider the classic problem of n honest but curious players with private inputs x1; : : : ; xn who wish to compute the value of a fixed function f(x1; \Delta \Delta \Delta; xn) in such way that at the end of the protocol every player knows the value f(x1; \Delta \Delta \Delta; xn). Each pair of players is connected by a secure point-to-point communication channel. The players have unbounded computational resources and they intend to compute f in a totally private way. That is, after the execution of the protocol no coalition of arbitrary size can get any information about the inputs of the remaining players other than what can be deduced by their own inputs and the value of f. We study the amount of randomness needed in totally private protocols. Our main result is a lower bound on the number of random bits needed to compute a function with sensitivity n. As a corollary we obtain that when the private inputs are uniformly distributed and the players have access to a source of uniformly distributed bits, at least k(n \Gamma 1)(n \Gamma 2)=2 random bits are needed to compute the sum modulo 2 k of n k-bit integers. This result is tight as there are protocols for this problem that use exactly this number of random bits. 1, |
