Document Open Access Logo

Non-Malleable Extractors - New Tools and Improved Constructions

Author Gil Cohen

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.8.pdf
  • Filesize: 0.58 MB
  • 29 pages

Document Identifiers

Author Details

Gil Cohen

Cite As Get BibTex

Gil Cohen. Non-Malleable Extractors - New Tools and Improved Constructions. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 8:1-8:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CCC.2016.8

Abstract

A non-malleable extractor is a seeded extractor with a very strong guarantee - the output of a non-malleable extractor obtained using a typical seed is close to uniform even conditioned on the output obtained using any other seed. The first contribution of this paper consists of two new and improved constructions of non-malleable extractors:

- We construct a non-malleable extractor with seed-length O(log(n) * log(log(n))) that works for entropy Omega(log(n)). This improves upon a recent exciting construction by Chattopadhyay, Goyal, and Li (STOC'16) that has seed length O(log^{2}(n)) and requires entropy Omega(log^{2}(n)).

- Secondly, we construct a non-malleable extractor with optimal seed length O(log(n)) for entropy n/log^{O(1)}(n). Prior to this construction, non-malleable extractors with a logarithmic seed length, due to Li (FOCS'12), required entropy 0.49*n. Even non-malleable condensers with seed length O(log(n)), by Li (STOC'12), could only support linear entropy.


We further devise several tools for enhancing a given non-malleable extractor in a black-box manner. One such tool is an algorithm that reduces the entropy requirement of a non-malleable extractor at the expense of a slightly longer seed. A second algorithm increases the output length of a non-malleable extractor from constant to linear in the entropy of the source. We also devise an algorithm that transforms a non-malleable extractor to the so-called t-non-malleable extractor for any desired t. Besides being useful building blocks for our constructions, we consider these modular tools to be of independent interest.

Subject Classification

Keywords
  • extractors
  • non-malleable
  • explicit constructions

Metrics

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

References

  1. D. Aggarwal, K. Hosseini, and S. Lovett. Affine-malleable extractors, spectrum doubling, and application to privacy amplification. In Electronic Colloquium on Computational Complexity (ECCC), page 179, 2015. Google Scholar
  2. B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson. Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. In Proceedings of the thirty-seventh annual ACM Symposium on Theory of Computing, pages 1-10. ACM, 2005. Google Scholar
  3. B. Barak, A. Rao, R. Shaltiel, and A. Wigderson. 2-source dispersers for n^o(1) entropy, and Ramsey graphs beating the Frankl-Wilson construction. Annals of Mathematics, 176(3):1483-1544, 2012. Google Scholar
  4. E. Chattopadhyay, V. Goyal, and X. Li. Non-malleable extractors and codes, with their many tampered extensions. arXiv preprint arXiv:1505.00107, 2015. Google Scholar
  5. E. Chattopadhyay and D. Zuckerman. Explicit two-source extractors and resilient functions. Electronic Colloquium on Computational Complexity (ECCC), 2015. Google Scholar
  6. B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230-261, 1988. Google Scholar
  7. G. Cohen. Local correlation breakers and applications to three-source extractors and mergers. In Electronic Colloquium on Computational Complexity (ECCC), page 38, 2015. Google Scholar
  8. G. Cohen. Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs. arXiv preprint arXiv:1506.04428, 2015. Google Scholar
  9. G. Cohen, R. Raz, and G. Segev. Nonmalleable extractors with short seeds and applications to privacy amplification. SIAM Journal on Computing, 43(2):450-476, 2014. Google Scholar
  10. Y. Dodis, X. Li, T. D. Wooley, and D. Zuckerman. Privacy amplification and nonmalleable extractors via character sums. SIAM Journal on Computing, 43(2):800-830, 2014. Google Scholar
  11. Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing, 38(1):97-139, 2008. Google Scholar
  12. Y. Dodis and D. Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. In Proceedings of the forty-first annual ACM Symposium on Theory of Computing, pages 601-610. ACM, 2009. Google Scholar
  13. Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan. Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. In 50th Annual IEEE Symposium on Foundations of Computer Science, pages 181-190. IEEE, 2009. Google Scholar
  14. S. Dziembowski and K. Pietrzak. Intrusion-resilient secret sharing. In 48th Annual IEEE Symposium on Foundations of Computer Science, pages 227-237, 2007. Google Scholar
  15. V. Guruswami, C. Umans, and S. Vadhan. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM, 56(4):20, 2009. Google Scholar
  16. X. Li. Improved constructions of three source extractors. In IEEE 26th Annual Conference on Computational Complexity, pages 126-136, 2011. Google Scholar
  17. X. Li. Design extractors, non-malleable condensers and privacy amplification. In Proceedings of the forty-fourth annual ACM Symposium on Theory of Computing, pages 837-854, 2012. Google Scholar
  18. X. Li. Non-malleable condensers for arbitrary min-entropy, and almost optimal protocols for privacy amplification. arXiv preprint arXiv:1211.0651, 2012. Google Scholar
  19. X. Li. Non-malleable extractors, two-source extractors and privacy amplification. In IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 688-697, 2012. Google Scholar
  20. X. Li. Extractors for a constant number of independent sources with polylogarithmic min-entropy. In IEEE 54th Annual Symposium on Foundations of Computer Science, pages 100-109, 2013. Google Scholar
  21. X. Li. New independent source extractors with exponential improvement. In Proceedings of the forty-fifth annual ACM Symposium on Theory of Computing, pages 783-792. ACM, 2013. Google Scholar
  22. X. Li. Extractors for affine sources with polylogarithmic entropy. In Electronic Colloquium on Computational Complexity (ECCC), page 121, 2015. Google Scholar
  23. X. Li. Improved constructions of two-source extractors. In Electronic Colloquium on Computational Complexity (ECCC), page 125, 2015. Google Scholar
  24. X. Li. Three-source extractors for polylogarithmic min-entropy. Electronic Colloquium on Computational Complexity (ECCC), 2015. Google Scholar
  25. X. Li, T. D. Wooley, and D. Zuckerman. Privacy amplification and nonmalleable extractors via character sums. arXiv preprint arXiv:1102.5415, 2011. Google Scholar
  26. N. Nisan and D. Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996. Google Scholar
  27. A. Rao. Extractors for a constant number of polynomially small min-entropy independent sources. SIAM Journal on Computing, 39(1):168-194, 2009. Google Scholar
  28. R. Raz. Extractors with weak random seeds. In Proceedings of the thirty-seventh annual ACM Symposium on Theory of Computing, pages 11-20, 2005. Google Scholar
  29. O. Reingold, R. Shaltiel, and A. Wigderson. Extracting randomness via repeated condensing. In Proceedings. 41st Annual Symposium on Foundations of Computer Science, 2000, pages 22-31. IEEE, 2000. Google Scholar
  30. R. Shaltiel. An introduction to randomness extractors. In Automata, languages and programming, pages 21-41. Springer, 2011. Google Scholar
  31. A. Ta-Shma and C. Umans. Better condensers and new extractors from Parvaresh-Vardy codes. In IEEE 27th Annual Conference onComputational Complexity (CCC), pages 309-315. IEEE, 2012. Google Scholar
  32. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 2011. Google Scholar
  33. D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3:103-128, 2007. 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