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)
    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
  3. ; ; ; ; (, 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
  4. ; ; ; ; ; ; ; (, Nanotechnology)
    Abstract Probabilistic (p-) computing is a physics-based approach to addressing computational problems which are difficult to solve by conventional von Neumann computers. A key requirement for p-computing is the realization of fast, compact, and energy-efficient probabilistic bits. Stochastic magnetic tunnel junctions (MTJs) with low energy barriers, where the relative dwell time in each state is controlled by current, have been proposed as a candidate to implement p-bits. This approach presents challenges due to the need for precise control of a small energy barrier across large numbers of MTJs, and due to the need for an analog control signal. Here we demonstrate an alternative p-bit design based on perpendicular MTJs that uses the voltage-controlled magnetic anisotropy (VCMA) effect to create the random state of a p-bit on demand. The MTJs are stable (i.e. have large energy barriers) in the absence of voltage, and VCMA-induced dynamics are used to generate random numbers in less than 10 ns/bit. We then show a compact method of implementing p-bits by using VC-MTJs without a bias current. As a demonstration of the feasibility of the proposed p-bits and high quality of the generated random numbers, we solve up to 40 bit integer factorization problems using experimental bit-streams generated by VC-MTJs. Our proposal can impact the development of p-computers, both by supporting a fully spintronic implementation of a p-bit, and alternatively, by enabling true random number generation at low cost for ultralow-power and compact p-computers implemented in complementary metal-oxide semiconductor chips. 
    more » « less
  5. ; ; (, IEEE)
    While the existence of randomness extractors, both seeded and seedless, has been studied for many sources of randomness, currently, not much is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, online NOSF (oNOSF) sources (originally defined as SHELA sources in \cite{aggarwal_how_2020}), and almost Chor-Goldreich (CG) sources as defined in \cite{doron_almost_2023}. We will think of these sources as a sequence of random variables $$\mathbf{X}=\mathbf{X}_1,\dots,\mathbf{X}_\ell$$ on $$\ell$$ symbols where at least $$g$$ out of these $$\ell$$ symbols are ``good'' (i.e., have some min-entropy requirement), denoted as a $$(g,\ell)$$-source, and the remaining ``bad'' $$\ell-g$$ symbols may adversarially depend on these $$g$$ good blocks. The difference between each of these sources is realized by restrictions on the power of the adversary, with the adversary in NOSF sources having no restrictions. Prior to our work, the only known seedless condenser upper or lower bound in these settings is due to \cite{doron_almost_2023}, where they explicitly construct a seedless condenser for a restricted subset of $$(g,\ell)$$-adversarial CG sources. The following are our main results concerning seedless condensers for each of these sources. \begin{enumerate} \item oNOSF sources \begin{enumerate} \item When $$g\leq\ell/2$, we prove that condensing with error 0.99 above rate $$\frac{1}{\lfloor \ell/g \rfloor}$$ is impossible. In fact, we show that this is tight. \item Quite surprisingly, for $$g> \ell/2$$, we show the existence of excellent condensers for uniform oNOSF sources. In addition, we show the existence of similar condensers for oNOSF sources with only logarithmic min-entropy. Our results are based on a new type of two-source extractors, called \emph{output-light two-source extractors}, that we introduce and prove the existence of. \end{enumerate} \item Adversarial CG sources \begin{enumerate} \item We observe that uniform adversarial CG sources are equivalent to uniform oNOSF sources and consequently inherit the same results. \item We show that one cannot condense beyond the min-entropy gap of each block or condense low min-entropy CG sources above rate $1/2$$. \end{enumerate} \item NOSF sources \begin{enumerate} \item We show that condensing with constant error above rate $$\frac{g}{\ell}$ is impossible for uniform NOSF sources for any $$g$$ and $$\ell$$, thus ruling out the possibility of any non-trivial condensing. This shows an interesting distinction between NOSF and oNOSF sources. \end{enumerate} \end{enumerate} 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email