Concentration Bounds for Almost k-wise Independence with Applications to Non-Uniform Security

Concentration Bounds for Almost k-wise Independence with Applications to Non-Uniform Security (via Zoom)

Abstract: We prove a few concentration inequalities for the sum of n binary random variables under weaker conditions than k-wise independence. Namely, we consider two standard conditions that are satisfied in many applications: (a) direct product conditions (b) XOR condition. Both conditions are weaker than mutual independence and both imply strong concentration bounds (similar to Chernoff-Hoeffding) on the tail probability of the sum of bounded random variables ([Impagliazzo and Kabanets, APPROX-RANDOM 10], [Unger, FOCS 09]). Our inequalities can be stated as the implication of threshold direct product theorems from either k-wise direct product conditions, or the k-wise XOR condition. By proving optimality of our inequalities, we show a clear separation for k≪n between k-wise product conditions and XOR condition as well as a stark contrast between k-wise and n-wise product theorems.
 
We use these bounds in the cryptographic application that provides provable security against algorithms with S-bit advice. Namely, we show how the problem reduces to proving S-wise direct product theorems or S-wise XOR lemmas for certain ranges of parameters. Finally, we derive a new S-wise XOR lemma, which yields a tight non-uniform bound for length increasing pseudorandom generators, resolving a 10-year-old open problem from [De, Trevisan, and Tulsiani, CRYPTO 10].
 
Joint work with Nick Gravin, Tsz Chiu Kwok and Pinyan Lu.

Bio: Siyao Guo is an Assistant Professor of Computer Science, NYU Shanghai; Global Network Assistant Professor, NYU. Previously, she was a postdoctoral fellow at the Cybersecurity and Privacy Institute at Northeastern University, Simons Institute for the theory of computation at UC Berkeley, and the Courant Institute of Mathematical Sciences at New York University.  Her research interests are cryptography, computational complexity and pseudorandomness.