Deterministic extractors for small-space sources

ABSTRACT

We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on (0,1)ⁿ as sources generated by width 2^s 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=Ω(β³ 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: Boaz Barak , Russell Impagliazzo , Avi Wigderson, Extracting Randomness Using Few Independent Sources, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.384-393, October 17-19, 2004 [doi>10.1109/FOCS.2004.29]
• 2: Boaz Barak , Guy Kindler , Ronen Shaltiel , Benny Sudakov , Avi Wigderson, Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060592]
• 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: Charles H. Bennett , Gilles Brassard , Jean-Marc Robert, Privacy amplification by public discussion, SIAM Journal on Computing, v.17 n.2, p.210-229, April 1988 [doi>10.1137/0217014]
• 5: M Blum, Independent unbiased coin flips from a correlated biased source:80a finite state Markov chain, Combinatorica, v.6 n.2, p.97-108, 1986 [doi>10.1007/BF02579167]
• 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: Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
• 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: Ariel Gabizon , Ran Raz , Ronen Shaltiel, Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.394-403, October 17-19, 2004 [doi>10.1109/FOCS.2004.21]
• 16: B. Jun and P. Kocher. The Intel random number generator, 1999. http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf.
• 17: Jesse Kamp , David Zuckerman, Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.92, October 11-14, 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: Ueli M. Maurer , Stefan Wolf, Privacy Amplification Secure Against Active Adversaries, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.307-321, August 17-21, 1997
• 22: Naom Nisan , Amnon Ta-Shma, Extracting randomness: a survey and new constructions, Journal of Computer and System Sciences, v.58 n.1, p.148-173, Feb. 1999 [doi>10.1006/jcss.1997.1546 ]
• 23: Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004 ]
• 24: Anup Rao, Extractors for a constant number of polynomially small min-entropy independent sources, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132589]
• 25: Ran Raz, Extractors with weak random seeds, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060593]
• 26: Miklos Santha , Umesh V Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences, v.33 n.1, p.75-87, Aug. 1986 [doi>10.1016/0022-0000(86)90044-9]
• 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: Amnon Ta-Shma, On extracting randomness from weak random sources (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.276-285, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237877]
• 30: L. Trevisan , S. Vadhan, Extracting randomness from samplable distributions, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.32, November 12-14, 2000
• 31: Umesh Virkumar Vazirani, Randomness, adversaries and computation (random polynomial time), 1986
• 32: Umesh Vazirani, Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources, Combinatorica, v.7 n.4, p.375-392, Dec, 1987 [doi>10.1007/BF02579325]
• 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.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
pseudorandomness, randomness extractors