Cryptology ePrint Archive: Report 2004/292

Asynchronous Proactive RSA

Ruishan Zhang and Kefei Chen

Abstract: Nowadays, to model practical systems better, such as the Internet network and ad hoc networks, researchers usually regard these systems as asynchronous networks. Meanwhile, proactive secret sharing schemes are often employed to tolerate a mobile adversary. Considering both aspects, an asynchronous proactive threshold signature scheme is needed to keep computer systems secure. So far, two asynchronous proactive secret sharing schemes have been proposed. One is proposed by Zhou in 2001, which is for RSA schemes. The other scheme is proposed by Cachin in 2002, which is a proactive secret sharing scheme for discrete-log schemes. There exist several drawbacks in both schemes. In Zhou¡¯s scheme, the formal security proof of this scheme is missing. Furthermore, Zhou¡¯s scheme needs to resort to the system administrator as the trusted third party for further run when some Byzantine errors occur. In Cachin¡¯s scheme, the building block is based on the threshold RSA scheme proposed by Shoup. However, how to proactivize Shoup¡¯s scheme is omitted in Cachin¡¯s scheme, so this scheme is incomplete. In this paper, we present a complete provably secure asynchronous proactive RSA scheme (APRS). Our paper has four contributions. Firstly, we present a provably secure asynchronous verifiable secret sharing for RSA schemes (asynchronous verifiable additive secret sharing, AVASS), which is based on a verifiable additive secret sharing over integers. Secondly, we propose an asynchronous threshold RSA signature scheme that is based on the AVASS scheme and the random oracle model, and is capable of being proactivized. Thirdly, we present a provably secure threshold coin-tossing scheme on the basis of the above threshold RSA scheme. Fourthly, we propose an asynchronous proactive secret sharing based on the threshold RSA scheme and the coin-tossing scheme. Finally, combining the proactive secret sharing scheme and the threshold RSA scheme, we achieve a complete provably secure asynchronous proactive RSA scheme.

Category / Keywords: Asynchronous networks, Threshold RSA signature, Provably secure, Asynchronous verifiable secret sharing, Asynchronous proactive secret sharing scheme, Threshold coin-tossing scheme

Publication Info: unpulished

Date: received 7 Nov 2004, last revised 9 Feb 2005

Contact author: zhang-rs at cs sjtu edu cn

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: We revised some proof in our scheme.

Version: 20050209:103206 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]