In a secure multi-party computation problem, players are required to compute a function of their private inputs without revealing any extra information about this input to other players. Randomness complexity is the number of random bits used by the protocol which enables such a computation. Since randomness is an expensive resource, developing MPC protocols to operate on minimum amount of randomness has been an interesting problem. In a recent work, Kushilevitz et. al. prove a lower bound of 1 bit and an upper bound of 7 bits (8 bits) for the randomness complexity of securely computing Boolean AND function in a 3-player (n>3 player) setting. In this work, we improve upon this lower bound obtaining 3 bits for a 3-player setting using information theoretic tools.
Zoom link -
https://zoom.us/j/98392241202?pwd=bTJRYklZZERXWWpIK0RIdnFZNzJSQT09
