skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Low-Degree Polynomials Extract From Local Sources
We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, this model was introduced by De and Watson (TOCT 2012) and Viola (SICOMP 2014), and is closely related to sources generated by AC⁰ circuits and bounded-width branching programs. In particular, extractors for local sources also work for sources generated by these classical computational models. Despite being introduced a decade ago, little progress has been made on improving the entropy requirement for extracting from local sources. The current best explicit extractors require entropy n^{1/2}, and follow via a reduction to affine extractors. To start, we prove a barrier showing that one cannot hope to improve this entropy requirement via a black-box reduction of this form. In particular, new techniques are needed. In our main result, we seek to answer whether low-degree polynomials (over 𝔽₂) hold potential for breaking this barrier. We answer this question in the positive, and fully characterize the power of low-degree polynomials as extractors for local sources. More precisely, we show that a random degree r polynomial is a low-error extractor for n-bit local sources with min-entropy Ω(r(nlog n)^{1/r}), and we show that this is tight. Our result leverages several new ingredients, which may be of independent interest. Our existential result relies on a new reduction from local sources to a more structured family, known as local non-oblivious bit-fixing sources. To show its tightness, we prove a "local version" of a structural result by Cohen and Tal (RANDOM 2015), which relies on a new "low-weight" Chevalley-Warning theorem.  more » « less
Award ID(s):
1845349
PAR ID:
10408353
Author(s) / Creator(s):
; ; ; ;
Editor(s):
Bojanczyk, Mikolaj; Merelli, Emanuela; Woodruff, David P.
Date Published:
Journal Name:
Leibniz international proceedings in informatics
Volume:
229
Issue:
10
ISSN:
1868-8969
Page Range / eLocation ID:
1-20
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Guruswami, Venkatesan (Ed.)
    We explicitly construct the first nontrivial extractors for degree d ≥ 2 polynomial sources over 𝔽₂. Our extractor requires min-entropy k ≥ n - (√{log n})/((log log n / d)^{d/2}). Previously, no constructions were known, even for min-entropy k ≥ n-1. A key ingredient in our construction is an input reduction lemma, which allows us to assume that any polynomial source with min-entropy k can be generated by O(k) uniformly random bits. We also provide strong formal evidence that polynomial sources are unusually challenging to extract from, by showing that even our most powerful general purpose extractors cannot handle polynomial sources with min-entropy below k ≥ n-o(n). In more detail, we show that sumset extractors cannot even disperse from degree 2 polynomial sources with min-entropy k ≥ n-O(n/log log n). In fact, this impossibility result even holds for a more specialized family of sources that we introduce, called polynomial non-oblivious bit-fixing (NOBF) sources. Polynomial NOBF sources are a natural new family of algebraic sources that lie at the intersection of polynomial and variety sources, and thus our impossibility result applies to both of these classical settings. This is especially surprising, since we do have variety extractors that slightly beat this barrier - implying that sumset extractors are not a panacea in the world of seedless extraction. 
    more » « less
  2. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)
    Non-malleable extractors are generalizations and strengthening of standard randomness extractors, that are resilient to adversarial tampering. Such extractors have wide applications in cryptography and have become important cornerstones in recent breakthroughs of explicit constructions of two-source extractors and affine extractors for small entropy. However, explicit constructions of non-malleable extractors appear to be much harder than standard extractors. Indeed, in the well-studied models of two-source and affine non-malleable extractors, the previous best constructions only work for entropy rate > 2/3 and 1-γ for some small constant γ > 0 respectively by Li (FOCS' 23). In this paper, we present explicit constructions of two-source and affine non-malleable extractors that match the state-of-the-art constructions of standard ones for small entropy. Our main results include: - Two-source and affine non-malleable extractors (over 𝖥₂) for sources on n bits with min-entropy k ≥ log^C n and polynomially small error, matching the parameters of standard extractors by Chattopadhyay and Zuckerman (STOC' 16, Annals of Mathematics' 19) and Li (FOCS' 16). - Two-source and affine non-malleable extractors (over 𝖥₂) for sources on n bits with min-entropy k = O(log n) and constant error, matching the parameters of standard extractors by Li (FOCS' 23). Our constructions significantly improve previous results, and the parameters (entropy requirement and error) are the best possible without first improving the constructions of standard extractors. In addition, our improved affine non-malleable extractors give strong lower bounds for a certain kind of read-once linear branching programs, recently introduced by Gryaznov, Pudlák, and Talebanfard (CCC' 22) as a generalization of several well studied computational models. These bounds match the previously best-known average-case hardness results given by Chattopadhyay and Liao (CCC' 23) and Li (FOCS' 23), where the branching program size lower bounds are close to optimal, but the explicit functions we use here are different. Our results also suggest a possible deeper connection between non-malleable extractors and standard ones. 
    more » « less
  3. ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Kumar, Amit; Ron-Zewi, Noga (Ed.)
    For S ⊆ 𝔽ⁿ, consider the linear space of restrictions of degree-d polynomials to S. The Hilbert function of S, denoted h_S(d,𝔽), is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets S of arbitrary finite grids in 𝔽ⁿ with a fixed size |S|. We achieve this by proving that this value coincides with a combinatorial quantity, namely the smallest number of low Hamming weight points in a down-closed set of size |S|. Understanding the smallest values of Hilbert functions is closely related to the study of degree-d closure of sets, a notion introduced by Nie and Wang (Journal of Combinatorial Theory, Series A, 2015). We use bounds on the Hilbert function to obtain a tight bound on the size of degree-d closures of subsets of 𝔽_qⁿ, which answers a question posed by Doron, Ta-Shma, and Tell (Computational Complexity, 2022). We use the bounds on the Hilbert function and degree-d closure of sets to prove that a random low-degree polynomial is an extractor for samplable randomness sources. Most notably, we prove the existence of low-degree extractors and dispersers for sources generated by constant-degree polynomials and polynomial-size circuits. Until recently, even the existence of arbitrary deterministic extractors for such sources was not known. 
    more » « less
  4. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Santhanam, Rahul (Ed.)
    Affine extractors give some of the best-known lower bounds for various computational models, such as AC⁰ circuits, parity decision trees, and general Boolean circuits. However, they are not known to give strong lower bounds for read-once branching programs (ROBPs). In a recent work, Gryaznov, Pudlák, and Talebanfard (CCC' 22) introduced a stronger version of affine extractors known as directional affine extractors, together with a generalization of ROBPs where each node can make linear queries, and showed that the former implies strong lower bound for a certain type of the latter known as strongly read-once linear branching programs (SROLBPs). Their main result gives explicit constructions of directional affine extractors for entropy k > 2n/3, which implies average-case complexity 2^{n/3-o(n)} against SROLBPs with exponentially small correlation. A follow-up work by Chattopadhyay and Liao (CCC' 23) improves the hardness to 2^{n-o(n)} at the price of increasing the correlation to polynomially large, via a new connection to sumset extractors introduced by Chattopadhyay and Li (STOC' 16) and explicit constructions of such extractors by Chattopadhyay and Liao (STOC' 22). Both works left open the questions of better constructions of directional affine extractors and improved average-case complexity against SROLBPs in the regime of small correlation. This paper provides a much more in-depth study of directional affine extractors, SROLBPs, and ROBPs. Our main results include: - An explicit construction of directional affine extractors with k = o(n) and exponentially small error, which gives average-case complexity 2^{n-o(n)} against SROLBPs with exponentially small correlation, thus answering the two open questions raised in previous works. - An explicit function in AC⁰ that gives average-case complexity 2^{(1-δ)n} against ROBPs with negligible correlation, for any constant δ > 0. Previously, no such average-case hardness is known, and the best size lower bound for any function in AC⁰ against ROBPs is 2^Ω(n). One of the key ingredients in our constructions is a new linear somewhere condenser for affine sources, which is based on dimension expanders. The condenser also leads to an unconditional improvement of the entropy requirement of explicit affine extractors with negligible error. We further show that the condenser also works for general weak random sources, under the Polynomial Freiman-Ruzsa Theorem in 𝖥₂ⁿ, recently proved by Gowers, Green, Manners, and Tao (arXiv' 23). 
    more » « less
  5. ; ; ; ; (, Advances in Cryptology - Asiacrypt)
    We give the first constructions in the plain model of 1) nonmalleable digital lockers (Canetti and Varia, TCC 2009) and 2) robust fuzzy extractors (Boyen et al., Eurocrypt 2005) that secure sources with entropy below 1/2 of their length. Constructions were previously only known for both primitives assuming random oracles or a common reference string (CRS). Along the way, we define a new primitive called a nonmalleable point function obfuscation with associated data. The associated data is public but protected from all tampering. We use the same paradigm to then extend this to digital lockers. Our constructions achieve nonmalleability over the output point by placing a CRS into the associated data and using an appropriate non-interactive zero-knowledge proof. Tampering is protected against the input point over low-degree polynomials and over any tampering to the output point and associated data. Our constructions achieve virtual black box security. These constructions are then used to create robust fuzzy extractors that can support low-entropy sources in the plain model. By using the geometric structure of a syndrome secure sketch (Dodis et al., SIAM Journal on Computing 2008), the adversary’s tampering function can always be expressed as a low-degree polynomial; thus, the protection provided by the constructed nonmalleable objects suffices. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email