Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2506.12595 · ACM Symposium on Theory of Computing (STOC)

Leakage-Resilient Extractors against Number-on-Forehead Protocols

Eshan Chattopadhyay, Jesse Goodman

Published Jun 15, 2025• 0 citations
arXivHTMLPDF

Abstract

Given a sequence of $N$ independent sources $\mathbf{X}_1,\mathbf{X}_2,\dots,\mathbf{X}_N\sim\{0,1\}^n$, how many of them must be good (i.e., contain some min-entropy) in order to extract a uniformly random string? This question was first raised by Chattopadhyay, Goodman, Goyal and Li (STOC '20), motivated by applications in cryptography, distributed computing, and the unreliable nature of real-world sources of randomness. In their paper, they showed how to construct explicit low-error extractors for just $K \geq N^{1/2}$ good sources of polylogarithmic min-entropy. In a follow-up, Chattopadhyay and Goodman improved the number of good sources required to just $K \geq N^{0.01}$ (FOCS '21). In this paper, we finally achieve $K=3$. Our key ingredient is a near-optimal explicit construction of a new pseudorandom primitive, called a leakage-resilient extractor (LRE) against number-on-forehead (NOF) protocols. Our LRE can be viewed as a significantly more robust version of Li's low-error three-source extractor (FOCS '15), and resolves an open question put forth by Kumar, Meka, and Sahai (FOCS '19) and Chattopadhyay, Goodman, Goyal, Kumar, Li, Meka, and Zuckerman (FOCS '20). Our LRE construction is based on a simple new connection we discover between multiparty communication complexity and non-malleable extractors, which shows that such extractors exhibit strong average-case lower bounds against NOF protocols.

DOI
10.1145/3717823.3718272

Related papers

Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Eshan Chattopadhyay, Vipul Goyal, Xin Li

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-malleable extractors, introduced in [DW09]; seedless non-malleable extractors, introduced in [CG14b]; and non-malleable codes, introduced in [DPW10]. However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts. In this paper we make progress towards solving the above problems. Our contributions are as follows. (1) We construct an explicit seeded non-malleable extractor for min-entropy $k \geq \log^2 n$. This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result in [Li15b]. (2) We construct the first explicit non-malleable two-source extractor for min-entropy $k \geq n-n^{Ω(1)}$, with output size $n^{Ω(1)}$ and error $2^{-n^{Ω(1)}}$. (3) We initiate the study of two natural generalizations of seedless non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times. We construct the first explicit non-malleable two-source extractor with tampering degree $t$ up to $n^{Ω(1)}$, which works for min-entropy $k \geq n-n^{Ω(1)}$, with output size $n^{Ω(1)}$ and error $2^{-n^{Ω(1)}}$. We show that we can efficiently sample uniformly from any pre-image. By the connection in [CG14b], we also obtain the first explicit non-malleable codes with tampering degree $t$ up to $n^{Ω(1)}$, relative rate $n^{Ω(1)}/n$, and error $2^{-n^{Ω(1)}}$.

arXiv:1505.00107•May 1, 2015•3 citations

Extractors: Low Entropy Requirements Colliding With Non-Malleability

Divesh Aggarwal, Eldon Chung, Maciej Obremski

