Séminaire des équipes-projets

Streaming Cryptography

  • Date : 28/06/2012
  • Place : École Normale Supérieure, Amphi Evariste Galois - NIR
  • Guests : Periklis A. Papakonstantinou (ITCS, Tsinghua University)
  • Organisers : Cascade

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 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 complemented the above results 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, instead of computing a function (e.g. multiplying integers) which is impossible in the streaming setting, we encrypt enough information from its computation (when we view this computation appropriately). Thus, we are 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.

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 with Guang Yang. Preliminary impossibility results appear in joint works with Josh Bronson, Ali Juma, and Guang Yang.


Keywords: Cryptographie Seminar Équipe-projet CASCADE Inria-Rocquencourt Periklis A Papakonstantinou