Bounded Indistinguishability for Simple Sources

Authors Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.26.pdf
  • Filesize: 0.72 MB
  • 18 pages

Document Identifiers

Author Details

Andrej Bogdanov
  • Department of Computer Science and Engineering and Institute of Theoretical Computer Science and Communications, The Chinese University of Hong Kong, Hong Kong
Krishnamoorthy Dinesh
  • Institute of Theoretical Computer Science and Communications, The Chinese University of Hong Kong, Hong Kong
Yuval Filmus
  • The Henry and Marylin Taub Faculty of Computer Science, Technion, Haifa, Israel
Yuval Ishai
  • The Henry and Marylin Taub Faculty of Computer Science, Technion, Haifa, Israel
Avi Kaplan
  • The Henry and Marylin Taub Faculty of Computer Science, Technion, Haifa, Israel
Akshayaram Srinivasan
  • School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India

Acknowledgements

We thank Chin Ho Lee, Igor Oliveira, Rahul Santhanam, Amir Shpilka, Justin Thaler, and Emanuele Viola for useful feedback. Special thanks go to Chin Ho Lee, who suggested [Andrej Bogdanov et al., 2021], and Justin Thaler, who suggested the construction in [Andrej Bogdanov et al., 2021].

Cite AsGet BibTex

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan. Bounded Indistinguishability for Simple Sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.26

Abstract

A pair of sources X, Y over {0,1}ⁿ are k-indistinguishable if their projections to any k coordinates are identically distributed. Can some AC^0 function distinguish between two such sources when k is big, say k = n^{0.1}? Braverman’s theorem (Commun. ACM 2011) implies a negative answer when X is uniform, whereas Bogdanov et al. (Crypto 2016) observe that this is not the case in general. We initiate a systematic study of this question for natural classes of low-complexity sources, including ones that arise in cryptographic applications, obtaining positive results, negative results, and barriers. In particular: - There exist Ω(√n)-indistinguishable X, Y, samplable by degree-O(log n) polynomial maps (over F₂) and by poly(n)-size decision trees, that are Ω(1)-distinguishable by OR. - There exists a function f such that all f(d, ε)-indistinguishable X, Y that are samplable by degree-d polynomial maps are ε-indistinguishable by OR for all sufficiently large n. Moreover, f(1, ε) = ⌈log(1/ε)⌉ + 1 and f(2, ε) = O(log^{10}(1/ε)). - Extending (weaker versions of) the above negative results to AC^0 distinguishers would require settling a conjecture of Servedio and Viola (ECCC 2012). Concretely, if every pair of n^{0.9}-indistinguishable X, Y that are samplable by linear maps is ε-indistinguishable by AC^0 circuits, then the binary inner product function can have at most an ε-correlation with AC^0 ◦ ⊕ circuits. Finally, we motivate the question and our results by presenting applications of positive results to low-complexity secret sharing and applications of negative results to leakage-resilient cryptography.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
  • Theory of computation → Circuit complexity
Keywords
  • Pseudorandomness
  • bounded indistinguishability
  • complexity of sampling
  • constant-depth circuits
  • secret sharing
  • leakage-resilient cryptography

Metrics

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

