Document Open Access Logo

Learning Versus Pseudorandom Generators in Constant Parallel Time

Authors Shuichi Hirahara, Mikito Nanashima

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.70.pdf
  • Filesize: 0.66 MB
  • 18 pages

Document Identifiers

Author Details

Shuichi Hirahara
  • National Institute of Informatics, Tokyo, Japan
Mikito Nanashima
  • Tokyo Institute of Technology, Japan

Funding

This work was done when the second author was supported by JST, ACT-X Grant Number JPMJAX190M.
  • Hirahara, Shuichi: JST, PRESTO Grant Number JPMJPR2024.

Acknowledgements

We thank the anonymous ITCS reviewers for providing helpful comments and suggestions.

Cite As Get BibTex

Shuichi Hirahara and Mikito Nanashima. Learning Versus Pseudorandom Generators in Constant Parallel Time. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 70:1-70:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.70

Abstract

A polynomial-stretch pseudorandom generator (PPRG) in NC⁰ (i.e., constant parallel time) is one of the most important cryptographic primitives, especially for constructing highly efficient cryptography and indistinguishability obfuscation. The celebrated work (Applebaum, Ishai, and Kushilevitz, SIAM Journal on Computing, 2006) on randomized encodings yields the characterization of sublinear-stretch pseudorandom generators in NC⁰ by the existence of logspace-computable one-way functions, but characterizing PPRGs in NC⁰ seems out of reach at present. Therefore, it is natural to ask which sort of hardness notion is essential for constructing PPRGs in NC⁰. Particularly, to the best of our knowledge, all the previously known candidates for PPRGs in NC⁰ follow only one framework based on Goldreich’s one-way function. 
In this paper, we present a new learning-theoretic characterization for PPRGs in NC⁰ and related classes. Specifically, we consider the average-case hardness of learning for well-studied classes in parameterized settings, where the number of samples is restricted to fixed-parameter tractable (FPT), and show that the following are equivalent:  
- The existence of (a collection of) PPRGs in NC⁰. 
- The average-case hardness of learning sparse 𝔽₂-polynomials on a sparse example distribution and an NC⁰-samplable target distribution (i.e., a distribution on target functions). 
- The average-case hardness of learning Fourier-sparse functions on a sparse example distribution and an NC⁰-samplable target distribution. 
- The average-case hardness of learning constant-depth parity decision trees on a sparse example distribution and an NC⁰-samplable target distribution.  Furthermore, we characterize a (single) PPRG in parity-NC⁰ by the average-case hardness of learning constant-degree 𝔽₂-polynomials on a uniform example distribution with FPT samples. Based on our results, we propose new candidates for PPRGs in NC⁰ and related classes under a hardness assumption on a natural learning problem. An important property of PPRGs in NC⁰ constructed in our framework is that the output bits are computed by various predicates; thus, it seems to resist an attack that depends on a specific property of one fixed predicate.
Conceptually, the main contribution of this study is to formalize a theory of FPT dualization of concept classes, which yields a meta-theorem for the first result. For the second result on PPRGs in parity-NC⁰, we use a different technique of pseudorandom 𝔽₂-polynomials.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic primitives
  • Theory of computation → Boolean function learning
Keywords
  • Parallel cryptography
  • polynomial-stretch pseudorandom generators in NC⁰
  • PAC learning
  • average-case complexity
  • fixed-parameter tractability

Metrics

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

Related Versions

