Abstract:
We consider the computation of cryptographic primitives using streaming devices. In this setting everything: keys, messages, ciphertexts, seeds, etc, are huge compared to the internal memory size of a streaming device which computes over Big Data. These data are thought to be stored in hard disks, or disk arrays or other sequentially accessed devices. For example, suppose that the total input length is n, there are two external tapes (initially one contains the input, whereas the other is auxiliary and initially empty), these two tapes can be scanned in total for no more than 10 times, and the internal memory (work memory) is of size O(logn). Can we do Cryptography in this setting, or because of the limitations of the device no cryptographically secure primitive can be computed?

Interestingly, in the above setting we cannot multiply two integers (say each of them n/2-bits long). In fact, this is true even when the number of passes is anything o(logn) and the internal memory a small polynomial n^epsilon. Although multiplication is impossible, is it still possible to base cryptography on the hardness of FACTORING? Surprisingly, the answer is yes through the use of non-black-box techniques. In fact, a great deal of Crypto can be done in this setting: computing one-way functions, pseudo-random generators, and Public-Key Encryption (using lattice assumptions). Also, unconditional lower bounds in the lengths of the keys can be proved by some new information theoretic lower bounding techniques.

This is joint work with Guang Yang.

Biography:
Prof. Papakonstantinou is an Assistant Professor at the Institute for Theoretical Computer Science of the Institute for Interdisciplinary Information Sciences, Tsinghua University. Right before that he did a PhD in Computer Science, an MSc in Mathematics (simultaneously to the PhD), and before that an MSc in Computer Science, all from the University of Toronto. His under graduate studies were in Computer Engineering and Science, University of Patras, and he is a licensed Electronics Engineer with the Technical Chamber of Greece. His research biases are towards Cryptography, Computational Complexity, computational problems with engineering motivation in particular their intersection with Algebra, Combinatorics, and Randomness.