International Association
for Cryptologic Research

In the field of information-theoretic cryptography, randomness complexity is a key metric for protocols for private computation, that is, the number of random bits needed to realize the protocol. Although some general bounds are known, even for the relatively simple example of $n$-party AND, the exact complexity is unknown.

We improve the upper bound from Couteau and Ros\'en in Asiacrypt 2022 on the (asymptotic) randomness complexity of $n$-party AND from 6 to 5 bits, that is, we give a $1$-private protocol for computing the AND of $n$ parties' inputs requiring $5$ bits of additional randomness, for all $n \geq 120$. Our construction, like that of Couteau and Ros\'en, requires a single source of randomness.

Additionally, we consider the modified setting of Goyal, Ishai, and Song (Crypto '22) where helper parties without any inputs are allowed to assist in the computation. In this setting, we show that the randomness complexity of computing a general boolean circuit $C$ $1$-privately is exactly 2 bits, and this computation can be performed with seven helper parties per gate.