Document Open Access Logo

Randomness Extraction in AC0 and with Small Locality

Authors Kuan Cheng, Xin Li

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.37.pdf
  • Filesize: 0.57 MB
  • 20 pages

Document Identifiers

Author Details

Kuan Cheng
  • Department of Computer Science, Johns Hopkins University.
Xin Li
  • Department of Computer Science, Johns Hopkins University.

Funding

  • Cheng, Kuan: Supported in part by NSF award CCF-1617713.
  • Li, Xin: Supported in part by NSF award CCF-1617713.

Cite As Get BibTex

Kuan Cheng and Xin Li. Randomness Extraction in AC0 and with Small Locality. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.37

Abstract

Randomness extractors, which extract high quality (almost-uniform) random bits from biased random sources, are important objects both in theory and in practice. While there have been significant progress in obtaining near optimal constructions of randomness extractors in various settings, the computational complexity of randomness extractors is still much less studied. In particular, it is not clear whether randomness extractors with good parameters can be computed in several interesting complexity classes that are much weaker than P.
In this paper we study randomness extractors in the following two models of computation: (1) constant-depth circuits (AC^0), and (2) the local computation model. Previous work in these models, such as [Viola, 2005], [Goldreich et al., 2015] and [Bogdanov and Guo, 2013], only achieve constructions with weak parameters. In this work we give explicit constructions of randomness extractors with much better parameters. Our results on AC^0 extractors refute a conjecture in [Goldreich et al., 2015] and answer several open problems there. We also provide a lower bound on the error of extractors in AC^0, which together with the entropy lower bound in [Viola, 2005; Goldreich et al., 2015] almost completely characterizes extractors in this class. Our results on local extractors also significantly improve the seed length in [Bogdanov and Guo, 2013]. As an application, we use our AC^0 extractors to study pseudorandom generators in AC^0, and show that we can construct both cryptographic pseudorandom generators (under reasonable computational assumptions) and unconditional pseudorandom generators for space bounded computation with very good parameters.
Our constructions combine several previous techniques in randomness extractors, as well as introduce new techniques to reduce or preserve the complexity of extractors, which may be of independent interest. These include (1) a general way to reduce the error of strong seeded extractors while preserving the AC^0 property and small locality, and (2) a seeded randomness condenser with small locality.

Subject Classification

ACM Subject Classification
  • Theory of computation → Expander graphs and randomness extractors
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Randomness Extraction
  • AC0
  • Locality
  • Pseudorandom Generator

Metrics

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

Related Versions

