期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-51
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 → {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 → {0, 1} µ ∈ F is a BCP with some collusion bound p and leakage (output length) µ. 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 Ω(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 = ω(log N). Our schemes have no dependence of this form, and can thus handle collusion size p = 0.99N.
