skip to main content
10.1145/1132516.1132613acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Deterministic extractors for small-space sources

Published: 21 May 2006 Publication History

Abstract

We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on (0,1)n as sources generated by width 2s branching programs: For every constant δ>0, we can extract .99 δ n bits that are exponentially close to uniform (in variation distance) from space s sources of min-entropy δ n, where s=Ω(n). In addition, assuming an efficient deterministic algorithm for finding large primes, there is a constant η > 0 such that for any δ>n, we can extract m=(δ-δ)n bits that are exponentially close to uniform from space s sources with min-entropy δ n, where s=Ω(β3 n). Previously, nothing was known for δ ≤ 1/2, even for space 0.Our results are obtained by a reduction to a new class of sources that we call independent-symbol sources, which generalize both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a string of n independent symbols over a d symbol alphabet with min-entropy k. We give deterministic extractors for such sources when k is as small as polylog(n), for small enough d.

References

[1]
B. Barak, R. Impagliazzo, and A. Wigderson. Extracting randomness using few independent sources. In 45th FOCS, pages 384--393, 2004.
[2]
B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson. Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. In 37th STOC, pages 1--10, 2005.
[3]
M. Ben-Or and N. Linial. Collective coin flipping. In S. Micali, editor, Randomness and Computation, pages 91--115. Academic Press, New York, 1990.
[4]
C. H. Bennett, G. Brassard, and J. Robert. Privacy amplification by public discussion. SICOMP, 17(2):210--229, Apr. 1988.
[5]
M. Blum. Independent unbiased coin flips from a correlated biased source: a finite Markov chain. Combinatorica, 6(2):97--108, 1986.
[6]
J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1:1--32, 2005.
[7]
J. Bourgain, A. Glibichuk, and S. Konyagin. Estimates for the number of sums and products and for exponential sums in fields of prime order. J. London Math. Soc., 2005. To appear.
[8]
R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, and A. Sahai. Exposure-resilient functions and all-or-nothing transforms. In B. Preneel, editor, Advances in Cryptology --- EUROCRYPT 2000, volume 1807 of LNCS, pages 453--469. Springer-Verlag, May 2000.
[9]
B. Chor, J. Friedman, O. Goldreich, J. Håstad, S. Rudich, and R. Smolensky. The bit extraction problem or t--resilient functions. In 26th FOCS, pages 396--407, 1985.
[10]
B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SICOMP, 17(2):230--261, 1988.
[11]
A. Cohen and A. Wigderson. Dispersers, deterministic amplification, and weak random sources. In 30th FOCS, pages 14--19, 1989.
[12]
H. Cramer. On the order of magnitude of the difference between consecutive prime numbers. Acta Arithmetica, pages 23--46, 1937.
[13]
Y. Dodis. Impossibility of black-box reduction from non-adaptively to adaptively secure coin-flipping. Unpublished manuscript, April 2000.
[14]
Z. Dvir and R. Raz. Analyzing linear mergers. Technical Report TR05-25, ECCC, 2005.
[15]
A. Gabizon, R. Raz, and R. Shaltiel. Deterministic extractors for bit-fixing sources by obtaining an independent seed. In 45th FOCS, pages 394--403, 2004.
[16]
B. Jun and P. Kocher. The Intel random number generator, 1999. http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf.
[17]
J. Kamp and D. Zuckerman. Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. In 44th FOCS, pages 92--101, 2003.
[18]
R. Koenig and U. Maurer. Extracting randomness from generalized symbol-fixing and markov sources. In Proceedings of 2004 IEEE International Symposium on Information Theory, page 232, June 2004.
[19]
R. Koenig and U. Maurer. Generalized strong extractors and deterministic privacy amplification. In N. Smart, editor, Cryptography and Coding 2005, volume 3796 of LNCS, pages 322--339. Springer-Verlag, Dec. 2005.
[20]
D. Lichtenstein, N. Linial, and M. Saks. Some extremal problems arising from discrete control processes. Combinatorica, 9(3):269--287, 1989.
[21]
U. Maurer and S. Wolf. Privacy amplification secure against active adversaries. In B. S. K. Jr., editor, Advances in Cryptology --- CRYPTO '97, volume 1294 of LNCS, pages 307--321. Springer-Verlag, Aug. 1997.
[22]
N. Nisan and A. Ta-Shma. Extracting randomness: A survey and new constructions. JCSS, 58:148--173, 1999.
[23]
N. Nisan and D. Zuckerman. Randomness is linear in space. JCSS, 52(1):43--52, 1996.
[24]
A. Rao. Extractors for a constant number of polynomially small min-entropy independent sources. In 38th STOC, 2006.
[25]
R. Raz. Extractors with weak random seeds. In 37th STOC, pages 11--20, 2005.
[26]
M. Santha and U. V. Vazirani. Generating quasi-random sequences from semi-random sources. JCSS, 33:75--87, 1986.
[27]
R. Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the European Association for Theoretical Computer Science, (77):67--95, June 2002.
[28]
R. Shaltiel. How to get more mileage from randomness extractors. Technical Report TR05-145, ECCC, 2005.
[29]
A. Ta-Shma. On extracting randomness from weak random sources. In 28th STOC, pages 276--285, 1996.
[30]
L. Trevisan and S. P. Vadhan. Extracting randomness from samplable distributions. In 41st FOCS, pages 32--42, 2000.
[31]
U. V. Vazirani. Randomness, Adversaries and Computation. PhD thesis, EECS, University of California at Berkeley, 1986.
[32]
U. V. Vazirani. Strong communication complexity or generating quasirandom sequences from two communicating semirandom sources. Combinatorica, 7(4):375--392, 1987.
[33]
U. V. Vazirani and V. V. Vazirani. Random polynomial time is equal to slightly-random polynomial time. In 26th FOCS, pages 417--428, 1985.
[34]
J. von Neumann. Various techniques used in connection with random digits. National Bureau of Standards, Applied Mathematics Series, 12:36--38, 1951.
[35]
A. Wigderson and D. Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica, 19(1):125--138, 1999.
[36]
D. Zuckerman. Simulating BPP using a general weak random source. Algorithmica, 16:367--391, 1996.

