Document Open Access Logo

Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRG

Authors Sumegha Garg, Pravesh K. Kothari, Ran Raz

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.21.pdf
  • Filesize: 0.59 MB
  • 18 pages

Document Identifiers

Author Details

Sumegha Garg
  • Department of Computer Science, Princeton University, NJ, USA
Pravesh K. Kothari
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Ran Raz
  • Department of Computer Science, Princeton University, NJ, USA

Funding

  • Raz, Ran: Research supported by the Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grant No. CCF-1714779.

Acknowledgements

We would like to thank Avishay Tal and David Woodruff for the discussions about the problem of distinguishing subspaces.

Cite As Get BibTex

Sumegha Garg, Pravesh K. Kothari, and Ran Raz. Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRG. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.21

Abstract

In this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming setting. 
Our first result applies to the problem of distinguishing the uniform distribution on {0,1}ⁿ from uniform distribution on some unknown linear subspace of {0,1}ⁿ. As a specific corollary, we show that any algorithm that distinguishes between uniform distribution on {0,1}ⁿ and uniform distribution on an n/2-dimensional linear subspace of {0,1}ⁿ with non-negligible advantage needs 2^Ω(n) samples or Ω(n²) memory (tight up to constants in the exponent). 
Our second result applies to distinguishing outputs of Goldreich’s local pseudorandom generator from the uniform distribution on the output domain. Specifically, Goldreich’s pseudorandom generator G fixes a predicate P:{0,1}^k → {0,1} and a collection of subsets S₁, S₂, …, S_m ⊆ [n] of size k. For any seed x ∈ {0,1}ⁿ, it outputs P(x_S₁), P(x_S₂), …, P(x_{S_m}) where x_{S_i} is the projection of x to the coordinates in S_i. We prove that whenever P is t-resilient (all non-zero Fourier coefficients of (-1)^P are of degree t or higher), then no algorithm, with < n^ε memory, can distinguish the output of G from the uniform distribution on {0,1}^m with a large inverse polynomial advantage, for stretch m ≤ (n/t) ^{(1-ε)/36 ⋅ t} (barring some restrictions on k). The lower bound holds in the streaming model where at each time step i, S_i ⊆ [n] is a randomly chosen (ordered) subset of size k and the distinguisher sees either P(x_{S_i}) or a uniformly random bit along with S_i. 
An important implication of our second result is the security of Goldreich’s generator with super linear stretch (in the streaming model), against memory-bounded adversaries, whenever the predicate P satisfies the necessary condition of t-resiliency identified in various prior works. 
Our proof builds on the recently developed machinery for proving time-space trade-offs (Raz 2016 and follow-ups). Our key technical contribution is to adapt this machinery to work for distinguishing problems in contrast to prior works on similar results for search/learning problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • memory-sample tradeoffs
  • bounded storage cryptography
  • Goldreich’s local PRG
  • distinguishing problems
  • refuting CSPs

Metrics

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

Related Versions

References

  1. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson. Pseudorandom generators in propositional proof complexity. SIAM J. Comput., 34(1):67-88, 2004. URL: https://doi.org/10.1137/S0097539701389944.
  2. Sarah R. Allen, Ryan O'Donnell, and David Witmer. How to refute a random CSP. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science - FOCS 2015, pages 689-708. IEEE Computer Soc., Los Alamitos, CA, 2015. Google Scholar
  3. Prabhanjan Ananth, Abhishek Jain, and Amit Sahai. Indistinguishability obfuscation from functional encryption for simple functions. Cryptology ePrint Archive, Report 2015/730, 2015. URL: https://eprint.iacr.org/2015/730.
  4. 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
  5. Benny Applebaum. Cryptographic hardness of random local functions - survey. Computational Complexity, 25(3):667-722, 2016. Google Scholar
  6. Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing, pages 171-180. ACM, New York, 2010. Google Scholar
  7. Benny Applebaum, Andrej Bogdanov, and Alon Rosen. A dichotomy for local small-bias generators. J. Cryptology, 29(3):577-596, 2016. Google Scholar
  8. Benny Applebaum and Shachar Lovett. Algebraic attacks against random local functions and their countermeasures. In STOC, pages 1087-1100. ACM, 2016. Google Scholar
  9. Yonatan Aumann, Yan Zong Ding, and Michael O. Rabin. Everlasting security in the bounded storage model. IEEE Trans. Information Theory, 48(6):1668-1680, 2002. URL: https://doi.org/10.1109/TIT.2002.1003845.
  10. Yonatan Aumann and Michael O. Rabin. Information theoretically secure communication in the limited storage space model. In Advances in Cryptology - CRYPTO '99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings, pages 65-79, 1999. URL: https://doi.org/10.1007/3-540-48405-1_5.
  11. Boaz Barak, Zvika Brakerski, Ilan Komargodski, and Pravesh K. Kothari. Limits on low-degree pseudorandom generators (or: Sum-of-squares meets program obfuscation). In Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II, pages 649-679, 2018. URL: https://doi.org/10.1007/978-3-319-78375-8_21.
  12. Boaz Barak, Siu On Chan, and Pravesh K. Kothari. Sum of squares lower bounds from pairwise independence [extended abstract]. In STOC'15 - Proceedings of the 2015 ACM Symposium on Theory of Computing, pages 97-106. ACM, New York, 2015. Google Scholar
  13. Boaz Barak and Ankur Moitra. Noisy tensor completion via the sum-of-squares hierarchy. In COLT, volume 49 of JMLR Workshop and Conference Proceedings, pages 417-445. JMLR.org, 2016. Google Scholar
  14. Paul Beame, Shayan Oveis Gharan, and Xin Yang. Time-space tradeoffs for learning finite functions from random evaluations, with applications to polynomials. In Conference On Learning Theory, pages 843-856, 2018. Google Scholar
  15. Christian Cachin and Ueli M. Maurer. Unconditional security against memory-bounded adversaries. In Advances in Cryptology - CRYPTO '97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, pages 292-306, 1997. URL: https://doi.org/10.1007/BFb0052243.
  16. Michael S. Crouch, Andrew McGregor, Gregory Valiant, and David P. Woodruff. Stochastic streams: Sample complexity vs. space complexity. In ESA, volume 57 of LIPIcs, pages 32:1-32:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  17. Mary Cryan and Peter Bro Miltersen. On pseudorandom generators in NC. In 26th International Symposium on Mathematical Foundations of Computer Science, MFCS, pages 272-284, 2001. Google Scholar
  18. Yuval Dagan and Ohad Shamir. Detecting correlations with little memory and communication. In Conference On Learning Theory, pages 1145-1198, 2018. Google Scholar
  19. Wei Dai, Stefano Tessaro, and Xihu Zhang. Super-linear time-memory trade-offs for symmetric encryption. Cryptology ePrint Archive, Report 2020/663, 2020. URL: https://eprint.iacr.org/2020/663.
  20. Amit Daniely. Complexity theoretic limitations on learning halfspaces. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 105-117. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897520.
  21. Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. More data speeds up training time in learning halfspaces over sparse vectors. In NIPS, pages 145-153, 2013. Google Scholar
  22. Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. The complexity of learning halfspaces using generalized linear methods. In COLT, volume 35 of JMLR Workshop and Conference Proceedings, pages 244-286. JMLR.org, 2014. Google Scholar
  23. Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. From average case complexity to improper learning complexity. In STOC, pages 441-448. ACM, 2014. Google Scholar
  24. Amit Daniely and Shai Shalev-Shwartz. Complexity theoretic limitations on learning dnf’s. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 815-830. JMLR.org, 2016. URL: http://proceedings.mlr.press/v49/daniely16.html.
  25. Ilias Diakonikolas, Themis Gouleakis, Daniel M Kane, and Sankeerth Rao. Communication and memory efficient testing of discrete distributions. In Conference on Learning Theory, pages 1070-1106, 2019. Google Scholar
  26. Stefan Dziembowski and Ueli M. Maurer. On generating the initial key in the bounded-storage model. In Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings, pages 126-137, 2004. URL: https://doi.org/10.1007/978-3-540-24676-3_8.
  27. Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pages 534-543. ACM, New York, 2002. URL: https://doi.org/10.1145/509907.509985.
  28. Sumegha Garg, Pravesh K Kothari, and Ran Raz. Time-space tradeoffs for distinguishing distributions and applications to security of goldreich’s prg. arXiv preprint, 2020. URL: http://arxiv.org/abs/2002.07235.
  29. Sumegha Garg, Ran Raz, and Avishay Tal. Extractor-based time-space lower bounds for learning. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 990-1002. ACM, 2018. Google Scholar
  30. Sumegha Garg, Ran Raz, and Avishay Tal. Time-space lower bounds for two-pass learning. In 34th Computational Complexity Conference (CCC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  31. Oded Goldreich. Candidate one-way functions based on expander graphs. Electronic Colloquium on Computational Complexity (ECCC), 7(90), 2000. Google Scholar
  32. Jiaxin Guan and Mark Zhandary. Simple schemes in the bounded storage model. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 500-524. Springer, 2019. Google Scholar
  33. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, and Amit Sahai. Efficient non-interactive secure computation. In Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings, pages 406-425, 2011. URL: https://doi.org/10.1007/978-3-642-20465-4_23.
  34. Joseph Jaeger and Stefano Tessaro. Tight time-memory trade-offs for symmetric encryption. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 467-497. Springer, 2019. Google Scholar
  35. Gillat Kol, Ran Raz, and Avishay Tal. Time-space hardness of learning sparse parities. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1067-1080. ACM, 2017. Google Scholar
  36. Pravesh K. Kothari and Roi Livni. Improper learning by refuting. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pages 55:1-55:10, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.55.
  37. Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 132-145, 2017. URL: https://doi.org/10.1145/3055399.3055485.
  38. Huijia Lin. Indistinguishability obfuscation from constant-degree graded encoding schemes. In Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, pages 28-57, 2016. URL: https://doi.org/10.1007/978-3-662-49890-3_2.
  39. Huijia Lin. Indistinguishability obfuscation from sxdh on 5-linear maps and locality-5 prgs. Cryptology ePrint Archive, Report 2016/1096, 2016. URL: https://eprint.iacr.org/2016/1096.
  40. Huijia Lin and Stefano Tessaro. Indistinguishability obfuscation from trilinear maps and block-wise local prgs. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I, pages 630-660, 2017. URL: https://doi.org/10.1007/978-3-319-63688-7_21.
  41. Huijia Lin and Vinod Vaikuntanathan. Indistinguishability obfuscation from ddh-like assumptions on constant-degree graded encodings. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 11-20. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.11.
  42. Alex Lombardi and Vinod Vaikuntanathan. Limits on the locality of pseudorandom generators and applications to indistinguishability obfuscation. In Theory of Cryptography - 15th International Conference, TCC, volume 10677, pages 119-137. Springer, 2017. Google Scholar
  43. Alex Lombardi and Vinod Vaikuntanathan. Minimizing the complexity of Goldreich’s pseudorandom generator. IACR Cryptology ePrint Archive, page 277, 2017. Google Scholar
  44. Ueli M. Maurer. Conditionally-perfect secrecy and a provably-secure randomized cipher. J. Cryptology, 5(1):53-66, 1992. URL: https://doi.org/10.1007/BF00191321.
  45. Dana Moshkovitz and Michal Moshkovitz. Mixing implies lower bounds for space bounded learning. In COLT, volume 65 of Proceedings of Machine Learning Research, pages 1516-1566. PMLR, 2017. Google Scholar
  46. Dana Moshkovitz and Michal Moshkovitz. Entropy samplers and strong generic lower bounds for space bounded learning. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  47. Michal Moshkovitz and Naftali Tishby. Mixing complexity and its applications to neural networks. arXiv preprint, 2017. URL: http://arxiv.org/abs/1703.00729.
  48. Elchanan Mossel, Amir Shpilka, and Luca Trevisan. On e-biased generators in NC0. In FOCS, pages 136-145. IEEE Computer Society, 2003. Google Scholar
  49. Elchanan Mossel, Amir Shpilka, and Luca Trevisan. On ε-biased generators in NC⁰. Random Structures Algorithms, 29(1):56-81, 2006. URL: https://doi.org/10.1002/rsa.20112.
  50. N. Nisan and D. Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996. Google Scholar
  51. Ryan O'Donnell and David Witmer. Goldreich’s PRG: evidence for near-optimal polynomial stretch. In IEEE 29th Conference on Computational Complexity - CCC 2014, pages 1-12. IEEE Computer Soc., Los Alamitos, CA, 2014. URL: https://doi.org/10.1109/CCC.2014.9.
  52. Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random csps below the spectral threshold. In STOC, pages 121-131. ACM, 2017. Google Scholar
  53. Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 266-275. IEEE, 2016. Google Scholar
  54. Ran Raz. A time-space lower bound for a large class of learning problems. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 732-742, 2017. Google Scholar
  55. Ohad Shamir. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 163-171, 2014. URL: http://papers.nips.cc/book/advances-in-neural-information-processing-systems-27-2014.
  56. Vatsal Sharan, Aaron Sidford, and Gregory Valiant. Memory-sample tradeoffs for linear regression with small error. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.08544.
  57. Jacob Steinhardt, Gregory Valiant, and Stefan Wager. Memory, communication, and statistical queries. In COLT, volume 49 of JMLR Workshop and Conference Proceedings, pages 1490-1516. JMLR.org, 2016. Google Scholar
  58. Stefano Tessaro and Aishwarya Thiruvengadam. Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries. In Theory of Cryptography Conference, pages 3-32. Springer, 2018. Google Scholar
  59. Salil P. Vadhan. On constructing locally computable extractors and cryptosystems in the bounded storage model. In CRYPTO, volume 2729 of Lecture Notes in Computer Science, pages 61-77. Springer, 2003. Google Scholar
  60. Salil P. Vadhan. On learning vs. refutation. In COLT, volume 65 of Proceedings of Machine Learning Research, pages 1835-1848. PMLR, 2017. Google Scholar
  61. Gregory Valiant and Paul Valiant. Information theoretically secure databases. arXiv preprint, 2016. URL: http://arxiv.org/abs/1605.02646.
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