ECCC-Report TR20-055https://eccc.weizmann.ac.il/report/2020/055Comments and Revisions published for TR20-055en-usThu, 23 Apr 2020 12:54:31 +0300-
Paper TR20-055
| Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing |
Ashutosh Kumar,
Raghu Meka,
David Zuckerman
https://eccc.weizmann.ac.il/report/2020/055In 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, non-trivial lower bounds were only known 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).Thu, 23 Apr 2020 12:54:31 +0300https://eccc.weizmann.ac.il/report/2020/055