On the Streaming Indistinguishability of a Random Permutation and a Random Function

An adversary with S bits of memory obtains a stream of Q elements that are uniformly drawn from the set minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\{1,2,\ldots ,N\}$document1,2,…,N, either with or without replacement. This corresponds to sampling Q elements using either a random function or a random permutation. The adversary’s goal is to distinguish between these two cases. This problem was first considered by Jaeger and Tessaro (EUROCRYPT 2019), which proved that the adversary’s advantage is upper bounded by minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\sqrt{Q \cdot S/N}$documentQ·S/N. Jaeger and Tessaro used this bound as a streaming switching lemma which allowed proving that known time-memory tradeoff attacks on several modes of operation (such as counter-mode) are optimal up to a factor of minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$O(\log N)$documentO(logN) if minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$Q \cdot S \approx N$documentQ·S≈N. However, the bound’s proof assumed an unproven combinatorial conjecture. Moreover, if minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$Q \cdot S \ll N$documentQ·S≪N there is a gap between the upper bound of minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\sqrt{Q \cdot S/N}$documentQ·S/N and the minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$Q \cdot S/N$documentQ·S/N advantage obtained by known attacks. In this paper, we prove a tight upper bound (up to poly-logarithmic factors) of minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$O(\log Q \cdot Q \cdot S/N)$documentO(logQ·Q·S/N) on the adversary’s advantage in the streaming distinguishing problem. The proof does not require a conjecture and is based on a hybrid argument that gives rise to a reduction from the unique-disjointness communication complexity problem to streaming.