Document Open Access Logo

Is It Possible to Improve Yao’s XOR Lemma Using Reductions That Exploit the Efficiency of Their Oracle?

Author Ronen Shaltiel

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.10.pdf
  • Filesize: 0.64 MB
  • 20 pages

Document Identifiers

Author Details

Ronen Shaltiel
  • University of Haifa, Israel

Funding

  • Shaltiel, Ronen: This research was supported by ISF grant 1628/17.

Acknowledgements

We are grateful to Emanuele Viola for very helpful discussions, and to anonymous referees for comments and suggestions.

Cite As Get BibTex

Ronen Shaltiel. Is It Possible to Improve Yao’s XOR Lemma Using Reductions That Exploit the Efficiency of Their Oracle?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.10

Abstract

Yao’s XOR lemma states that for every function f:{0,1}^k → {0,1}, if f has hardness 2/3 for P/poly (meaning that for every circuit C in P/poly, Pr[C(X) = f(X)] ≤ 2/3 on a uniform input X), then the task of computing f(X₁) ⊕ … ⊕ f(X_t) for sufficiently large t has hardness 1/2 +ε for P/poly.
Known proofs of this lemma cannot achieve ε = 1/k^ω(1), and even for ε = 1/k, we do not know how to replace P/poly by AC⁰[parity] (the class of constant depth circuits with the gates {and,or,not,parity} of unbounded fan-in).
Recently, Grinberg, Shaltiel and Viola (FOCS 2018) (building on a sequence of earlier works) showed that these limitations cannot be circumvented by black-box reductions. Namely, by reductions Red^(⋅) that given oracle access to a function D that violates the conclusion of Yao’s XOR lemma, implement a circuit that violates the assumption of Yao’s XOR lemma.
There are a few known reductions in the related literature on worst-case to average case reductions that are non-black box. Specifically, the reductions of Gutfreund, Shaltiel and Ta Shma (Computational Complexity 2007) and Hirahara (FOCS 2018)) are "class reductions" that are only guaranteed to succeed when given oracle access to an oracle D from some efficient class of algorithms. These works seem to circumvent some black-box impossibility results.
In this paper we extend the previous limitations of Grinberg, Shaltiel and Viola to class reductions, giving evidence that class reductions cannot yield the desired improvements in Yao’s XOR lemma. To the best of our knowledge, this is the first limitation on reductions for hardness amplification that applies to class reductions.
Our technique imitates the previous lower bounds for black-box reductions, replacing the inefficient oracle used in that proof, with an efficient one that is based on limited independence, and developing tools to deal with the technical difficulties that arise following this replacement.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • Yao’s XOR lemma
  • Hardness amplification
  • black-box reductions

Metrics

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

