Asynchronous Perfectly Secure Communication over One-Time Pads

Giovanni Di Crescenzo, Aggelos Kiayias

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)978-3-540-31691-6
ISBN (Print)978-3-540-27580-0
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Asynchronous Perfectly Secure Communication over One-Time Pads'. Together they form a unique fingerprint.

Cite this