Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-176 | 12th November 2024 02:54

Nearly-Linear Time Seeded Extractors with Short Seeds

RSS-Feed




TR24-176
Authors: Dean Doron, Joao Ribeiro
Publication: 17th November 2024 16:23
Downloads: 50
Keywords: 


Abstract:

Seeded extractors are fundamental objects in pseudorandomness and cryptography, and a deep line of work has designed polynomial-time seeded extractors with nearly-optimal parameters. However, existing constructions of seeded extractors with short seed length and large output length run in time $\Omega(n \log(1/\varepsilon))$ and often slower, where $n$ is the input source length and $\varepsilon$ is the error of the extractor. Since cryptographic applications of extractors require $\varepsilon$ to be small, the resulting runtime makes these extractors unusable in practice.

Motivated by this, we explore constructions of strong seeded extractors with short seeds computable in nearly-linear time $O(n \log^c n)$, for any error $\varepsilon$. We show that an appropriate combination of modern condensers and classical approaches for constructing seeded extractors for high min-entropy sources yields strong extractors for $n$-bit sources with any min-entropy $k$ and any target error $\varepsilon$ with seed length $d=O(\log(n/\varepsilon))$ and output length $m=(1-\eta)k$ for an arbitrarily small constant $\eta>0$, running in nearly-linear time, after a reasonable one-time preprocessing step (finding a primitive element of $\mathbb{F}_q$ with $q=\mathrm{poly}(n/\varepsilon)$ a power of $2$) that is only required when $k0$ and $\log^*$ the iterated logarithm, and which can be implemented in time $\mathrm{polylog}(n/\varepsilon)$ under mild conditions on $q$. As a second contribution, we give an instantiation of Trevisan's extractor that can be evaluated in \emph{truly} linear time in the RAM model, as long as the number of output bits is at most $\frac{n}{\log(1/\varepsilon)\mathrm{polylog}(n)}$. Previous fast implementations of Trevisan’s extractor ran in $\widetilde{O}(n)$ time in this setting. In particular, these extractors directly yield privacy amplification protocols with the same time complexity and output length, and communication complexity equal to their seed length.



ISSN 1433-8092 | Imprint