International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Separating Adaptive Streaming from Oblivious Streaming using the Bounded Storage Model

Authors:
Haim Kaplan , Tel Aviv University
Yishay Mansour , Tel Aviv University
Kobbi Nissim , Georgetown University
Uri Stemmer , Ben-Gurion University
Download:
DOI: 10.1007/978-3-030-84252-9_4 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2021
Abstract: Streaming algorithms are algorithms for processing large data streams, using only a limited amount of memory. Classical streaming algorithms typically work under the assumption that the input stream is chosen independently from the internal state of the algorithm. Algorithms that utilize this assumption are called oblivious algorithms. Recently, there is a growing interest in studying streaming algorithms that maintain utility also when the input stream is chosen by an adaptive adversary, possibly as a function of previous estimates given by the streaming algorithm. Such streaming algorithms are said to be adversarially-robust. By combining techniques from learning theory with cryptographic tools from the bounded storage model, we separate the oblivious streaming model from the adversarially-robust streaming model. Specifically, we present a streaming problem for which every adversarially-robust streaming algorithm must use polynomial space, while there exists a classical (oblivious) streaming algorithm that uses only polylogarithmic space. This is the first general separation between the capabilities of these two models, resolving one of the central open questions in adversarial robust streaming.
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31258,
  title={Separating Adaptive Streaming from Oblivious Streaming using the Bounded Storage Model},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-84252-9_4},
  author={Haim Kaplan and Yishay Mansour and Kobbi Nissim and Uri Stemmer},
  year=2021
}