Better short-seed extractors against quantum knowledge
Avraham Ben-Aroya, Amnon Ta‐Shma · 2010
We construct a strong extractor against quantum storage that works for every min-entropy k, has logarithmic seed length, and outputs Ω(k) bits, provided that the quantum adversary has at most βk qubits of memory, for any β < 12 . Previous constructions required poly-logarithmic seed length to output such a fraction of the entropy and, in addition, required super-logarithmic seed length for small values of k. The construction works by first condensing the source (with minimal entropy-loss) and then applying an extractor that works well against quantum adversaries, when the source is close to uniform. We also obtain an improved construction of a strong extractor against quantum knowledge, in the high guessing entropy regime. Specifically, we construct an extractor that uses a logarithmic seed length and extracts Ω(n) bits from any source over {0, 1}, provided that the guessing entropy of the source conditioned on the quantum adversary’s state is at least (1−β)n, for any β < 12 . Previous constructions required poly-logarithmic seed length to output Ω(n) bits from such sources.