Speaker: Periklis Papakonstantinou
Title: Streaming Cryptography
Three years ago we introduced the concept of Streaming Cryptography; i.e. the possibility of computing cryptographic primitives using a device severely restricted in memory and in its ability to scan its external tape(s). Is it possible to perform cryptography in such a setting, or do the limitations of these devices rule-out such a possibility? For several, natural, black-box settings, and pretty much all popular cryptographic assumptions used today we can show the impossibility of realizing cryptography in a streaming setting.
Recently we showed that one can circumvent lower bounds for specific kinds of constructions by devising a non-black-box technique, showing that Streaming Cryptography is possible if one uses two external streams, and in total 3 passes over them. Roughly speaking, this development encrypts in a streaming fashion not the output itself but enough information regarding the computation of the primitive. This idea is in the work of Applebaum-Ishai-Kushilevitch on Crypto in NC^0 (although their so-called "randomized encodings" cannot be computed in a streaming fashion). In Streaming Crypto we are able to make somewhat counter-intuitive statements, such as: computing the product of two numbers (and permuted variants) is unconditionally impossible in a streaming fashion, however we are still able to base streaming cryptography on the hardness of factoring a composite integer.
To the best of our knowledge, this is the first practical, non-black-box cryptographic construction (note that the vast majority of cryptographic constructions are black-box).
This is joint work (also in progress) with Guang Yang.
Preliminary impossibility results appear in joint works with Josh Bronson, Ali Juma, and Guang Yang.