  Streaming interactive proofs (SIPs) enable a space-bounded algorithm with
one-pass access to a massive stream of data to verify a computation that
requires large space, by communicating with a powerful but untrusted prover.
  This work initiates the study of zero-knowledge proofs for data streams. We
define the notion of zero-knowledge in the streaming setting and construct
zero-knowledge SIPs for the two main algorithmic building blocks in the
streaming interactive proofs literature: the sumcheck and polynomial evaluation
protocols. To the best of our knowledge all known streaming interactive proofs
are based on either of these tools, and indeed, this allows us to obtain
zero-knowledge SIPs for central streaming problems such as index, point and
range queries, median, frequency moments, and inner product.
  Our protocols are efficient in terms of time and space, as well as
communication: the verifier algorithm's space complexity is
$\mathrm{polylog}(n)$ and, after a non-interactive setup that uses a random
string of near-linear length, the remaining parameters are $n^{o(1)}$.
  En route, we develop an algorithmic toolkit for designing zero-knowledge data
stream protocols, consisting of an algebraic streaming commitment protocol and
a temporal commitment protocol.Our analyses rely on delicate algebraic and
information-theoretic arguments and reductions from average-case communication
complexity.