References

  1. Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595-605, 2004. URL: https://doi.org/10.1145/1008731.1008735.
  2. Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen. Candidate weak pseudorandom functions in AC⁰∘MOD₂. In Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 251-260, 2014. URL: https://doi.org/10.1145/2554797.2554821.
  3. Shyan Akmal and Ryan Williams. Majority-3sat (and related problems) in polynomial time, 2021. URL: http://arxiv.org/abs/2107.02748.
  4. Kazuyuki Amano, Kazuo Iwama, Akira Maruoka, Kenshi Matsuo, and Akihiro Matsuura. Inclusion-exclusion for k-cnf formulas. Inf. Process. Lett., 87(2):111-117, 2003. URL: https://doi.org/10.1016/S0020-0190(03)00259-X.
  5. A. Ambainis, L.J. Schulman, A. Ta-Shma, U. Vazirani, and A. Wigderson. The quantum communication complexity of sampling. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pages 342-351, 1998. URL: https://doi.org/10.1109/SFCS.1998.743480.
  6. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC⁰. SIAM J. Comput., 36(4):845-888, 2006. Google Scholar
  7. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778-797, 2001. URL: https://doi.org/10.1145/502090.502097.
  8. Chris Beck, Russell Impagliazzo, and Shachar Lovett. Large deviation bounds for decision trees and sampling lower bounds for ac0-circuits. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 101-110, 2012. URL: https://doi.org/10.1109/FOCS.2012.82.
  9. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 1-10, 1988. URL: https://doi.org/10.1145/62212.62213.
  10. Eli Ben-Sasson and Ariel Gabizon. Extractors for polynomial sources over fields of constant order and small characteristic. Theory Comput., 9:665-683, 2013. URL: https://doi.org/10.4086/toc.2013.v009a021.
  11. Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan. Bounded indistinguishability for simple sources. Electron. Colloquium Comput. Complex., 2021. URL: https://eccc.weizmann.ac.il/report/2021/093.
  12. Andrej Bogdanov, Yuval Ishai, and Akshayaram Srinivasan. Unconditionally secure computation against low-complexity leakage. In Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part II, volume 11693 of Lecture Notes in Computer Science, pages 387-416, 2019. URL: https://doi.org/10.1007/978-3-030-26951-7_14.
  13. Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson. Bounded indistinguishability and the complexity of recovering secrets. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part III, volume 9816 of Lecture Notes in Computer Science, pages 593-618, 2016. URL: https://doi.org/10.1007/978-3-662-53015-3_21.
  14. Andrej Bogdanov and Christopher Williamson. Approximate bounded indistinguishability. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pages 53:1-53:11, 2017. Google Scholar
  15. Mark Braverman. Poly-logarithmic independence fools bounded-depth boolean circuits. Commun. ACM, 54(4):108-115, 2011. URL: https://doi.org/10.1145/1924421.1924446.
  16. Mark Bun, Robin Kothari, and Justin Thaler. Quantum algorithms and approximating polynomials for composed functions with shared inputs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 662-678, 2019. URL: https://doi.org/10.1137/1.9781611975482.42.
  17. Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and markov-bernstein inequalities. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 303-314, 2013. URL: https://doi.org/10.1007/978-3-642-39206-1_26.
  18. Mark Bun and Justin Thaler. Dual polynomials for collision and element distinctness. Theory Comput., 12:Paper No. 16, 34, 2016. URL: https://doi.org/10.4086/toc.2016.v012a016.
  19. Mark Bun and Justin Thaler. Approximate degree and the complexity of depth three circuits. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, volume 116 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 35, 18. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018. Google Scholar
  20. Mark Bun and Justin Thaler. The large-error approximate degree of AC⁰. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, volume 145 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 55, 16. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019. Google Scholar
  21. Mark Bun and Justin Thaler. Guest column: Approximate degree in classical and quantum computing. SIGACT News, 51(4):48-72, 2020. URL: https://doi.org/10.1145/3444815.3444825.
  22. Mark Bun and Justin Thaler. A nearly optimal lower bound on the approximate degree of AC⁰. SIAM J. Comput., 49(4), 2020. URL: https://doi.org/10.1137/17M1161737.
  23. David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 11-19, 1988. URL: https://doi.org/10.1145/62212.62214.
  24. Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie. AC⁰∘MOD₂ lower bounds for the boolean inner product. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 35:1-35:14, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.35.
  25. Gil Cohen and Igor Shinkar. The complexity of DNF of parities. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 47-58, 2016. URL: https://doi.org/10.1145/2840728.2840734.
  26. Ivan Damgård, Yuval Ishai, and Mikkel Krøigaard. Perfectly secure multiparty computation and the computational overhead of cryptography. In Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 445-465, 2010. URL: https://doi.org/10.1007/978-3-642-13190-5_23.
  27. Ivan Damgård and Jesper Buus Nielsen. Scalable and unconditionally secure multiparty computation. In Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings, volume 4622 of Lecture Notes in Computer Science, pages 572-590, 2007. URL: https://doi.org/10.1007/978-3-540-74143-5_32.
  28. Anindya De and Thomas Watson. Extractors and lower bounds for locally samplable sources. ACM Trans. Comput. Theory, 4(1), March 2012. URL: https://doi.org/10.1145/2141938.2141941.
  29. Zeev Dvir, Ariel Gabizon, and Avi Wigderson. Extractors and rank extractors for polynomial sources. Comput. Complex., 18(1):1-58, 2009. URL: https://doi.org/10.1007/s00037-009-0258-4.
  30. Zeev Dvir, Dan Gutfreund, Guy N. Rothblum, and Salil P. Vadhan. On approximating the entropy of polynomial mappings. In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 460-475. Tsinghua University Press, 2011. URL: http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/28.html.
  31. Sebastian Faust, Tal Rabin, Leonid Reyzin, Eran Tromer, and Vinod Vaikuntanathan. Protecting circuits from computationally bounded and noisy leakage. SIAM J. Comput., 43(5):1564-1614, 2014. URL: https://doi.org/10.1137/120880343.
  32. Matthew K. Franklin and Moti Yung. Communication complexity of secure computation (extended abstract). In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 699-710. ACM, 1992. URL: https://doi.org/10.1145/129712.129780.
  33. Oded Goldreich, Shafi Goldwasser, and Asaf Nussboim. On the implementation of huge random objects. SIAM Journal on Computing, 39(7):2761-2822, 2010. URL: https://doi.org/10.1137/080722771.
  34. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 218-229, 1987. URL: https://doi.org/10.1145/28395.28420.
  35. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, and Amit Sahai. Efficient non-interactive secure computation. In Kenneth G. Paterson, editor, Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings, volume 6632 of Lecture Notes in Computer Science, pages 406-425. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-20465-4_23.
  36. Yuval Ishai, Amit Sahai, and David A. Wagner. Private circuits: Securing hardware against probing attacks. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science, pages 463-481. Springer, 2003. URL: https://doi.org/10.1007/978-3-540-45146-4_27.
  37. Jeffrey C. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pages 42-53, 1994. URL: https://doi.org/10.1109/SFCS.1994.365706.
  38. Ilan Komargodski, Moni Naor, and Eylon Yogev. How to share a secret, infinitely. In TCC (B2), pages 485-514. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53644-5_19.
  39. Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In FOCS, pages 168-177, 2016. Google Scholar
  40. Yehuda Lindell and Benny Pinkas. An efficient protocol for secure two-party computation in the presence of malicious adversaries. In Moni Naor, editor, Advances in Cryptology - EUROCRYPT 2007, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007, Proceedings, volume 4515 of Lecture Notes in Computer Science, pages 52-78. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-72540-4_4.
  41. Shachar Lovett and Emanuele Viola. Bounded-depth circuits cannot sample good codes. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pages 243-251, 2011. URL: https://doi.org/10.1109/CCC.2011.11.
  42. Silvio Micali and Leonid Reyzin. Physically observable cryptography (extended abstract). In Moni Naor, editor, Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19-21, 2004, Proceedings, volume 2951 of Lecture Notes in Computer Science, pages 278-296. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-24638-1_16.
  43. Moni Naor and Adi Shamir. Visual cryptography. In Advances in Cryptology - EUROCRYPT '94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9-12, 1994, Proceedings, volume 950 of Lecture Notes in Computer Science, pages 1-12, 1994. URL: https://doi.org/10.1007/BFb0053419.
  44. Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 462-467, 1992. URL: https://doi.org/10.1145/129712.129757.
  45. Ramamohan Paturi. On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC '92, pages 468-474, New York, NY, USA, 1992. Association for Computing Machinery. URL: https://doi.org/10.1145/129712.129758.
  46. Anup Rao. Extractors for low-weight affine sources. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 95-101. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/CCC.2009.36.
  47. Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  48. Guy N. Rothblum. How to compute under AC⁰ leakage without secure hardware. In Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 552-569, 2012. URL: https://doi.org/10.1007/978-3-642-32009-5_32.
  49. Rocco A. Servedio and Emanuele Viola. On a special case of rigidity. Electronic Colloquium on Computational Complexity (ECCC), 19:144, 2012. URL: http://eccc.hpi-web.de/report/2012/144.
  50. Adi Shamir. How to share a secret. Commun. ACM, 22(11):612-613, 1979. URL: https://doi.org/10.1145/359168.359176.
  51. Alexander A. Sherstov. Approximating the AND-OR tree. Theory Comput., 9:653-663, 2013. URL: https://doi.org/10.4086/toc.2013.v009a020.
  52. Alexander A. Sherstov. Algorithmic polynomials. SIAM J. Comput., 49(6):1173-1231, 2020. URL: https://doi.org/10.1137/19M1278831.
  53. Yaoyun Shi. Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables. Inform. Process. Lett., 75(1-2):79-83, 2000. URL: https://doi.org/10.1016/S0020-0190(00)00069-7.
  54. 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, 1987, New York, New York, USA, pages 77-82, 1987. URL: https://doi.org/10.1145/28395.28404.
  55. Robert Spalek. A dual polynomial for OR, 2008. URL: http://arxiv.org/abs/0803.4516.
  56. Avishay Tal. Tight bounds on the fourier spectrum of AC⁰. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 15:1-15:31, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.15.
  57. Luca Trevisan. A note on approximate counting for k-dnf. In Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, and Dana Ron, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 417-425, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  58. S. Vadhan and L. Trevisan. Extracting randomness from samplable distributions. In 2000 IEEE 41st Annual Symposium on Foundations of Computer Science, page 32, Los Alamitos, CA, USA, November 2000. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.2000.892063.
  59. Emanuele Viola. The complexity of distributions. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 202-211, 2010. URL: https://doi.org/10.1109/FOCS.2010.27.
  60. Emanuele Viola. Extractors for turing-machine sources. In Anupam Gupta, Klaus Jansen, José Rolim, and Rocco Servedio, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 663-671, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  61. Emanuele Viola. Extractors for circuit sources. SIAM Journal on Computing, 43(2):655-672, 2014. URL: https://doi.org/10.1137/11085983X.
  62. Emanuele Viola. Quadratic maps are hard to sample. ACM Trans. Comput. Theory, 8(4), June 2016. URL: https://doi.org/10.1145/2934308.
  63. Emanuele Viola. Sampling lower bounds: Boolean average-case and permutations. SIAM Journal on Computing, 49(1):119-137, 2020. URL: https://doi.org/10.1137/18M1198405.
  64. Emanuele Viola. Lower bounds for samplers and data structures via the cell-probe separator. Electron. Colloquium Comput. Complex., 28:73, 2021. URL: https://eccc.weizmann.ac.il/report/2021/073.
  65. R. Ryan Williams. Counting solutions to polynomial systems via reductions. In Raimund Seidel, editor, 1st Symposium on Simplicity in Algorithms (SOSA 2018), volume 61 of OpenAccess Series in Informatics (OASIcs), pages 6:1-6:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.SOSA.2018.6.
  66. Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 162-167, 1986. URL: https://doi.org/10.1109/SFCS.1986.25.
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