References

  1. M. Ajtai and N. Linial. The influence of large coalitions. Combinatorica, 13(2):129-145, 1993. Google Scholar
  2. Benny Applebaum. Pseudorandom generators with long stretch and low locality from random local one-way functions. SIAM Journal on Computing, 42(5):2008-2037, 2013. Google Scholar
  3. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in nc 0. SIAM Journal on Computing, 2006. Google Scholar
  4. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. On pseudorandom generators with linear stretch in nc0. Computational Complexity, 17(1):38-69, 2008. Google Scholar
  5. L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. Bpp has subexponential simulation unless Exptime has publishable proofs. Computational Complexity, 3:307-318, 1993. Google Scholar
  6. Andrej Bogdanov and Siyao Guo. Sparse extractor families for all the entropy. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 553-560. ACM, 2013. Google Scholar
  7. Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai. Exposure-resilient functions and all-or-nothing transforms. In Bart Preneel, editor, Advances in Cryptology - EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 453-469. Springer-Verlag, 2000. Google Scholar
  8. J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143-154, 1979. Google Scholar
  9. Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, 2016. Google Scholar
  10. Kuan Cheng and Xin Li. Randomness extraction in ac0 and with small locality. arXiv preprint arXiv:1602.01530, 2016. Google Scholar
  11. Anindya De and Luca Trevisan. Extractors using hardness amplification. In RANDOM 2009, 13th International Workshop on Randomization and Approximation Techniques in Computer Science, 2009. Google Scholar
  12. Stefan Dziembowski and Ueli Maurer. Tight security proofs for the bounded-storage model. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 341-350. ACM, 2002. Google Scholar
  13. Ariel Gabizon, Ran Raz, and Ronen Shaltiel. Deterministic extractors for bit-fixing sources by obtaining an independent seed. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages 394-403, 2004. Google Scholar
  14. Oded Goldreich. Candidate one-way functions based on expander graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 76-87. Springer, 2011. Google Scholar
  15. Oded Goldreich, Emanuele Viola, and Avi Wigderson. On randomness extraction in ac0. In 30th Conference on Computational Complexity (CCC 2015), volume 33, pages 601-668. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  16. M. Grohe and N. Schweikardt. Lower bounds for sorting with few random accesses to external memory. In Symposium on Principles of Database Systems (PODS), pages 238-249, 2005. Google Scholar
  17. Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM, 56(4), 2009. Google Scholar
  18. J. Håstad. Almost optimal lower bounds for small depth circuits. In S. Micali, editor, Randomness and Computation, volume 5, pages 143-170. JAI Press, 1989. Google Scholar
  19. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Construction of a pseudo-random generator from any one-way function. SIAM Journal on Computing, 28:12-24, 1993. Google Scholar
  20. R. Impagliazzo, N. Nisan, and A. Wigderson. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 356-364, 1994. Google Scholar
  21. R. Impagliazzo and A. Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 220-229, 1997. Google Scholar
  22. Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on, pages 538-545. IEEE, 1995. Google Scholar
  23. Russell Impagliazzo and Moni Naor. Efficient cryptographic schemes provably as secure as subset sum. Journal of cryptology, 9(4):199-216, 1996. Google Scholar
  24. Jesse Kamp and David Zuckerman. Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. SIAM Journal on Computing, 36(5):1231-1247, 2007. Google Scholar
  25. Xin Li. Design extractors, non-malleable condensers and privacy amplification. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 837-854, 2012. Google Scholar
  26. Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, 2016. Google Scholar
  27. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. Journal of the ACM, pages 607-620, 1993. Google Scholar
  28. Raghu Meka. Explicit resilient functions matching Ajtai-Linial. CoRR, abs/1509.00092, 2015. URL: http://arxiv.org/abs/1509.00092.
  29. Elchanan Mossel, Amir Shpilka, and Luca Trevisan. On ε-biased generators in nc0. Random Structures &Algorithms, 29(1):56-81, 2006. Google Scholar
  30. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12:449-461, 1992. Google Scholar
  31. Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of Computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  32. Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996. Google Scholar
  33. Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. Google Scholar
  34. Periklis A Papakonstantinou, David P Woodruff, and Guang Yang. True randomness from big data. Scientific reports, 6, 2016. Google Scholar
  35. R. Raz, O. Reingold, and S. Vadhan. Error reduction for extractors. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 191-201, 1999. Google Scholar
  36. Luca Trevisan. Extractors and pseudorandom generators. Journal of the ACM, pages 860-879, 2001. Google Scholar
  37. S. Vadhan. On constructing locally computable extractors and cryptosystems in the bounded storage model. In Advances in Cryptology - CRYPTO '03, 23rd Annual International Cryptology Conference, Proceedings, 2003. Google Scholar
  38. Emanuele Viola. The complexity of constructing pseudorandom generators from hard functions. computational complexity, 13(3-4):147-188, 2005. Google Scholar
  39. Emanuele Viola. On constructing parallel pseudorandom generators from one-way functions. In Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on, pages 183-197. IEEE, 2005. Google Scholar
  40. D. Zuckerman. Randomness-optimal oblivious sampling. Random Structures and Algorithms, 11:345-367, 1997. 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 About DROPS Imprint Privacy Contact