article

Efficient generation of shared RSA keys

Authors:

Matthew FranklinAuthors Info & Claims

Journal of the ACM (JACM), Volume 48, Issue 4

Pages 702 - 722

https://doi.org/10.1145/502090.502094

Published: 01 July 2001 Publication History

Abstract

We describe efficient techniques for a number of 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. All results are presented in the honest but curious scenario (passive adversary).

References

[1]

ALON, N., GALIL, Z., AND YUNG, M. 1995. Dynamic-resharing verifiable secret sharing. In Proceedings of the 3rd Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 979. Springer-Verlag, New York, pp. 523-537.]]

Digital Library

[2]

BAR-ILAN, J., AND BEAVER, D. 1989. Non-cryptographic fault-tolerant computing in a constant number of rounds of interaction. In Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing (Edmonton, Alb., Canada, Aug. 14-16). ACM, New York, pp. 201-209.]]

Digital Library

[3]

BEAVER, D. 1990. Security, fault tolerance, and communication complexity in distributed systems. Ph.D. dissertation. Harvard University, Cambridge, Mass.]]

Digital Library

[4]

BEN-OR, M., GOLDWASSER, S., AND WIGDERSON, A. 1988. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the 20th Annual ACMSymposium on Theory of Computing (Chicago, Ill., May 2-4). ACM, New York, pp. 1-10.]]

Digital Library

[5]

BENALOH (COHEN), J. 1987. Secret sharing homomorphisms: keeping shares of a secret secret. In Advances in Cryptology-Crypto '86. Lecture Notes in Computer Science, vol. 263. Springer-Verlag, New York, pp. 251-260.]]

Digital Library

[6]

BONEH, D., AND HORWITZ, J. 1998. Generating a product of three primes with an unknown factorization. In Proceedings of the 3rd Algorithmic Number Theory Symposium. Lecture Notes in Computer Science, vol. 1423. Springer-Verlag, New York, pp. 237-251.]]

Digital Library

[7]

CATALANO, D., GENNARO, R., AND HALEVI, S. 2000. Computing inverses over a shared secret modulus. In Advances in Cryptology-Eurocrypt 2000. Lecture Notes in Computer Science, vol. 1807. Springer-Verlag, New York, pp. 196-206.]]

[8]

CHAUM, D., CREPEAU, C., AND DAMGARD, I. 1988. Multiparty unconditionally secure protocols. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (Chicago, Ill., May 2-4). ACM, New York, pp. 11-19.]]

Digital Library

[9]

COCKS, C. 1997. Split knowledge generation of RSA parameters. In Cryptography and Coding: 6th IMA Conference. Lecture Notes in Computer Science, vol. 1423. Springer-Verlag, New York, pp. 237-251.]]

Digital Library

[10]

DE BRUIJN, N. 1950. On the number of uncanceled elements in the sieve of Eratosthenes. Proc. Neder. Akad. Wetensch. 53, pp. 803-812. (Reviewed in LeVeque Reviews in Number Theory, 4, N-28, p. 221.)]]

[11]

DESANTIS, A., DESMEDT, Y., FRANKEL,Y.,AND YUNG, M. 1994. How to share a function securely. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 522-533.]]

Digital Library

[12]

DESMEDT, Y. 1994. Threshold cryptography. Europ. Trans. Telecommun. Related Tech. 5, 4 (July-Aug.). 35-43.]]

[13]

DESMEDT,Y.,AND FRANKEL, Y. 1992. Shared generation of authenticators and signatures. In Advances in Cryptology-Crypto '91. Lecture Notes in Computer Science, vol. 576. Springer-Verlag, New York, pp. 457-469.]]

Digital Library

[14]

ELGAMAL, T. 1985. A public key cryptosystem and a signature scheme based on the discrete logarithm. IEEE Trans. Inf. Theory 31, 4, 469-472.]]

[15]

FEIGE, U., FIAT, A., AND SHAMIR, A. 1988. Zero-knowledge proofs of identity. J. Crypt. 1, 77-94.]]

Digital Library

[16]

FIAT, A., AND SHAMIR, A. 1987. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology-Crypto '86. Lecture Notes in Computer Science, vol. 263. Springer-Verlag, New York, pp. 186-194.]]

Digital Library

[17]

FRANKEL, Y. 1990. A practical protocol for large group oriented networks. In Advances in Cryptology- Eurocrypt '89. Lecture Notes in Computer Science, vol. 434. Springer-Verlag, New York, pp. 56-61.]]

Digital Library

[18]

FRANKEL, Y., GEMMELL, P., MACKENZIE,P.,AND YUNG, M. 1997. Optimal resilience proactive public key cryptosystems. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 384-393.]]

Digital Library

[19]

