Extractors and Secret Sharing Against Bounded Collusion Protocols

In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs). BCPs are multiparty communication protocols in which N parties, holding n bits each, attempt to compute some joint function of their inputs, f : (0, 1 n ) N → 0, 1. In each round, p parties (the collusion bound) work together to write a single bit on a public blackboard, and the protocol continues until every party knows the value of f . BCPs are a natural generalization of the well-studied number-in-hand (NIH) and number-on-forehead (NOF) models, which are just endpoints on this rich spectrum of protocols (corresponding to p = 1 and p = N -1, respectively). In this work, we investigate BCPs more thoroughly, and answer questions about them in the context of communication complexity, randomness extractors, and secret sharing.

1. First, we provide explicit lower bounds against BCPs. Our lower bounds offer a tradeoff between collusion and complexity, and are of the form n Ω(1) when p = 0.99N parties collude. This bound is independent of the relationship between N, n, whereas all previous bounds became trivial when N > 1.1 log n.

2. Second, we provide explicit leakage-resilient extractors against BCPs. Also known as cylinder-intersection extractors, these objects are multi-source extractors of the form Ext : (0, 1 n ) N → 0, 1, whose output looks uniform even conditioned on the bits produced ("leaked") by a BCP executed over the inputs of the extractor. Our extractors work for sources with min-entropy k ≥ polylog(n) against BCPs with collusion p ≤ N -2. Previously, all such extractors required min-entropy k ≥ 0.99n even when p ≤ O(1).

3. Third, we provide efficient leakage-resilient secret sharing schemes against BCPs. These cryptographic primitives are standard t-out-of-N secret sharing schemes, equipped with an additional guarantee that the secret remains hidden even if the individuals participate in a BCP using their shares. Our schemes can handle collusion up to p ≤ O(t/ log t), whereas the previous best scheme required p ≤ O(log N ).

Along the way, we also construct objects that are more general than those listed above (i.e., compilers), objects that are more specialized (and stronger) than those listed above, and resolve open questions posed by Goyal and Kumar (STOC 2018) and Kumar, Meka, and Sahai (FOCS 2019).