Document Open Access Logo

Dimension, Pseudorandomness and Extraction of Pseudorandomness

Authors Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.221.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Manindra Agrawal
Diptarka Chakraborty
Debarati Das
Satyadev Nandakumar

Cite AsGet BibTex

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, and Satyadev Nandakumar. Dimension, Pseudorandomness and Extraction of Pseudorandomness. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 221-235, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.FSTTCS.2015.221

Abstract

In this paper we propose a quantification of distributions on a set of strings, in terms of how close to pseudorandom a distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences introduced by Lutz. Adapting Hitchcock's work, we also show that the logarithmic loss incurred by a predictor on a distribution is quantitatively equivalent to the notion of dimension we define. Roughly, this captures the equivalence between pseudorandomness defined via indistinguishability and via unpredictability. Later we show some natural properties of our notion of dimension. We also do a comparative study among our proposed notion of dimension and two well known notions of computational analogue of entropy, namely HILL-type pseudo min-entropy and next-bit pseudo Shannon entropy. Further, we apply our quantification to the following problem. If we know that the dimension of a distribution on the set of n-length strings is s in (0,1], can we extract out O(sn) pseudorandom bits out of the distribution? We show that to construct such extractor, one need at least Omega(log n) bits of pure randomness. However, it is still open to do the same using O(log n) random bits. We show that deterministic extraction is possible in a special case - analogous to the bit-fixing sources introduced by Chor et al., which we term nonpseudorandom bit-fixing source. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic pseudorandom extractor for this source. By the end, we make a little progress towards P vs. BPP problem by showing that existence of optimal stretching function that stretches O(log n) input bits to produce n output bits such that output distribution has dimension s in (0,1], implies P=BPP.
Keywords
  • Pseudorandomness
  • Dimension
  • Martingale
  • Unpredictability
  • Pseudoentropy
  • Pseudorandom Extractor
  • Hard Function

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. K. B. Athreya, J. M. Hitchcock, J. H. Lutz, and E. Mayordomo. Effective strong dimension, algorithmic information, and computational complexity. SIAM Journal on Computing, 37:671-705, 2007. Google Scholar
  2. K. B. Athreya and S. N. Lahiri. Measure Theory and Probability Theory. Springer Verlag, 2006. Google Scholar
  3. Boaz Barak, Ronen Shaltiel, and Avi Wigderson. Computational analogues of entropy. In Sanjeev Arora, Klaus Jansen, José D. P. Rolim, and Amit Sahai, editors, RANDOM-APPROX, volume 2764 of Lecture Notes in Computer Science, pages 200-215. Springer, 2003. Google Scholar
  4. Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput., 13(4):850-864, November 1984. Google Scholar
  5. Benny Chor, Oded Goldreich, Johan Håstad, Joel Freidmann, Steven Rudich, and Roman Smolensky. The bit extraction problem or t-resilient functions, 1985. Google Scholar
  6. T. Cover. Universal gambling schemes and the complexity measures of Kolmogorov and Chaitin. Technical Report 12, Stanford University Department of Statistics, October 1974. Google Scholar
  7. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, 2006. Google Scholar
  8. Ariel Gabizon, Ran Raz, and Ronen Shaltiel. Deterministic extractors for bit-fixing sources by obtaining an independent seed, 2005. Google Scholar
  9. Oded Goldreich. The Foundations of Cryptography - Volume 1, Basic Techniques. Cambridge University Press, 2001. Google Scholar
  10. Shafi Goldwasser and Silvio Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270-299, 1984. Google Scholar
  11. Iftach Haitner, Omer Reingold, and Salil P. Vadhan. Efficiency improvements in constructing pseudorandom generators from one-way functions. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 437-446, 2010. Google Scholar
  12. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364-1396, 1999. Google Scholar
  13. J. M. Hitchcock. Effective Fractal Dimension Bibliography, http://www.cs.uwyo.edu/ ∼jhitchco/bib/dim.shtml. (current April, 2011). URL: http://www.cs.uwyo.edu/~jhitchco/bib/dim.shtml.
  14. J. M. Hitchcock. Resource Bounded Measure - Bibliography, http://www.cs.uwyo.edu/ ∼jhitchco/bib/rbm.shtml. (current April, 2011). URL: http://www.cs.uwyo.edu/~jhitchco/bib/rmb.shtml.
  15. J. M. Hitchcock. Fractal dimension and logarithmic loss unpredictability. Theoretical Computer Science, 304(1-3):431-441, 2003. Google Scholar
  16. John M. Hitchcock. Fractal dimension and logarithmic loss unpredictability, 2004. Google Scholar
  17. Chun-Yuan Hsiao, Chi-Jen Lu, and Leonid Reyzin. Conditional computational entropy, or toward separating pseudoentropy from compressibility. In Moni Naor, editor, Advances in Cryptology - EUROCRYPT 2007, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007, Proceedings, volume 4515 of Lecture Notes in Computer Science, pages 169-186. Springer, 2007. Google Scholar
  18. Russell Impagliazzo and Avi Wigderson. P=BPP unless E has sub-exponential circuits: Derandomizing the xor lemma (preliminary version). In In Proceedings of the 29th STOC, pages 220-229. ACM Press, 1996. Google Scholar
  19. Jesse Kamp and David Zuckerman. Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. In In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 92-101, 2003. Google Scholar
  20. Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, and Avi Wigderson. Extractors: optimal up to constant factors. In Lawrence L. Larmore and Michel X. Goemans, editors, STOC, pages 602-611. ACM, 2003. Google Scholar
  21. J. H. Lutz. Gales and the constructive dimension of individual sequences. In Proceedings of the 27th International Colloquium on Automata, Languages, and Programming, pages 902-913, 2000. Revised as [22]. Google Scholar
  22. J. H. Lutz. The dimensions of individual strings and sequences. Information and Computation, 187:49-79, 2003. Preliminary version appeared as [21]. Google Scholar
  23. Jack H. Lutz. Dimension in complexity classes. SIAM J. Comput., 32(5):1236-1259, 2003. Google Scholar
  24. Noam Nisan and Amnon Ta-Shma. Extracting randomness: A survey and new constructions. J. Comput. Syst. Sci., 58(1):148-173, 1999. Google Scholar
  25. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  26. Noam Nisan and David Zuckerman. More deterministic simulation in logspace. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 235-244. ACM, 1993. Google Scholar
  27. Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52:43-52, 1996. Google Scholar
  28. Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Discrete Mathematics, 13:2000, 2000. Google Scholar
  29. Ronen Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the EATCS, 77:67-95, 2002. Google Scholar
  30. Luca Trevisan and Salil P. Vadhan. Extracting randomness from samplable distributions. In FOCS, pages 32-42. IEEE Computer Society, 2000. Google Scholar
  31. Salil P. Vadhan and Colin Jia Zheng. Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19-22, 2012, pages 817-836, 2012. Google Scholar
  32. Andrew C. Yao. Theory and application of trapdoor functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, SFCS'82, pages 80-91, Washington, DC, USA, 1982. IEEE Computer Society. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact