Abstract
In this work, we establish lowerbounds 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/2dimensional linear subspace of {0,1}ⁿ with nonnegligible 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 tresilient (all nonzero 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 memorybounded adversaries, whenever the predicate P satisfies the necessary condition of tresiliency identified in various prior works.
Our proof builds on the recently developed machinery for proving timespace tradeoffs (Raz 2016 and followups). 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.
BibTeX  Entry
@InProceedings{garg_et_al:LIPIcs:2020:12624,
author = {Sumegha Garg and Pravesh K. Kothari and Ran Raz},
title = {{TimeSpace Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRG}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {21:121:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12624},
URN = {urn:nbn:de:0030drops126248},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.21},
annote = {Keywords: memorysample tradeoffs, bounded storage cryptography, Goldreich’s local PRG, distinguishing problems, refuting CSPs}
}
Keywords: 

memorysample tradeoffs, bounded storage cryptography, Goldreich’s local PRG, distinguishing problems, refuting CSPs 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) 
Issue Date: 

2020 
Date of publication: 

11.08.2020 