Cited By

View all
  • (2023)Almost Chor-Goldreich Sources and Adversarial Random WalksProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585134(1-9)Online publication date: 2-Jun-2023
  • (2022)Affine Extractors for Almost Logarithmic Entropy2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00067(622-633)Online publication date: Feb-2022
  • (2022)Improved Extractors for Small-Space Sources2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00066(610-621)Online publication date: Feb-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing
May 2006
786 pages
ISBN:1595931341
DOI:10.1145/1132516
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 May 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. pseudorandomness
  2. randomness extractors

Qualifiers

  • Article

Conference

STOC06
Sponsor:
STOC06: Symposium on Theory of Computing
May 21 - 23, 2006
WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)2
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Almost Chor-Goldreich Sources and Adversarial Random WalksProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585134(1-9)Online publication date: 2-Jun-2023
  • (2022)Affine Extractors for Almost Logarithmic Entropy2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00067(622-633)Online publication date: Feb-2022
  • (2022)Improved Extractors for Small-Space Sources2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00066(610-621)Online publication date: Feb-2022
  • (2020)Extractors for adversarial sources via extremal hypergraphsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384339(1184-1197)Online publication date: 22-Jun-2020
  • (2020)Extractors and Secret Sharing Against Bounded Collusion Protocols2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00117(1226-1242)Online publication date: Nov-2020
  • (2016)The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2016.29(197-208)Online publication date: Oct-2016
  • (2015)Three-Source Extractors for Polylogarithmic Min-EntropyProceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2015.58(863-882)Online publication date: 17-Oct-2015
  • (2015)Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani SourcesAutomata, Languages, and Programming10.1007/978-3-662-47672-7_12(143-154)Online publication date: 20-Jun-2015
  • (2014)Leakage-resilient coin tossingDistributed Computing10.1007/s00446-013-0206-z27:3(147-164)Online publication date: 1-Jun-2014
  • (2012)Two-source extractors for leaky sources2012 IEEE Information Theory Workshop10.1109/ITW.2012.6404713(452-456)Online publication date: Sep-2012
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media