The Round Complexity of Two-Party Random Selection

Abstract

We study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded "bias," even if one of the two parties deviates from the protocol (possibly using unlimited computational resources). Specifically, we require that the output's statistical difference from the uniform distribution on {0, 1}(n) is bounded by a constant less than 1. We present a protocol for the above problem that has 2 log* n + O(1) rounds, improving a previous 2n-round protocol of Goldreich, Goldwasser, and Linial (FOCS '91). Like the GGL Protocol, our protocol actually provides a stronger guarantee, ensuring that the output lands in any set T subset of {0, 1}(n) of density mu with probability at most O(root mu + delta), where delta may be an arbitrarily small constant. We then prove a nearly matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least log* n-log* log* n-O(1) rounds. We also prove several results for the case when the output's bias is measured by the maximum multiplicative factor by which a party can increase the probability of a set T subset of {0, 1}(n).