Paper 2020/478
LeakageResilient Extractors and SecretSharing against Bounded Collusion Protocols
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, and Xin Li
Abstract
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 numberinhand (NIH) and numberonforehead (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 leakageresilient 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=N1$) 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 leakageresilient extractor that can handle polylogarithmic entropy and substantially more leakage against BCPs. Thus any improvement of NOF lower bounds will immediately yield better leakageresilient extractors. Using our extractors against BCPs, we obtain improved $N$outof$N$ leakageresilient 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$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Communication complexityextractorscorrelation boundsleakageresilient secret sharingbounded collusion protocols
 Contact author(s)

eshanc @ cornell edu
jpmgoodman @ cs cornell edu
vipul @ cmu edu
lixints @ cs jhu edu  History
 20200428: revised
 20200428: received
 See all versions
 Short URL
 https://ia.cr/2020/478
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/478, author = {Eshan Chattopadhyay and Jesse Goodman and Vipul Goyal and Xin Li}, title = {LeakageResilient Extractors and SecretSharing against Bounded Collusion Protocols}, howpublished = {Cryptology ePrint Archive, Paper 2020/478}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/478}}, url = {https://eprint.iacr.org/2020/478} }