FRANKEL, Y., MACKENZIE,P.,AND YUNG, M. 1998. Robust efficient distributed RSA-key generation. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (Dallas, Tex., May 23-26). ACM, New York, pp. 663-672.]]

Digital Library

[20]

FRANKLIN, M., AND HABER, S. 1996. Joint encryption and message-efficient secure computation. J. Crypt. 9, 217-232.]]

Digital Library

[21]

GEMMELL, P. 1997. An introduction to threshold cryptography. CryptoBytes, a technical newsletter of RSA Laboratories 2,7.]]

[22]

GENNARO, R., JARECKI, S., KRAWCZYK, H., AND RABIN, T. 1996. Robust and efficient sharing of RSA functions. In Advances in Cryptology-Crypto '96. Lecture Notes in Computer Science, vol. 1109. Springer-Verlag, New York, pp. 157-172.]]

Digital Library

[23]

GENNARO, R., JARECKI, S., KRAWCZYK, H., AND RABIN, T. 1999. Secure distributed key generation for discrete-log based cryptosystems. In Advances in Cryptology-Eurocrypt '99. Lecture Notes in Computer Science, vol. 1592. Springer-Verlag, New York, pp. 295-310.]]

[24]

GILBOA, N. 1999. Two party RSA key generation. In Advances in Cryptology-Crypto '99. Lecture Notes in Computer Science, vol. 1666. Springer-Verlag, New York, pp. 116-129.]]

Digital Library

[25]

GOLDREICH, O., MICALI, S., AND WIGDERSON, A. 1987. How to play any mental game. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (New York, N.Y., May 25-27). ACM, New York, pp. 218-229.]]

Digital Library

[26]

GOLDWASSER, S., MICALI, S., AND RACKOFF, C. 1989. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1, 186-208.]]

Digital Library

[27]

GORDON, J. 1985. Strong primes are easy to find. In Advances in Cryptology-Eurocrypt '84. Lecture Notes in Computer Science, vol. 209. Springer-Verlag, New York, pp. 216-223.]]

Digital Library

[28]

GUILLOU, L., AND QUISQUATER, J. 1988. Apractical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In Advances in Cryptology-Eurocrypt '88. Lecture Notes in Computer Science, vol. 330. Springer-Verlag, New York, pp. 123-128.]]

Digital Library

[29]

MALKIN, M., WU,T.,AND BONEH, D. 1999. Experimenting with shared RSA key generation. In pro-ceedings of the Internet Society's 1999 Symposium on Network and Distributed System Security. Internet Society, Reston, Va., pp. 43-56.]]

[30]

MICALI, S., AND ROGAWAY, P. 1992. Secure computation. In Advances in Cryptology-Crypto '91. Lecture notes in Computer Science, vol. 576. Springer-Verlag, New York, pp. 392-404.]]

Digital Library

[31]

OHTA, K., AND OKAMOTO, T. 1990. A modification of the Fiat-Shamir scheme. In Advances in Cryptology-Crypto '88. Lecture Notes in Computer Science, vol. 403. Springer-Verlag, New York, pp. 232-243.]]

Digital Library

[32]

ONG, H., AND SCHNORR, C. 1991. Fast signature generation with a Fiat-Shamir-like scheme. In Advances in Cryptology-Eurocrypt '90. Lecture Notes in Computer Science, vol. 473. Springer-Verlag, NewYork, pp. 432-440.]]

Digital Library

[33]

PEDERSON, T. 1991. A threshold cryptosystem without a trusted party. In Advances in Cryptology- Eurocrypt 91. Lecture Notes in Computer Science, vol. 547. Springer-Verlag, New York, pp. 522-526.]]

[34]

POUPARD, G., AND STERN, J. 1998. Generation of shared RSA keys by two parties. In Advances in Cryptology-AsiaCrypt '98. Lecture Notes in Computer Science, vol. 1514. Springer-Verlag, New York, pp. 11-24.]]

Digital Library

[35]

RABIN, M. 1980. Probabilistic algorithm for testing primality. J. Num. Theory 12, 128-138.]]

[36]

RABIN, T. 1998. A simplified approach to threshold and proactive RSA. In Advances in Cryptology- Crypto '98. Lecture Notes in Computer Science, vol. 1462. Springer-Verlag, New York, pp. 89-104.]]

Digital Library

[37]

SHAMIR, A. 1979. How to share a secret. Commun. ACM 22, 11 (Nov.), 612-613.]]

Digital Library

[38]

SHOUP, V. 2000. Practical threshold signatures. In Advances in Cryptology-Eurocrypt 2000. Lecture Notes in Computer Science, vol. 1807. Springer-Verlag, New York, pp. 207-220.]]

[39]

SOLOVAY, R., AND STRASSEN, V. 1977. A fast Monte Carlo test for primality. SIAM J. Comput. 6, 84-85.]]

[40]

