Time-space tradeoffs for distinguishing distributions and applications to security of Goldreich's PRG

Sumegha Garg, Pravesh Kumar Kothari, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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}n from uniform distribution on some unknown linear subspace of {0, 1}n. As a specific corollary, we show that any algorithm that distinguishes between uniform distribution on {0, 1}n and uniform distribution on an n/2-dimensional linear subspace of {0, 1}n with non-negligible advantage needs 2Ω(n) samples or Ω(n2) 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 S1, S2,..., Sm ⊆ [n] of size k. For any seed x ∈ {0, 1}n, it outputs P(xS1), P(xS2),..., P(xSm) where xSi is the projection of x to the coordinates in Si. 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 ≤ (nt )(1-ε/36) ·t (barring some restrictions on k). The lower bound holds in the streaming model where at each time step i, Si ⊆ [n] is a randomly chosen (ordered) subset of size k and the distinguisher sees either P(xSi) or a uniformly random bit along with Si. 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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020
EditorsJaroslaw Byrka, Raghu Meka
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771641
DOIs
StatePublished - Aug 1 2020
Event23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020 - Virtual, Online, United States
Duration: Aug 17 2020Aug 19 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume176
ISSN (Print)1868-8969

Conference

Conference23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020
CountryUnited States
CityVirtual, Online
Period8/17/208/19/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Bounded storage cryptography
  • Distinguishing problems
  • Goldreich's local PRG
  • Memory-sample tradeoffs
  • Refuting CSPs

Fingerprint Dive into the research topics of 'Time-space tradeoffs for distinguishing distributions and applications to security of Goldreich's PRG'. Together they form a unique fingerprint.

Cite this