Paper 2026/2775

Quadratic Extractors

Gautam Chandrasekaran, The University of Texas at Austin
Jesse Goodman, Simons Institute for the Theory of Computing, Berkeley
David Zuckerman, The University of Texas at Austin
Abstract

A quadratic source is a random variable $X\sim\mathbb{F}_2^n$ generated by applying $n$ quadratics to a hidden uniform string. Previously, the best-known explicit extractor for this model required min-entropy roughly $k=n-\sqrt{\log n}$. In this paper, we give an explicit construction for min-entropy $k=\mathrm{polylog}(n)$. Even for the special case of $2$-local sources, where each bit of $X$ depends on two hidden uniform bits, achieving an entropy requirement below $k=\sqrt{n}$ was an important open problem. This is because such sources provably cannot be reduced (in a black-box manner) to our most powerful general-purpose seedless extractor, known as a sumset extractor. Our new extractor bypasses this barrier, providing the first explicit construction to go beyond sumset extraction.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Contact author(s)
gautamc @ cs utexas edu
jpmgoodman @ gmail com
diz @ cs utexas edu
History
2026-11-08: approved
2026-11-05: received
See all versions
Short URL
https://ia.cr/2026/2775
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2775,
      author = {Gautam Chandrasekaran and Jesse Goodman and David Zuckerman},
      title = {Quadratic Extractors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2775},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2775}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.