The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about $1/2$, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability. (2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered. (3) Constructions where both sources have entropy rate very close to $1$ and the extractor guarantees non-malleability against the tampering of both sources. We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have $0.8$ entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate $\frac 1 2$, which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.

arXiv:2111.04157•Nov 7, 2021•1 citation

Extractors: Low Entropy Requirements Colliding With Non-Malleability

Eldon Chung, Maciej Obremski, Divesh Aggarwal

The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about $1/2$, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability. (2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered. (3) Constructions where both sources have entropy rate very close to $1$ and the extractor guarantees non-malleability against the tampering of both sources. We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have $0.8$ entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate $\frac 1 2$, which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.

Electronic colloquium on computational complexity•Jan 1, 2021•2 citations

Nonmalleable Extractors with Short Seeds and Applications to Privacy Amplification

Gil Cohen, Ran Raz, Gil Segev

Motivated by the classical problem of privacy amplification, Dodis and Wichs [in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 601--610] introduced the notion of a nonmalleable extractor, significantly strengthening the notion of a strong extractor. A nonmalleable extractor is a function $\mathsf{nmExt}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m$ that takes two inputs---a weak source $W$ and a uniform (independent) seed $S$---and outputs a string $\mathsf{nmExt}(W,S)$ that is nearly uniform given the seed $S$ as well as the value $\mathsf{nmExt}(W,S')$ for any seed $S'\neq S$ that may be determined as an arbitrary function of $S$. The first explicit construction of a nonmalleable extractor was recently provided by Dodis et al. [Privacy Amplification and Non-malleable Extractors via Character Sums, preprint, arXiv:1102.5415 [cs.CR], 2011]. Their extractor works for any weak source with min-entropy rate $1/2+\delta$, where $\delta>0$ is an arbitrary constant and outputs up to a linear number of bits but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols), its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an unconditional construction of a nonmalleable extractor with short seeds. For any integers $n$ and $d$ such that $2.01\cdot\log n\leq d\leq n$, we present an explicit construction of a nonmalleable extractor $\mathsf{nmExt}\colon\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m$, with $m=\Omega(d)$ and error exponentially small in $m$. The extractor works for any weak source with min-entropy rate $1/2+\delta$, where $\delta>0$ is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of nonmalleability: its output $\mathsf{nmExt}(W,S)$ is nearly uniform given the seed $S$ as well as the values $\mathsf{nmExt}(W,S_1),\dots,\mathsf{nmExt}(W,S_t)$ for several seeds $S_1,\dots,S_t$ that may be determined as an arbitrary function of $S$, as long as $S\notin\{S_1,\dots,S_t\}$. By instantiating the framework of Dodis and Wichs with our nonmalleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate $1/2+\delta$ with asymptotically optimal entropy loss and polylogarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs, whose entropy loss is not asymptotically optimal, and the protocol of Dodis et al., whose communication complexity is linear.

SIAM Journal on Computing•Jan 1, 2014•15 citations

Quantum secure non-malleable-extractors

Naresh Goud Boddu, Rahul Jain, Upendra Kapshikar

We construct several explicit quantum secure non-malleable-extractors. All the quantum secure non-malleable-extractors we construct are based on the constructions by Chattopadhyay, Goyal and Li [2015] and Cohen [2015]. 1) We construct the first explicit quantum secure non-malleable-extractor for (source) min-entropy $k \geq \textsf{poly}\left(\log \left( \frac{n}ε \right)\right)$ ($n$ is the length of the source and $ε$ is the error parameter). Previously Aggarwal, Chung, Lin, and Vidick [2019] have shown that the inner-product based non-malleable-extractor proposed by Li [2012] is quantum secure, however it required linear (in $n$) min-entropy and seed length. Using the connection between non-malleable-extractors and privacy amplification (established first in the quantum setting by Cohen and Vidick [2017]), we get a $2$-round privacy amplification protocol that is secure against active quantum adversaries with communication $\textsf{poly}\left(\log \left( \frac{n}ε \right)\right)$, exponentially improving upon the linear communication required by the protocol due to [2019]. 2) We construct an explicit quantum secure $2$-source non-malleable-extractor for min-entropy $k \geq n- n^{Ω(1)}$, with an output of size $n^{Ω(1)}$ and error $2^{- n^{Ω(1)}}$. 3) We also study their natural extensions when the tampering of the inputs is performed $t$-times. We construct explicit quantum secure $t$-non-malleable-extractors for both seeded ($t=d^{Ω(1)}$) as well as $2$-source case ($t=n^{Ω(1)}$).

arXiv:2109.03097•Sep 7, 2021•5 citations

Leakage-Resilient Secret Sharing Against Colluding Parties

Ashutosh Kumar, Raghu Meka, Amit Sahai

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against an adversary who may learn some “leaked'' information about all the shares. We say that a secret sharing scheme is p-party leakage-resilient, if the secret remains statistically hidden even after a computationally unbounded adversary learns a bounded amount of leakage, where each bit of leakage adaptively and jointly depends on the shares of an adaptively chosen subset of p parties. Existing multi-party secret sharing schemes (Dziembowski and Pietrzak FOCS 07), (Goyal and Kumar STOC 18) and (Benhamouda, Degwekar, Ishai and Rabin CRYPTO 18) have focused on handling non-adaptive and individual leakage for (limited special cases of) threshold secret sharing schemes. (1) We give an unconditional compiler that transforms any secret sharing scheme on n parties into a p-party leakage-resilient one for p upto O(log n). This yields the first multi-party secret sharing schemes that are secure against adaptive or joint leakage. (2) As a natural extension, we initiate the study of leakage-resilient non-malleable secret sharing. We empower the adversary to adaptively leak from each of the shares and then use the leakage to tamper with all of them arbitrarily and independently. Leveraging our p-party leakage-resilient schemes, we compile any secret sharing scheme into a non-malleable one ensuring that any such tampering either preserves the secret or completely `destroys' it. This improves upon the non-malleable secret sharing scheme of (Goyal and Kumar CRYPTO 18) where no leakage was permitted. Leakage-resilient non-malleable codes can be seen as 2-out-of-2 schemes satisfying our guarantee and have already found many applications in cryptography. (3) Our constructions rely on a clean connection we draw to communication complexity in the well-studied number-on-forehead (NOF) model and rely on functions that have strong communication-complexity lower bounds in the NOF model (in a black-box way). We get efficient p-party leakage-resilient schemes for p upto O(log n) as our share sizes have exponential dependence on p. We observe that improving this exponential dependence, even for simultaneous, non-adaptive leakage, will lead to progress on longstanding open problems in complexity theory.

Annual Symposium on Foundations of Computer Science•Nov 1, 2019•28 citations
Given a sequence of NNN independent sources X1,X2,…,XN∼{0,1}n\mathbf{X}_1,\mathbf{X}_2,\dots,\mathbf{X}_N\sim\{0,1\}^nX1​,X2​,…,XN​∼{0,1}n, how many of them must be good (i.e., contain some min-entropy) in order to extract a uniformly random string? This question was first raised by Chattopadhyay, Goodman, Goyal and Li (STOC '20), motivated by applications in cryptography, distributed computing, and the unreliable nature of real-world sources of randomness. In their paper, they showed how to construct explicit low-error extractors for just K≥N1/2K \geq N^{1/2}K≥N1/2 good sources of polylogarithmic min-entropy. In a follow-up, Chattopadhyay and Goodman improved the number of good sources required to just K≥N0.01K \geq N^{0.01}K≥N0.01 (FOCS '21). In this paper, we finally achieve K=3K=3K=3. Our key ingredient is a near-optimal explicit construction of a new pseudorandom primitive, called a leakage-resilient extractor (LRE) against number-on-forehead (NOF) protocols. Our LRE can be viewed as a significantly more robust version of Li's low-error three-source extractor (FOCS '15), and resolves an open question put forth by Kumar, Meka, and Sahai (FOCS '19) and Chattopadhyay, Goodman, Goyal, Kumar, Li, Meka, and Zuckerman (FOCS '20). Our LRE construction is based on a simple new connection we discover between multiparty communication complexity and non-malleable extractors, which shows that such extractors exhibit strong average-case lower bounds against NOF protocols.
Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-malleable extractors, introduced in [DW09]; seedless non-malleable extractors, introduced in [CG14b]; and non-malleable codes, introduced in [DPW10]. However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts. In this paper we make progress towards solving the above problems. Our contributions are as follows. (1) We construct an explicit seeded non-malleable extractor for min-entropy k≥log⁡2nk \geq \log^2 nk≥log2n. This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result in [Li15b]. (2) We construct the first explicit non-malleable two-source extractor for min-entropy k≥n−nΩ(1)k \geq n-n^{Ω(1)}k≥n−nΩ(1), with output size nΩ(1)n^{Ω(1)}nΩ(1) and error 2−nΩ(1)2^{-n^{Ω(1)}}2−nΩ(1). (3) We initiate the study of two natural generalizations of seedless non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times. We construct the first explicit non-malleable two-source extractor with tampering degree ttt up to nΩ(1)n^{Ω(1)}nΩ(1), which works for min-entropy k≥n−nΩ(1)k \geq n-n^{Ω(1)}k≥n−nΩ(1), with output size nΩ(1)n^{Ω(1)}nΩ(1) and error 2−nΩ(1)2^{-n^{Ω(1)}}2−nΩ(1). We show that we can efficiently sample uniformly from any pre-image. By the connection in [CG14b], we also obtain the first explicit non-malleable codes with tampering degree ttt up to nΩ(1)n^{Ω(1)}nΩ(1), relative rate nΩ(1)/nn^{Ω(1)}/nnΩ(1)/n, and error 2−nΩ(1)2^{-n^{Ω(1)}}2−nΩ(1).
The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about 1/21/21/2, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability. (2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered. (3) Constructions where both sources have entropy rate very close to 111 and the extractor guarantees non-malleability against the tampering of both sources. We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have 0.80.80.8 entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate 12\frac 1 221​, which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.
The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about 1/21/21/2, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability. (2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered. (3) Constructions where both sources have entropy rate very close to 111 and the extractor guarantees non-malleability against the tampering of both sources. We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have 0.80.80.8 entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate 12\frac 1 221​, which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.
Motivated by the classical problem of privacy amplification, Dodis and Wichs [in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 601--610] introduced the notion of a nonmalleable extractor, significantly strengthening the notion of a strong extractor. A nonmalleable extractor is a function nmExt:{0,1}n×{0,1}d→{0,1}m\mathsf{nmExt}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^mnmExt:{0,1}n×{0,1}d→{0,1}m that takes two inputs---a weak source WWW and a uniform (independent) seed SSS---and outputs a string nmExt(W,S)\mathsf{nmExt}(W,S)nmExt(W,S) that is nearly uniform given the seed SSS as well as the value nmExt(W,S′)\mathsf{nmExt}(W,S')nmExt(W,S′) for any seed S′≠SS'\neq SS′=S that may be determined as an arbitrary function of SSS. The first explicit construction of a nonmalleable extractor was recently provided by Dodis et al. [Privacy Amplification and Non-malleable Extractors via Character Sums, preprint, arXiv:1102.5415 [cs.CR], 2011]. Their extractor works for any weak source with min-entropy rate 1/2+δ1/2+\delta1/2+δ, where δ>0\delta>0δ>0 is an arbitrary constant and outputs up to a linear number of bits but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols), its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an unconditional construction of a nonmalleable extractor with short seeds. For any integers nnn and ddd such that 2.01⋅log⁡n≤d≤n2.01\cdot\log n\leq d\leq n2.01⋅logn≤d≤n, we present an explicit construction of a nonmalleable extractor nmExt ⁣:{0,1}n×{0,1}d→{0,1}m\mathsf{nmExt}\colon\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^mnmExt:{0,1}n×{0,1}d→{0,1}m, with m=Ω(d)m=\Omega(d)m=Ω(d) and error exponentially small in mmm. The extractor works for any weak source with min-entropy rate 1/2+δ1/2+\delta1/2+δ, where δ>0\delta>0δ>0 is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of nonmalleability: its output nmExt(W,S)\mathsf{nmExt}(W,S)nmExt(W,S) is nearly uniform given the seed SSS as well as the values nmExt(W,S1),…,nmExt(W,St)\mathsf{nmExt}(W,S_1),\dots,\mathsf{nmExt}(W,S_t)nmExt(W,S1​),…,nmExt(W,St​) for several seeds S1,…,StS_1,\dots,S_tS1​,…,St​ that may be determined as an arbitrary function of SSS, as long as S∉{S1,…,St}S\notin\{S_1,\dots,S_t\}S∈/{S1​,…,St​}. By instantiating the framework of Dodis and Wichs with our nonmalleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate 1/2+δ1/2+\delta1/2+δ with asymptotically optimal entropy loss and polylogarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs, whose entropy loss is not asymptotically optimal, and the protocol of Dodis et al., whose communication complexity is linear.
We construct several explicit quantum secure non-malleable-extractors. All the quantum secure non-malleable-extractors we construct are based on the constructions by Chattopadhyay, Goyal and Li [2015] and Cohen [2015]. 1) We construct the first explicit quantum secure non-malleable-extractor for (source) min-entropy k≥poly(log⁡(nε))k \geq \textsf{poly}\left(\log \left( \frac{n}ε \right)\right)k≥poly(log(εn​)) (nnn is the length of the source and εεε is the error parameter). Previously Aggarwal, Chung, Lin, and Vidick [2019] have shown that the inner-product based non-malleable-extractor proposed by Li [2012] is quantum secure, however it required linear (in nnn) min-entropy and seed length. Using the connection between non-malleable-extractors and privacy amplification (established first in the quantum setting by Cohen and Vidick [2017]), we get a 222-round privacy amplification protocol that is secure against active quantum adversaries with communication poly(log⁡(nε))\textsf{poly}\left(\log \left( \frac{n}ε \right)\right)poly(log(εn​)), exponentially improving upon the linear communication required by the protocol due to [2019]. 2) We construct an explicit quantum secure 222-source non-malleable-extractor for min-entropy k≥n−nΩ(1)k \geq n- n^{Ω(1)}k≥n−nΩ(1), with an output of size nΩ(1)n^{Ω(1)}nΩ(1) and error 2−nΩ(1)2^{- n^{Ω(1)}}2−nΩ(1). 3) We also study their natural extensions when the tampering of the inputs is performed ttt-times. We construct explicit quantum secure ttt-non-malleable-extractors for both seeded (t=dΩ(1)t=d^{Ω(1)}t=dΩ(1)) as well as 222-source case (t=nΩ(1)t=n^{Ω(1)}t=nΩ(1)).
In this work, we consider the natural goal of designing secret sharing schemes that ensure security against an adversary who may learn some “leaked'' information about all the shares. We say that a secret sharing scheme is p-party leakage-resilient, if the secret remains statistically hidden even after a computationally unbounded adversary learns a bounded amount of leakage, where each bit of leakage adaptively and jointly depends on the shares of an adaptively chosen subset of p parties. Existing multi-party secret sharing schemes (Dziembowski and Pietrzak FOCS 07), (Goyal and Kumar STOC 18) and (Benhamouda, Degwekar, Ishai and Rabin CRYPTO 18) have focused on handling non-adaptive and individual leakage for (limited special cases of) threshold secret sharing schemes. (1) We give an unconditional compiler that transforms any secret sharing scheme on n parties into a p-party leakage-resilient one for p upto O(log n). This yields the first multi-party secret sharing schemes that are secure against adaptive or joint leakage. (2) As a natural extension, we initiate the study of leakage-resilient non-malleable secret sharing. We empower the adversary to adaptively leak from each of the shares and then use the leakage to tamper with all of them arbitrarily and independently. Leveraging our p-party leakage-resilient schemes, we compile any secret sharing scheme into a non-malleable one ensuring that any such tampering either preserves the secret or completely `destroys' it. This improves upon the non-malleable secret sharing scheme of (Goyal and Kumar CRYPTO 18) where no leakage was permitted. Leakage-resilient non-malleable codes can be seen as 2-out-of-2 schemes satisfying our guarantee and have already found many applications in cryptography. (3) Our constructions rely on a clean connection we draw to communication complexity in the well-studied number-on-forehead (NOF) model and rely on functions that have strong communication-complexity lower bounds in the NOF model (in a black-box way). We get efficient p-party leakage-resilient schemes for p upto O(log n) as our share sizes have exponential dependence on p. We observe that improving this exponential dependence, even for simultaneous, non-adaptive leakage, will lead to progress on longstanding open problems in complexity theory.