Abstract
We describe efficient techniques for three (or more) parties to jointly generate an RSA key. At the end of the protocol an RSA modulus N = pq is publicly known. None of the parties know the factorization of N. In addition a public encryption exponent is publicly known and each party holds a share of the private exponent that enables threshold decryption. Our protocols are efficient in computation and communication.
Chapter PDF
References
N. Alon, Z. Galil and M. Yung, “Dynamic-resharing verifiable secret sharing,” ESA 1995.
D. Beaver, “Security, fault tolerance, and communication complexity in distributed systems,” Ph.D. thesis, Harvard University, May 1990.
M. Ben-Or, S. Goldwasser, A. Wigderson, “Completeness theorems for noncryptographic fault tolerant distributed computation”, STOC 1988, pp. 1–10.
J. Benaloh (Cohen), “Secret sharing homomorphisms: keeping shares of a secret secret,” Crypto '86, 251–260.
J. Carter and M. Wegman, “Universal classes of hash functions”, J. Comput. Syst. Sci. 18 (1979), 143–154.
D. Chaum, C. Crépeau, and I. Damgård, “Multiparty unconditionally secure protocols,” ACM STOC 1988, 11–19.
N. De Bruijn, ”On the number of uncanceled elements in the sieve of Eratosthenes”, Proc. Neder. Akad. Wetensch, vol. 53, 1950, pp. 803–812. Reviewed in LeVeque Reviews in Number Theory, Vol. 4, Section N-28, p. 221.
A. DeSantis, Y. Desmedt, Y. Frankel, M. Yung, “How to share a function securely”, STOC 1994, pp. 522–533.
Y. Desmedt, “Threshold cryptography,” European Transactions on Telecommunications and Related Technologies, Vol. 5, No. 4, July–August 1994, pp. 35–43.
Y. Desmedt and Y. Frankel, “Shared generation of authenticators and signatures”, Crypto '91, 457–469.
U. Feige, A. Fiat, and A. Shamir, “Zero-knowledge proofs of identity,” Journal of Cryptology 1 (1988), 77–94.
A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems,” Crypto '86, 186–194.
Y. Frankel, “A practical protocol for large group oriented networks”, Eurocrypt 89, pp. 56–61.
M. Franklin and S. Haber, “Joint encryption and message-efficient secure computation,” Journal of Cryptology, 9 (1996), 217–232.
R. Fagin, M. Naor, P. Winkler, “Comparing information without leaking it”, CACM, Vol 39, No. 5, May 1996, pp. 77–85.
R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin, “Robust and efficient sharing of RSA functions”, Crypto 96, pp. 157–172.
O. Goldreich, S. Micali, A. Wigderson, “How to play any mental game”, STOC 1987, pp. 218–229.
J. Gordon, “Strong primes are easy to find”, Eurocrypt 84, pp. 216–223.
L. Guillou and J. Quisquater, “A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory,” Eurocrypt '88, 123–128.
K. Ohta and T. Okamoto, “A modification of the Fiat-Shamir scheme,” Crpto '88, 232–243.
H. Ong and C. Schnorr, “Fast signature generation with a Fiat Shamir-like scheme,” Eurocrypt '90, 432–440.
T. Pederson, “A threshold cryptosystem without a trusted party,” Proceedings of Eurocrypt 91, pp. 522–526.
M. Rabin, “Probabilistic algorithm for testing primality”, J. of Number Theory, vol. 12, pp. 128–138, 1980.
R. Solovay, V. Strassen, “A fast monte carlo test for primality”, SIAM journal of computing, vol. 6, pp. 84–85, 1977.
M. Wegman and J. Carter, “New hash functions and their use in authentication and set equality”, J. Comput. Syst. Sci. 22 (1981), 265–279.
A. Yao, “How to generate and exchange secrets”, FOCS 1986, pp. 162–167.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag
About this paper
Cite this paper
Boneh, D., Franklin, M. (1997). Efficient generation of shared RSA keys. 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/BFb0052253
Download citation
DOI: https://doi.org/10.1007/BFb0052253
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