Paper 2020/473

Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing

Ashutosh Kumar, Raghu Meka, and David Zuckerman


In this work we study bounded collusion protocols (BCPs) recently introduced in the context of secret sharing by Kumar, Meka, and Sahai (FOCS 2019). These are multi-party communication protocols on $n$ parties where in each round a subset of $p$-parties (the collusion bound) collude together and write a function of their inputs on a public blackboard. BCPs interpolate elegantly between the well-studied number-in-hand (NIH) model ($p=1$) and the number-on-forehead (NOF) model ($p=n-1$). Motivated by questions in communication complexity, secret sharing, and pseudorandomness we investigate BCPs more thoroughly, answering several questions about them. * We prove a polynomial (in the input-length) lower bound for an explicit function against BCPs where any constant fraction of players can collude. Previously, nontrivial lower bounds were known only when the collusion bound was at most logarithmic in the input-length (owing to bottlenecks in NOF lower bounds). * For all $t \leq n$, we construct efficient $t$-out-of-$n$ secret sharing schemes where the secret remains hidden even given the transcript of a BCP with collusion bound $O(t/\log t)$. Prior work could only handle collusions of size $O(\log n)$. Along the way, we construct leakage-resilient schemes against disjoint and adaptive leakage, resolving a question asked by Goyal and Kumar (STOC 2018). * An explicit $n$-source cylinder intersection extractor whose output is close to uniform even when given the transcript of a BCP with a constant fraction of parties colluding. The min-entropy rate we require is $0.3$ (independent of collusion bound $p \ll n$). Our results rely on a new class of exponential sums that interpolate between the ones considered in additive combinatorics by Bourgain (Geometric and Functional Analysis 2009) and Petridis and Shparlinski (Journal d'Analyse Mathématique 2019).

Available format(s)
Publication info
Preprint. MINOR revision.
secret sharingleakage-resilienceextractorscommunication complexity
Contact author(s)
a @ ashutoshk com
raghum @ cs ucla edu
diz @ cs utexas edu
2020-04-28: received
Short URL
Creative Commons Attribution


      author = {Ashutosh Kumar and Raghu Meka and David Zuckerman},
      title = {Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2020/473},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.