Secure Multiparty Sampling of a Biased Coin for Differential Privacy

Sampling a biased coin is a key primitive in designing secure multiparty computation (MPC) for differentially private mechanisms. We explore privately sampling a biased coin from l unbiased coins and offer an unconditionally secure MPC protocol for this task that can be implemented using either \(7.5l - 4\) (when l is even) or \(7.5l - 1.5\) (when l is odd) multiplications in 7 rounds. This protocol assumes control over the choice of the underlying field size and is compatible with any linear secret sharing scheme with a multiplication protocol. The protocol is also secure against active adversaries when the underlying secret sharing scheme is secure. Eriguchi and colleagues proposed a protocol to generate noise for differential privacy, incorporating a sub-protocol for biased coins. Replacing their sub-protocol with ours significantly reduces communication needs as the number of multiplications needed per biased coin becomes roughly 3/8 of the original.