SPEAKER:
Giovanni Di Crescenzo 
Telcordia

TITLE:   
Asynchronous Perfectly Secure Communication over One-Time Pads

ABSTRACT:
The One-Time Pad is a fundamental cryptographic protocol as it
represents the ideal in secure unidirectional communication (i.e., in
cases where there is a designated sender and a designated receiver)
both in terms of security (in the presence of eavesdroppers) as well
as in terms of computational efficiency. Surprisingly, no modeling and
investigation of this protocol has been done in important practical
settings, as distributed and asynchronous ones. In this work we
introduce an asynchronous model for multidirectional and multi-player
One-Time Pad asynchronous communication protocols. In this model the
random pad is shared by all players, and there is no designated sender
and receiver; in fact any participating player can act as a receiver
at any given time, players communicate in a totally asynchronous
fashion and may arbitrarily go off-line.

We define the problem of designing One-Time Pad asynchronous
communication protocols, where the goal is that of maximizing the
amount of the shared pad used before new randomness needs to be
generated, with the constraint of mantaining the security property
under reasonable adversarial assumptions on the relative behavior of
the players and the network. We present lower bounds and protocol
solutions for this problem that significantly improve over the obvious
scenario where parties use an equal fraction of the pad. Our
constructions are non-interactive in the sense that they require no
additional synchronizing communication beyond the (usual) information
that accompanies each ciphertext.

This is joint work with Aggelos Kiayias.