Document Open Access Logo

New Extractors for Interleaved Sources

Authors Eshan Chattopadhyay, David Zuckerman

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.7.pdf
  • Filesize: 0.63 MB
  • 28 pages

Document Identifiers

Author Details

Eshan Chattopadhyay
David Zuckerman

Cite AsGet BibTex

Eshan Chattopadhyay and David Zuckerman. New Extractors for Interleaved Sources. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 7:1-7:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.CCC.2016.7

Abstract

We study how to extract randomness from a C-interleaved source, that is, a source comprised of C independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields: (1) For some delta>0, c>0, explicit extractors for 2-interleaved sources on {0,1}^{2n} when one source has min-entropy at least (1-delta)*n and the other has min-entropy at least c*log(n). The best previous construction, by Raz and Yehudayoff, worked only when both sources had entropy rate 1-delta. (2) For some c>0 and any large enough prime p, explicit extractors for 2-interleaved sources on [p]^{2n} when one source has min-entropy rate at least .51 and the other source has min-entropy rate at least (c*log(n))/n. We use these to obtain the following applications: (a) We introduce the class of any-order-small-space sources, generalizing the class of small-space sources studied by Kamp et al.. We construct extractors for such sources with min-entropy rate close to 1/2. Using the Raz-Yehudayoff construction would require entropy rate close to 1. (b) For any large enough prime p, we exhibit an explicit function f:[p]^{2n} -> {0,1} such that the randomized best-partition communication complexity of f with error 1/2-2^{-Omega(n)} is at least .24*n*log(p). Previously this was known only for a tiny constant instead of .24, for p=2 by by Raz and Yehudayoff. We introduce non-malleable extractors in the interleaved model. For any large enough prime p, we give an explicit construction of a weak-seeded non-malleable extractor for sources over [p]^n with min-entropy rate .51. Nothing was known previously, even for almost full min-entropy.
Keywords
  • extractor
  • derandomization
  • explicit construction

Metrics

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

