Cryptography with Streaming Algorithms

Abstract. We put forth the question of whether cryptography is fea-sible 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 algo-rithms 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 insufficient. In this set-ting 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 con-struct 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