Paper 2020/462

An Information-Theoretic Proof of the Streaming Switching Lemma for Symmetric Encryption

Ido Shahaf, Or Ordentlich, and Gil Segev

Abstract

Motivated by a fundamental paradigm in cryptography, we consider a recent variant of the classic problem of bounding the distinguishing advantage between a random function and a random permutation. Specifically, we consider the problem of deciding whether a sequence of $q$ values was sampled uniformly with or without replacement from $[N]$, where the decision is made by a streaming algorithm restricted to using at most s bits of internal memory. In this work, the distinguishing advantage of such an algorithm is measured by the KL divergence between the distributions of its output as induced under the two cases. We show that for any $ s=\Omega( \log N) $ the distinguishing advantage is upper bounded by $ O(q\cdot s/N) $, and even by $ O(q\cdot s/N \log N) $ when $ q\le N^{1-\epsilon} $ for any constant $ \epsilon>0 $ where it is nearly tight with respect to the KL divergence.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. 2020 IEEE International Symposium on Information Theory (ISIT)
Contact author(s)
ido shahaf @ cs huji ac il
History
2020-04-24: last of 3 revisions
2020-04-24: received
See all versions
Short URL
https://ia.cr/2020/462
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/462,
      author = {Ido Shahaf and Or Ordentlich and Gil Segev},
      title = {An Information-Theoretic Proof of the Streaming Switching Lemma for Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/462},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/462}},
      url = {https://eprint.iacr.org/2020/462}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.