Speaker: Periklis Papakonstantinou Tsinghua University
Time: 2012-05-10 14:00-2012-05-10 15:00
Venue: FIT 1-222
Abstract:
Cryptography and its Foundations is probably the most successful area which lies in the intersection of Applications and Theory of Computing. Part of its success is due to the 1000s of constructions based on 10s of assumptions regarding cryptographic hardness. Despite this success almost every construction (but a few examples you can count on the fingers of one hand) are black-box. This means that starting from elementary primitives such as one-way functions, or trapdoor permutations one can do most of the known Private- and Public-key cryptography, where in the construction of the new primitive we do not need to care about the specific implementation (e.g. the code) of the primitive we base our construction on. To put things in context: think of the construction of a standard Private-Key Encryption constructed using e.g. a pseudo-random generator. In this construction we evaluate the generator on the given key, and the only thing we care about is that the output of the generator has the pseudo-random property.
How far can black-box techniques take us?
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 do cryptography in such a setting, or because of the limitations of such devices every function computed this way cannot be cryptographically hard (in any common use of the term)? The answer to this question is very surprising. 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. On the other hand, we devise a non-black-box technique through which we show that it is possible to encrypt in a streaming fashion not the output itself but enough information regarding the computation of the primitive. Under this technical development we able to make somewhat counter-intuitive statements, such as: computing the product of two numbers (and any of its 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.
This is joint work in progress with Guang Yang.
Preliminary impossibility results appear in manuscripts and published papers, in joint works with Joshua Bronson, Ali Juma, and Guang Yang.
Short Bio:
