Concentration bounds for almost k -wise independence with applications to non-uniform security
Nick Gravin, Siyao Guo, Tsz Chiu Kwok, Pinyan Lu · Society for Industrial and Applied Mathematics eBooks · 2021
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) the 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].