Explicit extractor for low entropy quadratic random sources
Quadratic Extractors
Computational ComplexityCryptography and Security
Summary
The paper addresses a challenge in creating random number extractors for complex sources called quadratic sources. These sources are generated by applying quadratic functions to hidden uniform bits. Previously, the best extractors needed the source to have a high level of randomness (min-entropy close to the full length). The authors present a new explicit extractor that works even when the source has much lower randomness, down to a polylogarithmic level. This overcomes a key obstacle that previous techniques, like sumset extractors, could not bypass.
What this means in practice
- •For cryptography engineers: Generate secure random keys from structured but weakly random sources with very low entropy using the new quadratic extractor design.
- •For hardware security teams: Improve randomness extraction in hardware devices where output bits depend on few hidden bits, enabling better entropy use.
A theory result. No direct application yet.
Authors
Gautam Chandrasekaran, Jesse Goodman, David Zuckerman
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.