Document Open Access Logo

Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions (Extended Abstract)

Authors Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

PDF
Thumbnail PDF

File

LIPIcs.CCC.2015.582.pdf
  • Filesize: 0.55 MB
  • 19 pages

Document Identifiers

Author Details

Benny Applebaum
Sergei Artemenko
Ronen Shaltiel
Guang Yang

Cite As Get BibTex

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, and Guang Yang. Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions (Extended Abstract). In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 582-600, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CCC.2015.582

Abstract

A circuit C compresses a function f:{0,1}^n -> {0,1}^m if given an input x in {0,1}^n the circuit C can shrink x to a shorter l-bit string x' such that later, a computationally-unbounded solver D will be able to compute f(x) based on x'. In this paper we study the existence of functions which are incompressible by circuits of some fixed polynomial size s=n^c. Motivated by cryptographic applications, we focus on average-case (l,epsilon) incompressibility, which guarantees that on a random input x in {0,1}^n, for every size s circuit C:{0,1}^n -> {0,1}^l and any unbounded solver D, the success probability Pr_x[D(C(x))=f(x)] is upper-bounded by 2^(-m)+epsilon. While this notion of incompressibility appeared in several works  (e.g., Dubrov and Ishai, STOC 06), so far no explicit constructions of efficiently computable incompressible functions were known. In this work we present the following results:

1. Assuming that E is hard for exponential size nondeterministic circuits, we construct a polynomial time computable boolean function f:{0,1}^n -> {0,1} which is incompressible by size n^c circuits with communication l=(1-o(1)) * n and error epsilon=n^(-c). Our technique generalizes to the case of PRGs against nonboolean circuits, improving and simplifying the previous construction of Shaltiel and Artemenko (STOC 14).


2. We show that it is possible to achieve negligible error parameter epsilon=n^(-omega(1)) for nonboolean functions. Specifically, assuming that E is hard for exponential size Sigma_3-circuits, we construct a nonboolean function f:{0,1}^n -> {0,1}^m which is incompressible by size n^c circuits with l=Omega(n) and extremely small epsilon=n^(-c) * 2^(-m). Our construction combines the techniques of Trevisan and Vadhan (FOCS 00) with a new notion of relative error deterministic extractor which may be of independent interest.

3. We show that the task of constructing an incompressible boolean function f:{0,1}^n -> {0,1} with negligible error parameter epsilon cannot be achieved by "existing proof techniques". Namely, nondeterministic reductions (or even Sigma_i reductions) cannot get epsilon=n^(-omega(1)) for boolean incompressible functions. Our results also apply to constructions of standard Nisan-Wigderson type PRGs and (standard) boolean functions that are hard on average, explaining, in retrospective, the limitations of existing constructions. Our impossibility result builds on an approach of Shaltiel and Viola (SIAM J. Comp., 2010).

Subject Classification

Keywords
  • compression
  • pseudorandomness
  • extractors
  • nondeterministic reductions

Metrics

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