References

  1. Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On basing one-way functions on np-hardness. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 701-710, 2006. URL: https://doi.org/10.1145/1132516.1132614.
  2. Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, and Guang Yang. Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. Computational Complexity, 25(2):349-418, 2016. URL: https://doi.org/10.1007/s00037-016-0128-9.
  3. Sergei Artemenko and Ronen Shaltiel. Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification. Computational Complexity, 23(1):43-83, 2014. URL: https://doi.org/10.1007/s00037-012-0056-2.
  4. Albert Atserias. Distinguishing SAT from polynomial-size circuits, through black-box queries. In 21st Annual IEEE Conference on Computational Complexity, pages 88-95, 2006. URL: https://doi.org/10.1109/CCC.2006.17.
  5. Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. SIAM J. Comput., 36(4):1119-1159, 2006. URL: https://doi.org/10.1137/S0097539705446974.
  6. Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola. On beating the hybrid argument. Theory of Computing, 9:809-843, 2013. Google Scholar
  7. Joan Feigenbaum and Lance Fortnow. Random-self-reducibility of complete sets. SIAM J. Comput., 22(5):994-1005, 1993. URL: https://doi.org/10.1137/0222061.
  8. Oded Goldreich and Hugo Krawczyk. On the composition of zero-knowledge proof systems. SIAM J. Comput., 25(1):169-192, 1996. URL: https://doi.org/10.1137/S0097539791220688.
  9. Oded Goldreich, Noam Nisan, and Avi Wigderson. On yao’s xor-lemma. In Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, volume 6650 of Lecture Notes in Computer Science, pages 273-301. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22670-0_23.
  10. Aryeh Grinberg, Ronen Shaltiel, and Emanuele Viola. Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. In 59th IEEE Annual Symposium on Foundations of Computer Science, pages 956-966, 2018. URL: https://doi.org/10.1109/FOCS.2018.00094.
  11. Dan Gutfreund. Worst-case vs. algorithmic average-case complexity in the polynomial-time hierarchy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX and 10th International Workshop on Randomization and Computation, RANDOM, volume 4110 of Lecture Notes in Computer Science, pages 386-397, 2006. URL: https://doi.org/10.1007/11830924_36.
  12. Dan Gutfreund and Guy N. Rothblum. The complexity of local list decoding. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX, and 12th International Workshop, RANDOM, volume 5171 of Lecture Notes in Computer Science, pages 455-468, 2008. URL: https://doi.org/10.1007/978-3-540-85363-3_36.
  13. Dan Gutfreund, Ronen Shaltiel, and Amnon 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. URL: https://doi.org/10.1007/s00037-007-0235-8.
  14. Dan Gutfreund and Amnon Ta-Shma. Worst-case to average-case reductions revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX, and 11th International Workshop, RANDOM, volume 4627 of Lecture Notes in Computer Science, pages 569-583, 2007. URL: https://doi.org/10.1007/978-3-540-74208-1_41.
  15. Dan Gutfreund and Salil P. Vadhan. Limitations of hardness vs. randomness under uniform reductions. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX, and 12th International Workshop, RANDOM, volume 5171 of Lecture Notes in Computer Science, pages 469-482, 2008. URL: https://doi.org/10.1007/978-3-540-85363-3_37.
  16. Dan Gutfreund and Emanuele Viola. Fooling parity tests with parity gates. In Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, and 8th International Workshop on Randomization and Computation, RANDOM, volume 3122 of Lecture Notes in Computer Science, pages 381-392, 2004. URL: https://doi.org/10.1007/978-3-540-27821-4_34.
  17. Shuichi Hirahara. Non-black-box worst-case to average-case reductions within NP. In 59th IEEE Annual Symposium on Foundations of Computer Science, pages 247-258, 2018. URL: https://doi.org/10.1109/FOCS.2018.00032.
  18. Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In 36th Annual Symposium on Foundations of Computer Science, pages 538-545, 1995. URL: https://doi.org/10.1109/SFCS.1995.492584.
  19. Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 44-61, 1989. URL: https://doi.org/10.1145/73007.73012.
  20. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, pages 220-229, 1997. URL: https://doi.org/10.1145/258533.258590.
  21. Adam R. Klivans and Rocco A. Servedio. Boosting and hard-core set construction. Machine Learning, 51(3):217-238, 2003. URL: https://doi.org/10.1023/A:1022949332276.
  22. Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. A fixed-depth size-hierarchy theorem for ac^0[⊕] via the coin problem. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing, pages 442-453, 2019. URL: https://doi.org/10.1145/3313276.3316339.
  23. Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu. On the complexity of hardness amplification. IEEE Trans. Information Theory, 54(10):4575-4586, 2008. URL: https://doi.org/10.1109/TIT.2008.928988.
  24. Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan. Parity helps to compute majority. In 34th Computational Complexity Conference, volume 137, pages 23:1-23:17, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.23.
  25. Alexander Razborov. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Akademiya Nauk SSSR. Matematicheskie Zametki, 41(4):598-607, 1987. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987. Google Scholar
  26. Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Notions of reducibility between cryptographic primitives. In Theory of Cryptography, First Theory of Cryptography Conference, TCC, volume 2951 of Lecture Notes in Computer Science, pages 1-20, 2004. URL: https://doi.org/10.1007/978-3-540-24638-1_1.
  27. Ronen Shaltiel and Emanuele Viola. Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122-3154, 2010. URL: https://doi.org/10.1137/080735096.
  28. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 77-82, 1987. URL: https://doi.org/10.1145/28395.28404.
  29. Madhu Sudan, Luca Trevisan, and Salil P. Vadhan. Pseudorandom generators without the XOR lemma. J. Comput. Syst. Sci., 62(2):236-266, 2001. URL: https://doi.org/10.1006/jcss.2000.1730.
  30. Luca Trevisan and Salil P. Vadhan. Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity, 16(4):331-364, 2007. URL: https://doi.org/10.1007/s00037-007-0233-x.
  31. Emanuele Viola. Hardness vs. randomness within alternating time. In 18th Annual IEEE Conference on Computational Complexity, page 53, 2003. URL: https://doi.org/10.1109/CCC.2003.1214410.
  32. Emanuele Viola. The Complexity of Hardness Amplification and Derandomization. PhD thesis, Harvard University, 2006. 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