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. It was previously known that XOR can be computed using only one random bit for any number of players.
In this talk, we will see the result by Kushilevitz et al. which shows that there exists a protocol that can privately compute the Boolean function AND with 8 random bits for n>3 players and 7 bits for n=3 players under a semi-honest adversarial setting.
Link to the paper: https://epubs.siam.org/doi/pdf/10.1137/20M1314197
