Extractors and Secret Sharing Against Bounded Collusion Protocols
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, David Zuckerman
Abstract
In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs). BCPs are multiparty communication protocols in which N parties, holding n bits each, attempt to compute some joint function of their inputs, f : (0, 1 n ) N → 0, 1. In each round, p parties (the collusion bound) work together to write a single bit on a public blackboard, and the protocol continues until every party knows the value of f . BCPs are a natural generalization of the well-studied number-in-hand (NIH) and number-on-forehead (NOF) models, which are just endpoints on this rich spectrum of protocols (corresponding to p = 1 and p = N -1, respectively). In this work, we investigate BCPs more thoroughly, and answer questions about them in the context of communication complexity, randomness extractors, and secret sharing.
-
First, we provide explicit lower bounds against BCPs. Our lower bounds offer a tradeoff between collusion and complexity, and are of the form n Ω(1) when p = 0.99N parties collude. This bound is independent of the relationship between N, n, whereas all previous bounds became trivial when N > 1.1 log n.
-
Second, we provide explicit leakage-resilient extractors against BCPs. Also known as cylinder-intersection extractors, these objects are multi-source extractors of the form Ext : (0, 1 n ) N → 0, 1, whose output looks uniform even conditioned on the bits produced ("leaked") by a BCP executed over the inputs of the extractor. Our extractors work for sources with min-entropy k ≥ polylog(n) against BCPs with collusion p ≤ N -2. Previously, all such extractors required min-entropy k ≥ 0.99n even when p ≤ O(1).
-
Third, we provide efficient leakage-resilient secret sharing schemes against BCPs. These cryptographic primitives are standard t-out-of-N secret sharing schemes, equipped with an additional guarantee that the secret remains hidden even if the individuals participate in a BCP using their shares. Our schemes can handle collusion up to p ≤ O(t/ log t), whereas the previous best scheme required p ≤ O(log N ).
Along the way, we also construct objects that are more general than those listed above (i.e., compilers), objects that are more specialized (and stronger) than those listed above, and resolve open questions posed by Goyal and Kumar (STOC 2018) and Kumar, Meka, and Sahai (FOCS 2019).
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
3 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Short Leakage Resilient and Non-malleable Secret Sharing Schemes cites Lower Bounds for Leakage-Resilient Secret Sharing
- Constructing Leakage-Resilient Shamir's Secret Sharing: Over Composite Order Fields cites Short Leakage Resilient and Non-malleable Secret Sharing Schemes
- Constructing Leakage-Resilient Shamir's Secret Sharing: Over Composite Order Fields cites Lower Bounds for Leakage-Resilient Secret Sharing
- Leakage-Resilient Extractors against Number-on-Forehead Protocols cites Improved Extractors for Small-Space Sources
- Leakage-Resilient Extractors against Number-on-Forehead Protocols cites Extractors for adversarial sources via extremal hypergraphs
- Improved Extractors for Small-Space Sources cites How to Extract Useful Randomness from Unreliable Sources
- Improved Extractors for Small-Space Sources cites Extractors for adversarial sources via extremal hypergraphs
Cited by top-tier papers3
- Short Leakage Resilient and Non-malleable Secret Sharing SchemesNishanth Chandran, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Sruthi SekarCRYPTO 2022 · 11 citations
- Constructing Leakage-Resilient Shamir's Secret Sharing: Over Composite Order FieldsHemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, Xiuyu YeEUROCRYPT 2024 · 8 citations
- Leakage-Resilient Extractors against Number-on-Forehead ProtocolsEshan Chattopadhyay, Jesse GoodmanSTOC 2025 · 1 citation
Builds on4
- Lower Bounds for Leakage-Resilient Secret SharingJesper Buus Nielsen, Mark SimkinEUROCRYPT 2020 · 27 citations
- How to Extract Useful Randomness from Unreliable SourcesDivesh Aggarwal, Maciej Obremski, João Ribeiro, Luisa Siniscalchi et al.EUROCRYPT 2020 · 11 citations
- Improved Extractors for Small-Space SourcesEshan Chattopadhyay, Jesse GoodmanFOCS 2021 · 6 citations
- Extractors for adversarial sources via extremal hypergraphsEshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin LiSTOC 2020 · 1 citation
Related papers
- On the Round Complexity of Black-Box Secure MPCYuval Ishai, Dakshita Khurana, Amit Sahai, Akshayaram SrinivasanCRYPTO 2021 · 18 citations
- The Mother of All Leakages: How to Simulate Noisy Leakages via Bounded Leakage (Almost) for FreeGianluca Brian, Antonio Faonio, Maciej Obremski, João Ribeiro et al.EUROCRYPT 2021 · 5 citations
- Asymptotically Optimal Early Termination for Dishonest Majority BroadcastGiovanni Deligios, Ivana Klasovita, Chen-Da Liu-ZhangEUROCRYPT 2025 · 1 citation
- Leakage-Resilient Key Exchange and Two-Seed ExtractorsXin Li, Fermi Ma, Willy Quach, Daniel WichsCRYPTO 2020 · 6 citations
- A Tight Lower Bound on Adaptively Secure Full-Information Coin FlipIftach Haitner, Yonatan Karidi-HellerFOCS 2020 · 13 citations
