Abstract
Distributed threshold protocols that incorporate proactive maintenance can tolerate a very strong “mobile adversary.” This adversary may corrupt all participants throughout the lifetime of the system in a non-monotonic fashion (i.e., recoveries are possible) but the adversary is limited to the number of participants it can corrupt during any short time period. The proactive maintenance assures increased security and availability of the cryptographic primitive. We present a proactive RSA system in which a threshold of servers applies the RSA signature (or decryption) function in a distributed manner. Our protocol enables servers which hold the RSA key distributively to dynamically and cooperatively self-update; it is secure even when a linear number of the servers are corrupted during any time period; it efficiently maintains the security of the function; and it enables continuous function availability (correct efficient function application using the shared key is possible at any time). A major technical difficulty in “proactivizing” RSA was the fact that the servers have to update the “distributed representation” of an RSA key, while not learning the order of the group from which keys are drawn (in order not to compromise the RSA security). We give a distributed threshold RSA method which permits “proactivization”.
On leave from Sandia National Labs.
This work was performed under U.S. Department of Energy contract number DE-AC04-94AL85000.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
N. Alon, Z. Galil and M. Yung, Dynamic-resharing Verifiable Secret Sharing, European Symposium on Algorithms (ESA) 95, Springer-Verlag LNCS.
G.R. Blakley, Safeguarding Cryptographic Keys, AFIPS Con. Proc (v. 48), 1979, pp 313–317.
M. Blum, Designing programs to check their work, ICSI Technical report TR-88-009.
C. Boyd, Digital Multisignatures, IMA Conference on Cryptography and Coding, Claredon Press, 241–246, (Eds. H. Baker and F. Piper), 1986.
D. Boneh and M. Franklin, Efficient Generation of Shared RSA Keys, Crypto 97 (these proceedings).
R. Canetti and A. Herzberg, Maintaining Security in the presence of transient faults, Crypto '94, Springer-Verlag, 1994.
J. Cohen and M. Fischer, A robust and verifiable cryptographically secure election scheme, FOCS 85.
A. De Santis, Y. Desmedt, Y. Frankel and M. Yung, How to Share a Function Securely, ACM STOC 94. (First version May 92).
Y. Desmedt and Y. Frankel, Threshold cryptosystems, Crypto '89 Springer-Verlag, 1990.
Y. Desmedt and Y. Frankel, Shared generation of authenticators and signatures, Crypto 91, Springer-Verlag LNCS 576, 1992, pp. 307–315.
P. Feldman, A Practical Scheme for Non-Interactive Verifiable Secret Sharing, Proc. of the 28th IEEE FOCS pp. 427–437, 1987
Y. Frankel, A practical protocol for large group oriented networks, Eurocrypt '89, Springer-Verlarg LNCS 773, pp. 56–61.
Y. Frankel and Y. Desmedt. Distributed reliable threshold multisignatures, Tech. Report version TR-92-04-02, Dept. of EE & CS, Univ. of Wisconsin-Milwaukee, April 1992.
Y. Frankel, P. Gemmell and M. Yung, Witness-based Cryptographic Program Checking and Robust Function Sharing Proc. of STOC 1996, pp. 499–508.
M. Franklin and M. Yung, Secure and Efficient Digital Coin, ICALP 93, Springer Verlag LNCS.
Z. Galil, S. Haber and M. Yung, Minimum-Knowledge Interactive Proofs for Decision Problems, SIAM Journal on Computing, vol. 18, n. 4, pp. 711–739. (Previous version in FOCS 85).
R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin, Robust Threshold DSS Signatures, Eurocrypt 96.
R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin, Robust and Efficient Sharing of RSA, Crypto 96.
S. Goldwasser and S. Micali, Probabilistic Encryption, J. Comp. Sys. Sci. 28, 1984, pp. 270–299.
A. Herzberg, S. Jarecki, H. Krawczyk and M. Yung, How to Cope with Perpetual Leakage, or: Proactive Secret Sharing, Crypto 95.
A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk, and M. Yung, Proactive public key and signature systems, The 4-th ACM Symp. on Comp. and Comm. Security. April 1997.
M. Luby, Pseudorandomness and its Cryptographic Applications, Princeton University Press, 1996.
R. Ostrovsky and M. Yung, How to withstand mobile virus attacks, ACM Symposium on Principles of Distributed Computing (PODC), 1991, pp. 51–61.
R. Rivest, A. Shamir and L. Adleman, A Method for Obtaining Digital Signature and Public Key Cryptosystems, Comm. of the ACM, 21 (1978), pp. 120–126.
A. Shamir. How to share a secret, Comm. of the ACM, 22 (1979), pp. 612–613.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag
About this paper
Cite this paper
Frankel, Y., Gemmell, P., MacKenzie, P.D., Yung, M. (1997). Proactive RSA. In: Kaliski, B.S. (eds) Advances in Cryptology — CRYPTO '97. CRYPTO 1997. Lecture Notes in Computer Science, vol 1294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052254
Download citation
DOI: https://doi.org/10.1007/BFb0052254
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63384-6
Online ISBN: 978-3-540-69528-8
eBook Packages: Springer Book Archive