Asynchronous Proactive Cryptosystems Without Agreement (extended abstract)
Bartosz Przydatek and Reto Strobl
In this paper, we present efficient asynchronous protocols that allow to build proactive cryptosystems secure against a mobile fail-stop adversary. Such systems distribute the power of a public-key cryptosystem among a set of servers, so that the security and functionality of the overall system is preserved against an adversary that crashes and/or eavesdrops every server repeatedly and transiently, but no more than a certain fraction of the servers at a given time. The building blocks of proactive cryptosystems, to which we present novel solutions, are protocols for joint random secret sharing and for proactive secret sharing. The first protocol provides every server with a share of a random value unpredictable by the adversary, and the second allows to change the shared representation of a secret value. Synchronous protocols for these tasks are well-known, but the standard method for adapting them to the asynchronous model requires an asynchronous agreement sub-protocol.
Our solutions are more efficient as they go without such an agreement sub-protocol. Moreover, they are the first solutions for such protocols having a bounded worst-case complexity, as opposed to only a bounded average-case complexity.
BibTeX Citation
@inproceedings{PrzStr04,
author = {Bartosz Przydatek and Reto Strobl},
title = {Asynchronous Proactive Cryptosystems Without Agreement (extended abstract)},
editor = {Pil Joong Lee},
booktitle = {Advances in Cryptology --- ASIACRYPT 2004},
pages = 152--169,
series = {Lecture Notes in Computer Science},
volume = 3329,
year = 2004,
month = 12,
publisher = {Springer-Verlag},
}