Asynchronous Proactive Cryptosystems Without Agreement

In this paper we present efficient asynchronous protocols that allow to build proactive versions of a large class of public key cryptosystems for signing and encryption. Such proactive cryptosystems tolerate an adversary that may corrupt every server transiently and repeatedly, but no more than a certain fraction 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 representation of a sharing. Synchronous protocols for these tasks are well-known, but the standard method for turning them into 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.