References

  1. Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, and Guang Yang. Incompressible functions, relative-error extractors, and the power of nondeterminsitic reductions. Electronic Colloquium on Computational Complexity (ECCC), 15(51), 2015. Google Scholar
  2. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. From secrecy to soundness: Efficient verification via secure computation. In ICALP, pages 152-163, 2010. Google Scholar
  3. Benny Applebaum, Yuval Ishai, Eyal Kushilevitz, and Brent Waters. Encoding functions with constant online rate or how to compress garbled circuits keys. In CRYPTO, pages 166-184, 2013. Google Scholar
  4. S. Artemenko and R. Shaltiel. Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification. Computational Complexity, 23(1):43-83, 2014. Google Scholar
  5. Sergei Artemenko and Ronen Shaltiel. Pseudorandom generators with optimal seed length for non-boolean poly-size circuits. In Symposium on Theory of Computing, STOC, pages 99-108, 2014. Google Scholar
  6. L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. Bpp has subexponential time simulations unless exptime has publishable proofs. Computational Complexity, 3:307-318, 1993. Google Scholar
  7. László Babai and Shlomo Moran. Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci., 36(2):254-276, 1988. Google Scholar
  8. B. Barak, S. J. Ong, and S. P. Vadhan. Derandomization in cryptography. SIAM J. Comput., 37(2):380-400, 2007. Google Scholar
  9. Kai-Min Chung, Yael Kalai, and Salil Vadhan. Improved delegation of computation using fully homomorphic encryption. In CRYPTO, pages 483-501, 2010. Google Scholar
  10. Francesco Davì, Stefan Dziembowski, and Daniele Venturi. Leakage-resilient storage. In Security and Cryptography for Networks, 7th International Conference, SCN 2010, pages 121-137, 2010. Google Scholar
  11. Andrew Drucker. Nondeterministic direct product reductions and the success probability of SAT solvers. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 736-745, 2013. Google Scholar
  12. B. Dubrov and Y. Ishai. On the randomness complexity of efficient sampling. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 711-720, 2006. Google Scholar
  13. Uriel Feige and Carsten Lund. On the hardness of computing the permanent of random matrices. Computational Complexity, 6(2):101-132, 1997. Google Scholar
  14. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. Google Scholar
  15. Rosario Gennaro, Craig Gentry, and Bryan Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In CRYPTO, pages 465-482, 2010. Google Scholar
  16. O. Goldreich and A. Wigderson. Derandomization that is rarely wrong from short advice that is typically good. In APPROX-RANDOM, pages 209-223, 2002. Google Scholar
  17. Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 25-32, 1989. Google Scholar
  18. Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J. ACM, 38(3):691-729, 1991. Google Scholar
  19. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 59-68, 1986. Google Scholar
  20. D. Gutfreund and G. Rothblum. The complexity of local list decoding. In 12th Intl. Workshop on Randomization and Computation (RANDOM), 2008. Google Scholar
  21. D. Gutfreund, R. Shaltiel, and A. Ta-Shma. If np languages are hard on the worst-case, then it is easy to find their hard instances. Computational Complexity, 16(4):412-441, 2007. Google Scholar
  22. D. Gutfreund and A. Ta-Shma. Worst-case to average-case reductions revisited. In APPROX-RANDOM, pages 569-583, 2007. Google Scholar
  23. Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma. Uniform hardness versus randomness tradeoffs for arthur-merlin games. Computational Complexity, 12(3-4):85-130, 2003. Google Scholar
  24. Danny Harnik and Moni Naor. On the compressibility of NP instances and cryptographic applications. SIAM J. Comput., 39(5):1667-1713, 2010. Google Scholar
  25. R. Impagliazzo and A. Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In STOC, pages 220-229, 1997. Google Scholar
  26. R. Impagliazzo and A. Wigderson. Randomness vs. time: De-randomization under a uniform assumption. In 39th Annual Symposium on Foundations of Computer Science. IEEE, 1998. Google Scholar
  27. M. Jerrum, L. G. Valiant, and V. V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci., 43:169-188, 1986. Google Scholar
  28. Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. How to delegate computations: the power of no-signaling proofs. In STOC, 2014. Google Scholar
  29. A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31(5):1501-1526, 2002. Google Scholar
  30. R. Lipton. New directions in testing. In Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, volume 2, pages 191-202. ACM/AMS, 1991. Google Scholar
  31. C.-J. Lu, S.-C. Tsai, and H.-L. Wu. On the complexity of hardness amplification. IEEE Transactions on Information Theory, 54(10):4575-4586, 2008. Google Scholar
  32. Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu. Impossibility results on weakly black-box hardness amplification. In FCT, pages 400-411, 2007. Google Scholar
  33. P. Bro Miltersen and N. V. Vinodchandran. Derandomizing arthur-merlin games using hitting sets. Computational Complexity, 14(3):256-279, 2005. Google Scholar
  34. N. Nisan and A. Wigderson. Hardness vs. randomness. JCSS: Journal of Computer and System Sciences, 49, 1994. Google Scholar
  35. R. Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the EATCS, 77:67-95, 2002. Google Scholar
  36. R. Shaltiel. An introduction to randomness extractors. In Automata, Languages and Programming - 38th International Colloquium, pages 21-41, 2011. Google Scholar
  37. R. Shaltiel and C. Umans. Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM, 52(2):172-216, 2005. Google Scholar
  38. R. Shaltiel and C. Umans. Pseudorandomness for approximate counting and sampling. Computational Complexity, 15(4):298-341, 2006. Google Scholar
  39. R. Shaltiel and C. Umans. Low-end uniform hardness versus randomness tradeoffs for am. SIAM J. Comput., 39(3):1006-1037, 2009. Google Scholar
  40. R. Shaltiel and E. Viola. Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122-3154, 2010. Google Scholar
  41. Ronen Shaltiel. Weak derandomization of weak algorithms: Explicit versions of yao’s lemma. Computational Complexity, 20(1):87-143, 2011. Google Scholar
  42. M. Sipser. A complexity theoretic approach to randomness. In STOC, pages 330-335, 1983. Google Scholar
  43. L. J. Stockmeyer. The complexity of approximate counting. In STOC, pages 118-126, 1983. Google Scholar
  44. M. Sudan, L. Trevisan, and S. P. Vadhan. Pseudorandom generators without the xor lemma. J. Comput. Syst. Sci., 62(2):236-266, 2001. Google Scholar
  45. A. Ta-Shma and D. Zuckerman. Extractor codes. In STOC, 2001. Google Scholar
  46. L. Trevisan and S. Vadhan. Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity, 16(4):331-364, 2007. Google Scholar
  47. L. Trevisan and S. P. Vadhan. Extracting randomness from samplable distributions. In 41st Annual Symposium on Foundations of Computer Science, pages 32-42, 2000. Google Scholar
  48. E. Viola. The complexity of constructing pseudorandom generators from hard functions. Computational Complexity, 13(3-4):147-188, 2005. 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