Paper 2020/478

Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, and Xin Li


In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs), in which $N$ parties wish to compute some joint function $f:(\{0,1\}^n)^N\to\{0,1\}$ using a public blackboard, but such that only $p$ parties may collude at a time. This generalizes well studied models in multiparty communication complexity, such as the number-in-hand (NIH) and number-on-forehead (NOF) models, which are just endpoints on this rich spectrum. We construct explicit hard functions against this spectrum, and achieve a tradeoff between collusion and complexity. Using this, we obtain improved leakage-resilient secret sharing schemes against bounded collusion protocols. Our main tool in obtaining hard functions against BCPs are explicit constructions of leakage resilient extractors against BCPs for a wide range of parameters. Kumar et al. (FOCS 2019) studied such extractors and called them cylinder intersection extractors. In fact, such extractors directly yield correlation bounds against BCPs. We focus on the following setting: the input to the extractor consists of $N$ independent sources of length $n$, and the leakage function Leak $:(\{0,1\}^n)^N\to\{0,1\}^\mu\in\mathcal{F}$ is a BCP with some collusion bound $p$ and leakage (output length) $\mu$. While our extractor constructions are very general, we highlight some interesting parameter settings: 1. In the case when the input sources are uniform, and $p=0.99N$ parties collude, our extractor can handle $n^{\Omega(1)}$ bits of leakage, regardless of the dependence between $N,n$. The best NOF lower bound (i.e., $p=N-1$) on the other hand requires $N<\log n$ even to handle $1$ bit of leakage. 2. Next, we show that for the same setting as above, we can drop the entropy requirement to $k=$ polylog $n$, while still handling polynomial leakage for $p=0.99N$. This resolves an open question about cylinder intersection extractors raised by Kumar et al. (FOCS 2019), and we find an application of such low entropy extractors in a new type of secret sharing. We also provide an explicit compiler that transforms any function with high NOF (distributional) communication complexity into a leakage-resilient extractor that can handle polylogarithmic entropy and substantially more leakage against BCPs. Thus any improvement of NOF lower bounds will immediately yield better leakage-resilient extractors. Using our extractors against BCPs, we obtain improved $N$-out-of-$N$ leakage-resilient secret sharing schemes. The previous best scheme from Kumar et al. (FOCS 2019) required share size to grow exponentially in the collusion bound, and thus cannot efficiently handle $p=\omega(\log N)$. Our schemes have no dependence of this form, and can thus handle collusion size $p=0.99N$.

Available format(s)
Publication info
Preprint. MINOR revision.
Communication complexityextractorscorrelation boundsleakage-resilient secret sharingbounded collusion protocols
Contact author(s)
eshanc @ cornell edu
jpmgoodman @ cs cornell edu
vipul @ cmu edu
lixints @ cs jhu edu
2020-04-28: revised
2020-04-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Eshan Chattopadhyay and Jesse Goodman and Vipul Goyal and Xin Li},
      title = {Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2020/478},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.