References

  1. A. Akavia, A. Bogdanov, S. Guo, A. Kamath, and A. Rosen. Candidate Weak Pseudorandom Functions in AC⁰ ∘ MOD₂. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS '14, pages 251-260, New York, NY, USA, 2014. Association for Computing Machinery. Google Scholar
  2. D. Angluin and D. Chen. Learning a Random DFA from Uniform Strings and State Information. In Proceedings of the 26th International Conference on Algorithmic Learning Theory, ALT'15, pages 119-133. Springer International Publishing, 2015. Google Scholar
  3. D. Angluin and M. Kharitonov. When Won't Membership Queries Help? Journal of Computer and System Sciences, 50(2):336-355, 1995. Google Scholar
  4. B. Applebaum, A. Bogdanov, and A. Rosen. A Dichotomy for Local Small-Bias Generators. In Ronald Cramer, editor, Theory of Cryptography, pages 600-617. Springer Berlin Heidelberg, 2012. Google Scholar
  5. B. Applebaum, Y. Ishai, and E. Kushilevitz. Cryptography in NC⁰. SIAM Journal on Computing, 36(4):845-888, 2006. Google Scholar
  6. B. Applebaum, Y. Ishai, and E. Kushilevitz. On Pseudorandom Generators with Linear Stretch in NC0. Comput. Complex., 17(1):38-69, April 2008. Google Scholar
  7. B. Applebaum and E. Kachlon. Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error. In IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS19), pages 171-179, 2019. Google Scholar
  8. B. Applebaum and S. Lovett. Algebraic Attacks against Random Local Functions and Their Countermeasures. SIAM Journal on Computing, 47(1):52-79, 2018. Google Scholar
  9. Benny Applebaum. Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions. SIAM J. Comput., 42(5):2008-2037, 2013. Google Scholar
  10. Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 171-180. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806715.
  11. Benny Applebaum and Pavel Raykov. Fast Pseudorandom Functions Based on Expander Graphs. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I, volume 9985 of Lecture Notes in Computer Science, pages 27-56, 2016. Google Scholar
  12. V. Arvind, J. Köbler, and W. Lindner. Parameterized Learnability of Juntas. Theor. Comput. Sci., 410(47-49):4928-4936, November 2009. Google Scholar
  13. I. Ben-Eliezer, R. Hod, and S. Lovett. Random low-degree polynomials are hard to approximate. Comput. Complex., 21(1):63-81, 2012. URL: https://doi.org/10.1007/s00037-011-0020-6.
  14. A. Blum, M. Furst, M. Kearns, and R. J. Lipton. Cryptographic Primitives Based on Hard Learning Problems. In Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO '93, pages 278-291, 1994. Google Scholar
  15. A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Occam’s Razor. Inf. Process. Lett., 24(6):377-380, April 1987. Google Scholar
  16. A. Bogdanov and Y. Qiao. On the Security of Goldreich’s One-Way Function. Comput. Complex., 21(1):83-127, March 2012. Google Scholar
  17. E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl. Low-Complexity Weak Pseudorandom Functions in AC0[MOD2]. In Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, volume 12828 of Lecture Notes in Computer Science, pages 487-516. Springer, 2021. Google Scholar
  18. M. Carmosino, R. Impagliazzo, V. Kabanets, and A. Kolokolova. Learning Algorithms from Natural Proofs. In Proceedings of the 31st Conference on Computational Complexity, CCC'16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  19. M. Carmosino, R. Impagliazzo, V. Kabanets, and A. Kolokolova. Agnostic Learning from Tolerant Natural Proofs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017), volume 81 of LIPIcs, pages 35:1-35:19, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  20. J. Cook, O. Etesami, R. Miller, and L. Trevisan. Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms. In Omer Reingold, editor, Theory of Cryptography, pages 521-538, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. Google Scholar
  21. G. Couteau, A. Dupin, P. Méaux, M. Rossi, and Y. Rotella. On the Concrete Security of Goldreich’s Pseudorandom Generator. In Thomas Peyrin and Steven D. Galbraith, editors, Advances in Cryptology - ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part II, volume 11273 of Lecture Notes in Computer Science, pages 96-124. Springer, 2018. Google Scholar
  22. M. Cryan and P. B. Miltersen. On Pseudorandom Generators in NC⁰. In Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001, Proceedings, volume 2136 of Lecture Notes in Computer Science, pages 272-284. Springer, 2001. Google Scholar
  23. A. Daniely. Complexity Theoretic Limitations on Learning Halfspaces. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC'16, pages 105-117, New York, NY, USA, 2016. ACM. Google Scholar
  24. A. Daniely and S. Shalev-Shwartz. Complexity Theoretic Limitations on Learning DNF’s. In Proceedings of 29th Conference on Learning Theory, volume 49 of COLT'16, pages 815-830, Columbia University, New York, USA, 23-26 June 2016. PMLR. Google Scholar
  25. A. Daniely and G. Vardi. From Local Pseudorandom Generators to Hardness of Learning. In Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 1358-1394. PMLR, 2021. Google Scholar
  26. V. Feldman, P. Gopalan, S. Khot, and A. K. Ponnuswami. New results for learning noisy parities and halfspaces. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 563-574, October 2006. Google Scholar
  27. Yuval Filmus. Junta threshold for low degree boolean functions on the slice. CoRR, abs/2203.04760, 2022. URL: https://doi.org/10.48550/arXiv.2203.04760.
  28. Yuval Filmus and Ferdinand Ihringer. Boolean constant degree functions on the slice are juntas. Discret. Math., 342(12), 2019. URL: https://doi.org/10.1016/j.disc.2019.111614.
  29. O. Goldreich. Foundations of Cryptography: Volume 1. Cambridge University Press, New York, NY, USA, 2006. Google Scholar
  30. O Goldreich. Candidate One-Way Functions Based on Expander Graphs, pages 76-87. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. Google Scholar
  31. O. Goldreich, S. Goldwasser, and S. Micali. How to Construct Random Functions. J. ACM, 33(4):792-807, August 1986. Google Scholar
  32. O. Goldreich and L. A. Levin. A Hard-Core Predicate for All One-Way Functions. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC '89, pages 25-32, New York, NY, USA, 1989. Association for Computing Machinery. Google Scholar
  33. R. Impagliazzo and L. Levin. No better ways to generate hard NP instances than picking uniformly at random. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, FOCS'90, pages 812-821, 1990. Google Scholar
  34. Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai. Cryptography with Constant Computational Overhead. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, pages 433-442, New York, NY, USA, 2008. Association for Computing Machinery. Google Scholar
  35. J. Jackson, H. Lee, R. Servedio, and A. Wan. Learning random monotone DNF. Discrete Applied Mathematics, 159(5):259-271, 2011. Google Scholar
  36. J. Jackson and R. Servedio. Learning Random Log-Depth Decision Trees under Uniform Distribution. SIAM Journal on Computing, 34(5):1107-1128, 2005. Google Scholar
  37. A. Jain, H. Lin, and A. Sahai. Indistinguishability Obfuscation from Well-Founded Assumptions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 60-73, New York, NY, USA, 2021. Association for Computing Machinery. Google Scholar
  38. Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability Obfuscation from LPN over 𝔽_p, DLIN, and PRGs in NC⁰. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part I, volume 13275 of Lecture Notes in Computer Science, pages 670-699. Springer, 2022. Google Scholar
  39. M. Kearns and L. G. Valiant. Cryptographic Limitations on Learning Boolean Formulae and Finite Automata. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC '89, pages 433-444, New York, NY, USA, 1989. Association for Computing Machinery. Google Scholar
  40. M. Kharitonov. Cryptographic Hardness of Distribution-Specific Learning. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC '93, pages 372-381, New York, NY, USA, 1993. Association for Computing Machinery. Google Scholar
  41. E. Kushilevitz and Y. Mansour. Learning Decision Trees Using the Fourier Spectrum. SIAM J. Comput., 22(6):1331-1348, December 1993. Google Scholar
  42. N. Linial, Y. Mansour, and N. Nisan. Constant Depth Circuits, Fourier Transform, and Learnability. J. ACM, 40(3):607-620, July 1993. Google Scholar
  43. Yanyi Liu and Rafael Pass. On the possibility of basing cryptography on exp≠bpp. In Advances in Cryptology – CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part I, pages 11-40, Berlin, Heidelberg, 2021. Springer-Verlag. URL: https://doi.org/10.1007/978-3-030-84242-0_2.
  44. M. Nanashima. Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning. In Proceedings of the 33rd Conference on Learning Theory, COLT'20, volume 125, pages 2998-3029. PMLR, 09-12 July 2020. Google Scholar
  45. M. Nanashima. A Theory of Heuristic Learnability. In Proceedings of the 34th Conference on Learning Theory, COLT'21. PMLR, 2021. Google Scholar
  46. Moni Naor and Omer Reingold. Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions. J. Comput. Syst. Sci., 58(2):336-375, 1999. Google Scholar
  47. Moni Naor and Guy N. Rothblum. Learning to impersonate. In William W. Cohen and Andrew W. Moore, editors, Machine Learning, Proceedings of the Twenty-Third International Conference (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25-29, 2006, volume 148 of ACM International Conference Proceeding Series, pages 649-656. ACM, 2006. Google Scholar
  48. R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, New York, NY, USA, 2014. Google Scholar
  49. R. O'Donnell and D. Witmer. Goldreich’s PRG: Evidence for Near-Optimal Polynomial Stretch. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 1-12, 2014. Google Scholar
  50. I. Oliveira and R. Santhanam. Conspiracies between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. In Proceedings of the 32nd Computational Complexity Conference, CCC'17, Dagstuhl, DEU, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  51. Igor Carboni Oliveira, Rahul Santhanam, and Roei Tell. Expander-Based Cryptography Meets Natural Proofs. Comput. Complex., 31(1):4, 2022. Google Scholar
  52. L. Pitt and L. Valiant. Computational Limitations on Learning from Examples. J. ACM, 35(4):965-984, October 1988. Google Scholar
  53. O. Regev. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. J. ACM, 56(6), September 2009. Google Scholar
  54. H. Ren and R. Santhanam. Hardness of KT Characterizes Parallel Cryptography. In Valentine Kabanets, editor, 36th Computational Complexity Conference (CCC 2021), volume 200 of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1-35:58, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.35.
  55. R. Santhanam. Pseudorandomness and the Minimum Circuit Size Problem. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, volume 151 of LIPIcs, pages 68:1-68:26, 2020. Google Scholar
  56. L. Sellie. Learning Random Monotone DNF Under the Uniform Distribution. In Proceedings of the 21st Annual Conference on Learning Theory, COLT'08, pages 181-192. Omnipress, 2008. Google Scholar
  57. L. Sellie. Exact Learning of Random DNF over the Uniform Distribution. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC'09, pages 45-54, New York, NY, USA, 2009. ACM. Google Scholar
  58. Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York, NY, USA, 2014. Google Scholar
  59. S. Vadhan. On learning vs. refutation. In Proceedings of the 2017 Conference on Learning Theory (COLT'17), volume 65 of Proceedings of Machine Learning Research, pages 1835-1848, Amsterdam, Netherlands, 07-10 July 2017. PMLR. Google Scholar
  60. L. Valiant. A Theory of the Learnable. Commun. ACM, 27(11):1134-1142, 1984. URL: https://doi.org/10.1145/1968.1972.
  61. A. Yao. Theory and Application of Trapdoor Functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, FOCS'82, pages 80-91, November 1982. 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