References

  1. Noga Alon and Wolfgang Maass. Meanders, Ramsey Theory and Lower Bounds for Branching Programs. In IEEE Symposium on Foundations of Computer Science, pages 410-417, 1986. URL: http://dx.doi.org/10.1109/SFCS.1986.31.
  2. Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, and Emmanuel Thomé. A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, pages 1-16, 2014. URL: http://dx.doi.org/10.1007/978-3-642-55220-5_1.
  3. Manuel Blum. Independent unbiased coin flips from a correlated biased source finite state markov chain. Combinatorica, 6(2):97-108, 1986. Google Scholar
  4. J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 01(01):1-32, 2005. URL: http://dx.doi.org/10.1142/S1793042105000108.
  5. J. Bourgain, A. A. Glibichuk, and S. V. Konyagin. Estimates for the number of sums and products and for exponential sums in fields of prime order. Journal of the London Mathematical Society, 73:380-398, 4 2006. URL: http://dx.doi.org/10.1112/S0024610706022721.
  6. Jean Bourgain, Nets Katz, and Terence Tao. A sum-product estimate in finite fields, and applications. Geometric and Functional Analysis GAFA, 14(1):27-57, 2004. URL: http://dx.doi.org/10.1007/s00039-004-0451-1.
  7. Eshan Chattopadhyay, Vipul Goyal, and Xin Li. Non-malleable extractors and codes, with their many tampered extensions. In STOC, 2016. Google Scholar
  8. Eshan Chattopadhyay and David Zuckerman. Eshan chattopadhyay and xin li. In STOC, 2016. Google Scholar
  9. Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In STOC, 2016. Google Scholar
  10. Benny Chor and Oded Goldreich. Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. Siam Journal on Computing, 17:230-261, 1988. URL: http://dx.doi.org/10.1137/0217015.
  11. Benny Chor, Oded Goldreich, Johan Hasted, Joel Freidmann, Steven Rudich, and Roman Smolensky. The bit extraction problem or t-resilient functions. In IEEE Symposium on Foundations of Computer Science, pages 396-407, 1985. URL: http://dx.doi.org/10.1109/SFCS.1985.55.
  12. Gil Cohen, Ran Raz, and Gil Segev. Non-malleable extractors with short seeds and applications to privacy amplification. In IEEE Conference on Computational Complexity, pages 298-308, 2012. URL: http://dx.doi.org/10.1109/CCC.2012.21.
  13. Yevgeniy Dodis, Xin Li, Trevor D Wooley, and David Zuckerman. Privacy amplification and nonmalleable extractors via character sums. SIAM Journal on Computing, 43(2):800-830, 2014. Google Scholar
  14. Yevgeniy Dodis and Daniel Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. In STOC, pages 601-610, 2009. URL: http://dx.doi.org/10.1145/1536414.1536496.
  15. Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan. Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. In FOCS, pages 181-190, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.40.
  16. Zeev Dvir and Shachar Lovett. Subspace evasive sets. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 351-358. ACM, 2012. Google Scholar
  17. Venkatesan Guruswami. List decoding from erasures: bounds and code constructions. IEEE Transactions on Information Theory, 49(11):2826-2833, 2003. URL: http://dx.doi.org/10.1109/TIT.2003.815776.
  18. Venkatesan Guruswami. List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition), volume 3282 of Lecture Notes in Computer Science. Springer, 2004. URL: http://dx.doi.org/10.1007/b104335.
  19. Venkatesan Guruswami. Linear-algebraic list decoding of folded Reed-Solomon codes. In Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on, pages 77-85. IEEE, 2011. Google Scholar
  20. Venkatesan Guruswami and Piotr Indyk. Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC'02, pages 812-821, New York, NY, USA, 2002. ACM. URL: http://dx.doi.org/10.1145/509907.510023.
  21. Venkatesan Guruswami, Christopher Umans, and Salil P. Vadhan. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM, 56(4), 2009. URL: http://dx.doi.org/10.1145/1538902.1538904.
  22. Jesse Kamp, Anup Rao, Salil P. Vadhan, and David Zuckerman. Deterministic extractors for small-space sources. Journal of Computer and System Sciences, 77:191-220, 2011. URL: http://dx.doi.org/10.1016/j.jcss.2010.06.014.
  23. Jesse Kamp and David Zuckerman. Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. Siam Journal on Computing, 36:1231-1247, 2007. URL: http://dx.doi.org/10.1137/S0097539705446846.
  24. A.A. Karatsuba. On a certain arithmetic sum. Soviet Math Dokl., 12, 1172-1174, 1971. URL: https://www.researchgate.net/publication/258358497_On_a_certain_arithmetic_sum.
  25. AA Karatsuba. The distribution of values of dirichlet characters on additive sequences. In Doklady Acad. Sci. USSR, volume 319, pages 543-545, 1991. Google Scholar
  26. Sergei Konyagin. A sum-product estimate in fields of prime order. CoRR, arXiv:math/0304217, 2003. URL: http://arxiv.org/abs/math/0304217v1.
  27. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  28. Thomas Lengauer. Handbook of Theoretical Computer Science (Vol. A). MIT Press, Cambridge, MA, USA, 1990. URL: http://dl.acm.org/citation.cfm?id=114872.114888.
  29. Xin Li. Non-malleable extractors, two-source extractors and privacy amplification. In FOCS, pages 688-697, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.26.
  30. Xin Li. Improved constructions of two-source extractors. Electronic Colloquium on Computational Complexity (ECCC), 2015. URL: http://eccc.hpi-web.de/report/2015/125.
  31. Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, and Avi Wigderson. Extractors: optimal up to constant factors. In STOC, pages 602-611, 2003. URL: http://dx.doi.org/10.1145/780542.780630.
  32. Ueli M. Maurer and Stefan Wolf. Privacy amplification secure against active adversaries. In CRYPTO, pages 307-321, 1997. URL: http://dx.doi.org/10.1007/BFb0052244.
  33. Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996. Google Scholar
  34. Anup Rao. An exposition of Bourgain’s 2-source extractor. Electronic Colloquium on Computational Complexity (ECCC), 14(034), 2007. Google Scholar
  35. Ran Raz. Extractors with weak random seeds. In ACM Symposium on Theory of Computing, pages 11-20, 2005. URL: http://dx.doi.org/10.1145/1060590.1060593.
  36. Ran Raz and Amir Yehudayoff. Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. Journal of Computer and System Sciences, 77:167-190, 2011. URL: http://dx.doi.org/10.1016/j.jcss.2010.06.013.
  37. Miklos Santha and Umesh V. Vazirani. Generating quasi-random sequences from semi-random sources. Journal of Computer and System Sciences, 33:75-87, 1986. URL: http://dx.doi.org/10.1016/0022-0000(86)90044-9.
  38. Ronen Shaltiel. How to get more mileage from randomness extractors. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 46-60, 2006. URL: http://dx.doi.org/10.1109/CCC.2006.24.
  39. Victor Shoup. Searching for primitive roots in finite fields. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 546-554, 1990. URL: http://dx.doi.org/10.1145/100216.100293.
  40. Luca Trevisan and Salil P. Vadhan. Extracting Randomness from Samplable Distributions. In IEEE Symposium on Foundations of Computer Science, pages 32-42, 2000. URL: http://dx.doi.org/10.1109/SFCS.2000.892063.
  41. J. von Neumann. Various techniques used in connection with random digits. Applied Math Series, 12:36-38, 1951. Notes by G.E. Forsythe, National Bureau of Standards. Reprinted in Von Neumann’s Collected Works, 5:768-770, 1963. Google Scholar
  42. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing. In ACM Symposium on Theory of Computing, pages 209-213, 1979. URL: http://dx.doi.org/10.1145/800135.804414.
  43. David Zuckerman. Randomness-optimal oblivious sampling. Random Struct. Algorithms, 11(4):345-367, 1997. URL: http://dx.doi.org/10.1002/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z.
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