Speaker: Periklis A. Papakonstantinou (IIIS Tsinghua University)
Time & date: 4:00pm, May 29
Place: CELC seminar room (404, 4F)
Title: Cryptography with Streaming Algorithms

Abstract: We put forth the question of whether cryptography is feasible using streaming devices. We
give constructions and prove lower bounds. In streaming cryptography (not to be confused
with stream-ciphers) everything|the keys, the messages, and the seeds|are huge compared
to the internal memory of the device. These streaming algorithms have small internal memory
size and make a constant number of passes over big data maintained in a constant number of
read/write external tapes. Typically, the internal memory size is O(log n) and we use 2 external
tapes; whereas 1 tape is provably insucient. In this setting we cannot compute instances of
popular intractability assumptions. Nevertheless, we base cryptography on these assumptions
by employing non-black-box techniques, and study its limitations.
We introduce new techniques to obtain unconditional lower bounds showing that no super-
linear stretch pseudorandom generator exists, and no Public Key Encryption (PKE) exists with
private-keys of size sub-linear in the plaintext length.
For possibility results, assuming the existence of one-way functions computable in NC1|e.g.
factoring, lattice assumptions|we obtain streaming algorithms computing one-way functions
and pseudorandom generators. Given the Learning With Errors (LWE) assumption we construct
PKE where both the encryption and decryption are streaming algorithms. The starting point
of our work is the groundbreaking work of Applebaum-Ishai-Kushilevitz on Cryptography in
NC0. In the end, our developments are technically orthogonal to their work; e.g. there is a PKE
where the decryption is a streaming algorithm, whereas no PKE decryption can be in NC0.