Extractors and Secret Sharing Against Bounded Collusion Protocols

Extractors and Secret Sharing Against Bounded Collusion Protocols (via Zoom)

Abstract: Bounded collusion protocols (BCPs) are multiparty communication protocols in which N players, holding n bits each, wish to compute some joint function f : ({0,1}^n)^N —> {0,1}. In each round, p players are allowed to work together to write a single bit on a public blackboard, and the protocol continues until everyone 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 (corresponding to p=1 and p=N-1, respectively). In this talk, we will investigate BCPs more thoroughly, and answer questions about them in the context of communication complexity, pseudorandomness, and cryptography.

Our investigation will culminate in the explicit construction of three related objects: (1) functions with strong *lower bounds* against BCPs, (2) leakage-resilient *extractors* against BCPs, and (3) leakage-resilient *secret sharing schemes* against BCPs. Our constructions are simple, and provide an exponential improvement over the previous best results [Kumar-Meka-Sahai, FOCS 2019].

This work appeared in FOCS 2020, and is joint with Eshan Chattopadhyay, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, and David Zuckerman.

Bio: Jesse Goodman is a third year CS PhD student at Cornell, where he is advised by Eshan Chattopadhyay. Previously, he received his BSE from Princeton. His primary interests lie in combinatorics, complexity theory, and pseudorandomness.