YAO, A. 1986. Howto generate and exchange secrets. In Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 162-167.]]

Cited By

Lian BCui JChen HZhao XWang FChen KMa M(2024)Trusted Location Sharing on Enhanced Privacy-Protection IoT Without Trusted CenterIEEE Internet of Things Journal10.1109/JIOT.2023.333633711:7(12331-12345)Online publication date: 1-Apr-2024
https://doi.org/10.1109/JIOT.2023.3336337
Haber SMassias H(2024)Time-StampingEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-642-27739-9_136-2(1-6)Online publication date: 2-Aug-2024
https://doi.org/10.1007/978-3-642-27739-9_136-2
Cohen RDoerner JKondi YShelat A(2024)Secure Multiparty Computation with Identifiable Abort via Vindicating ReleaseAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_2(36-73)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68397-8_2
Show More Cited By

Index Terms

Efficient generation of shared RSA keys
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Public key encryption

Recommendations

Improved Distributed RSA Key Generation Using the Miller-Rabin Test
CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security

Secure distributed generation of RSA moduli (e.g., generating N=pq where none of the parties learns anything about p or q) is an important cryptographic task, that is needed both in threshold implementations of RSA-based cryptosystems and in other, ...
Secure and practical threshold RSA
SIN '13: Proceedings of the 6th International Conference on Security of Information and Networks

This article describes a scheme that outputs RSA signatures using a threshold mechanism in which each share has a bitlength close to the bitlength of the RSA modulus. The scheme is proven unforgeable under the standard RSA assumption against an honest ...
Multiparty Generation of an RSA Modulus
Abstract
We present a new multiparty protocol for the distributed generation of biprime RSA moduli, with security against any subset of maliciously colluding parties assuming oblivious transfer and the hardness of factoring. Our protocol is highly modular, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 48, Issue 4

July 2001

303 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/502090

Issue’s Table of Contents

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2001

Published in JACM Volume 48, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

86
Total Citations
View Citations
2,836
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)4

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lian BCui JChen HZhao XWang FChen KMa M(2024)Trusted Location Sharing on Enhanced Privacy-Protection IoT Without Trusted CenterIEEE Internet of Things Journal10.1109/JIOT.2023.333633711:7(12331-12345)Online publication date: 1-Apr-2024
https://doi.org/10.1109/JIOT.2023.3336337
Haber SMassias H(2024)Time-StampingEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-642-27739-9_136-2(1-6)Online publication date: 2-Aug-2024
https://doi.org/10.1007/978-3-642-27739-9_136-2
Cohen RDoerner JKondi YShelat A(2024)Secure Multiparty Computation with Identifiable Abort via Vindicating ReleaseAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_2(36-73)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68397-8_2
Gambhir ASimran Tyagi V(2023)Elevating ‘e’ in RSA: A Path to Improved Encryption Algorithms2023 3rd International Conference on Technological Advancements in Computational Sciences (ICTACS)10.1109/ICTACS59847.2023.10390067(71-75)Online publication date: 1-Nov-2023
https://doi.org/10.1109/ICTACS59847.2023.10390067
Mansouri MÖnen MBen Jaballah W(2022)Learning from Failures: Secure and Fault-Tolerant Aggregation for Federated LearningProceedings of the 38th Annual Computer Security Applications Conference10.1145/3564625.3568135(146-158)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1145/3564625.3568135
Jia MChen JHe KDu RZheng LLai MWang DLiu F(2022)Redactable Blockchain From Decentralized Chameleon Hash FunctionsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2022.319271617(2771-2783)Online publication date: 2022
https://doi.org/10.1109/TIFS.2022.3192716
Chen MDoerner JKondi YLee ERosefield SShelat ACohen R(2022)Multiparty Generation of an RSA ModulusJournal of Cryptology10.1007/s00145-021-09395-y35:2Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s00145-021-09395-y
Zawia AHasan M(2022)A New Class of Trapdoor Verifiable Delay FunctionsFoundations and Practice of Security10.1007/978-3-031-30122-3_5(71-87)Online publication date: 12-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-30122-3_5
Chen MHazay CIshai YKashnikov YMicciancio DRiviere TShelat AVenkitasubramaniam MWang R(2021)Diogenes: Lightweight Scalable RSA Modulus Generation with a Dishonest Majority2021 IEEE Symposium on Security and Privacy (SP)10.1109/SP40001.2021.00025(590-607)Online publication date: May-2021
https://doi.org/10.1109/SP40001.2021.00025
Therar HMohammed EAli A(2020)Biometric Signature based Public Key Security System2020 International Conference on Advanced Science and Engineering (ICOASE)10.1109/ICOASE51841.2020.9436615(1-6)Online publication date: 23-Dec-2020
https://doi.org/10.1109/ICOASE51841.2020.9436615
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents