Paper 2019/413
On the Streaming Indistinguishability of a Random Permutation and a Random Function
Itai Dinur
Abstract
An adversary with $S$ bits of memory obtains a stream of $Q$ elements that are uniformly drawn from the set $\{1,2,\ldots,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 $\sqrt{Q \cdot S/N}$. Jaeger and Tessaro used this bound as a streaming switching lemma which allowed proving that known timememory tradeoff attacks on several modes of operation (such as countermode) are optimal up to a factor of $O(\log N)$ if $Q \cdot S \approx N$. However, the bound's proof assumed an unproven combinatorial conjecture. Moreover, if $Q \cdot S \ll N$ there is a gap between the upper bound of $\sqrt{Q \cdot S/N}$ and the $Q \cdot S/N$ advantage obtained by known attacks. In this paper, we prove a tight upper bound (up to polylogarithmic factors) of $O(\log Q \cdot Q \cdot 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 uniquedisjointness communication complexity problem to streaming.
Note: Minor changes
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 A minor revision of an IACR publication in Eurocrypt 2020
 Keywords
 Streaming algorithmtimememory tradeoffcommunication complexityprovable securityswitching lemmamode of operation.
 Contact author(s)
 dinuri @ cs bgu ac il
 History
 20200718: last of 2 revisions
 20190422: received
 See all versions
 Short URL
 https://ia.cr/2019/413
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/413, author = {Itai Dinur}, title = {On the Streaming Indistinguishability of a Random Permutation and a Random Function}, howpublished = {Cryptology ePrint Archive, Paper 2019/413}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/413}}, url = {https://eprint.iacr.org/2019/413} }