Document Open Access Logo

Black-Box Hypotheses and Lower Bounds

Authors Brynmor K. Chapman, R. Ryan Williams

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.29.pdf
  • Filesize: 0.89 MB
  • 22 pages

Document Identifiers

Author Details

Brynmor K. Chapman
  • MIT, Cambridge, MA, USA
R. Ryan Williams
  • MIT, Cambridge, MA, USA

Funding

Partially supported by NSF CCF-1741615, NSF CCF-1909429, and a Frank Quick Faculty Innovation Fellowship.

Cite AsGet BibTex

Brynmor K. Chapman and R. Ryan Williams. Black-Box Hypotheses and Lower Bounds. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.29

Abstract

What sort of code is so difficult to analyze that every potential analyst can discern essentially no information from the code, other than its input-output behavior? In their seminal work on program obfuscation, Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang (CRYPTO 2001) proposed the Black-Box Hypothesis, which roughly states that every property of Boolean functions which has an efficient "analyst" and is "code independent" can also be computed by an analyst that only has black-box access to the code. In their formulation of the Black-Box Hypothesis, the "analysts" are arbitrary randomized polynomial-time algorithms, and the "codes" are general (polynomial-size) circuits. If true, the Black-Box Hypothesis would immediately imply NP ̸ ⊂ BPP. We consider generalized forms of the Black-Box Hypothesis, where the set of "codes" 𝒞 and the set of "analysts" 𝒜 may correspond to other efficient models of computation, from more restricted models such as AC⁰ to more general models such as nondeterministic circuits. We show how lower bounds of the form 𝒞 ̸ ⊂ 𝒜 often imply a corresponding Black-Box Hypothesis for those respective codes and analysts. We investigate the possibility of "complete" problems for the Black-Box Hypothesis: problems in 𝒞 such that they are not in 𝒜 if and only if their corresponding Black-Box Hypothesis is true. Along the way, we prove an equivalence: for nondeterministic circuit classes 𝒞, the "𝒞-circuit satisfiability problem" is not in 𝒜 if and only if the Black-Box Hypothesis is true for analysts in 𝒜.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • Black-Box hypothesis
  • circuit complexity
  • lower bounds

Metrics

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

References

  1. Miklos Ajtai. Σ¹₁-formulae on finite structures. Annals of Pure and Applied Logic, 24:1-48, 1983. Google Scholar
  2. Shaull Almagor, Brynmor Chapman, Mehran Hosseini, Joël Ouaknine, and James Worrell. Effective divergence analysis for linear recurrence sequences. In Proceedings of the 29th International Conference on Concurrency Theory (CONCUR 2018), LIPIcs 118. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  3. Kazuyuki Amano. On the size of depth-two threshold circuits for the inner product mod 2 function. In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, and Claudio Zandron, editors, Language and Automata Theory and Applications, pages 235-247, Cham, 2020. Springer International Publishing. Google Scholar
  4. Sanjeev Arora and Boaz Barak. Computational complexity: A modern approach. Cambridge University Press, Cambridge, 2009. URL: https://doi.org/10.1017/CBO9780511804090.
  5. Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (im) possibility of obfuscating programs. In Annual international cryptology conference, pages 1-18. Springer, 2001. Google Scholar
  6. Nir Bitansky and Vinod Vaikuntanathan. Indistinguishability obfuscation from functional encryption. Journal of the ACM (JACM), 65(6):39, 2018. Google Scholar
  7. Dan Boneh and Mark Zhandry. Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. Algorithmica, 79(4):1233-1285, 2017. Google Scholar
  8. Bernd Borchert and Frank Stephan. Looking for an analogue of rice’s theorem in circuit complexity theory. In Kurt Gödel Colloquium on Computational Logic and Proof Theory, pages 114-127. Springer, 1997. Google Scholar
  9. Merrick Furst, James Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. See also FOCS'81. Google Scholar
  10. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM Journal on Computing, 45(3):882-929, 2016. Google Scholar
  11. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Hiding secrets in software: A cryptographic approach to program obfuscation. Communications of the ACM, 59(5):113-120, 2016. Google Scholar
  12. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM symposium on Theory of computing, pages 6-20. 1986. Google Scholar
  13. Lane A Hemaspaandra and Mayur Thakur. Lower bounds and the hardness of counting properties. Theoretical computer science, 326(1-3):1-28, 2004. Google Scholar
  14. Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, and Shadab Romani. Does looking inside a circuit help? In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  15. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-24508-4.
  16. Joël Ouaknine and James Worrell. Decision problems for linear recurrence sequences. In Proceedings of the 6th International Workshop on Reachability Problems (RP 2012), LNCS 7550. Springer, 2012. Google Scholar
  17. Joël Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. In Proceedings of 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), LNCS 8573. Springer, 2014. Google Scholar
  18. Alexander Razborov. Lower bounds on the size of bounded-depth networks over the complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  19. Henry Gordon Rice. Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society, 74(2):358-366, 1953. Google Scholar
  20. Shadab Romani. Succinct representations of Boolean functions and the Circuit-SAT problem. PhD thesis, Memorial University of Newfoundland, 2016. Google Scholar
  21. Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 475-484. ACM, 2014. Google Scholar
  22. Michael Sipser. Borel sets and circuit complexity. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 61-69, 1983. URL: https://doi.org/10.1145/800061.808733.
  23. Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In STOC, pages 77-82, 1987. 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