Randomness complexity of private computation

We consider the problem of n honest but curious players with private inputs x(1),...,x(n), who wish to compute the value of a fixed function F(x(1),.. .,x(n)) in such way that at the end of the protocol every player knows the value F(x(1),...,x(n)). Each pair of players is connected by a secure point -to-point communication channel. The players have unbounded computational r esources and they intend to compute F in a t-private way. That is, after th e execution of the protocol, no coalition of size at most t less than or eq ual to n - 1 can get any information about the inputs of the remaining play ers other than what can be deduced from their own inputs and the value of F . We study the amount of randomness needed in t-private protocols. We prove a lower bound on the randomness complexity of any t-private protocol to comp ute a function with sensitivity n. As a corollary, we obtain that when the private inputs are uniformly distributed, at least k(n-1)(n-2)/2 random bit s are needed to compute the sum module 2(k) of n Ic-bit integers in an (n-2 )-private way. This result is tight as there are protocols for this problem that use exactly this number of random bits.