nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Multiparty Generation of an RSA Modulus

verfasst von : Megan Chen, Ran Cohen, Jack Doerner, Yashvanth Kondi, Eysa Lee, Schuyler Rosefield, Abhi Shelat

Erschienen in: Advances in Cryptology – CRYPTO 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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, and its uppermost layer can be viewed as a template that generalizes the structure of prior works and leads to a simpler security proof. We introduce a combined sampling-and-sieving technique that eliminates both the inherent leakage in the approach of Frederiksen et al. (Crypto’18), and the dependence upon additively homomorphic encryption in the approach of Hazay et al. (JCrypt’19). We combine this technique with an efficient, privacy-free check to detect malicious behavior retroactively when a sampled candidate is not a biprime, and thereby overcome covert rejection-sampling attacks and achieve both asymptotic and concrete efficiency improvements over the previous state of the art.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF

Nächstes Kapitel Non-malleability Against Polynomial Tampering

Prior works generally consider RSA key generation and include steps for generating shares of e and d such that \(e\cdot d \equiv 1 \pmod {\varphi (N)}\). This work focuses only on the task of sampling the RSA modulus \(N\). Prior techniques can be applied to sample (e, d) after sampling \(N\), and the distributed generation of an RSA modulus has standalone applications, such as for generating the trusted setup required by verifiable delay functions [28, 35]; consequently, we omit further discussion of e and d.

The folklore technique involves invoking the protocol iteratively, each iteration eliminating one corrupt party until a success occurs. For a constant fraction of corruptions, the implied linear round complexity overhead can be reduced to super-constant (e.g., \(\log ^*{n}\)) [10].

In other words, a biprime of length \(2{\kappa } \) provides \({\lambda } \) bits of security.

Technically, Katz and Lindell specify that sampling failures are permitted with negligible probability, and require \(\mathsf {GenModulus} \) to run in strict polynomial time. We elide this detail.

Boneh and Franklin actually propose two variations, one of which has no false negatives; we choose the other variation, as it leads to a more efficient sampling protocol.

\({\mathsf {CRTSample}}\) never outputs biprimes with factors smaller than \({\kappa } \), whereas \({\mathsf {BFGM}}\) outputs such biprimes with negligible probability. The discrepancy of share ranges can be remedied by using non-integer values of \({\kappa } \) with \({\mathsf {BFGM}}\).

Algesheimer, J., Camenisch, J., Shoup, V.: Efficient computation modulo a shared secret with application to the generation of shared safe-prime products. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 417–432. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_27CrossRef

Barker, E.: NIST special publication 800–57, part 1, revision 4 (2016). https://doi.org/10.6028/NIST.SP.800-57pt1r4

Boneh, D., Franklin, M.K.: Efficient generation of shared RSA keys. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 425–439. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052253CrossRef

Boneh, D., Franklin, M.K.: Efficient generation of shared RSA keys. J. ACM 48(4), 702–722 (2001)MathSciNetCrossRef

Boyle, E., et al.: Efficient two-round OT extension and silent non-interactive secure computation. In: ACM CCS, pp. 291–308 (2019)

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: FOCS, pp. 136–145 (2001)

Chen, M., et al.: Muliparty generation of an RSA modulus (2020). http://eprint.iacr.org/2020/370

Cocks, C.: Split knowledge generation of RSA parameters. In: Darnell, M. (ed.) Cryptography and Coding 1997. LNCS, vol. 1355, pp. 89–95. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0024452CrossRef

Cocks, C.: Split generation of RSA parameters with multiple participants (1998). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.177.2600

10.

Cohen, R., Haitner, I., Omri, E., Rotem, L.: From fairness to full security in multiparty computation. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 216–234. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_12CrossRefMATH

11.

Cohen, R., Lindell, Y.: Fairness versus guaranteed output delivery in secure multiparty computation. JCRYPT 30(4), 1157–1186 (2017)MathSciNetMATH

12.

Damgård, I., Mikkelsen, G.L.: Efficient, robust and constant-round distributed RSA key generation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 183–200. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_12CrossRef

13.

Doerner, J., Kondi, Y., Lee, E., Shelat, A.: Secure two-party threshold ECDSA from ECDSA assumptions. In: S&P, pp. 980–997 (2018)

14.

Doerner, J., Kondi, Y., Lee, E., Shelat, A.: Threshold ECDSA from ECDSA assumptions: the multiparty case. In: S&P (2019)

15.

Frankel, Y., MacKenzie, P.D., Yung, M.: Robust efficient distributed RSA-key generation. In: PODC, p. 320 (1998)

16.

Frederiksen, T.K., Lindell, Y., Osheter, V., Pinkas, B.: Fast distributed RSA key generation for semi-honest and malicious adversaries. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 331–361. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_12CrossRef

17.

Gilboa, N.: Two party RSA key generation. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 116–129. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_8CrossRef

18.

Goldreich, O.: The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press (2001)

19.

Hazay, C., Mikkelsen, G.L., Rabin, T., Toft, T.: Efficient RSA key generation and threshold paillier in the two-party setting. In: Dunkelman, O. (ed.) CT-RSA 2012. LNCS, vol. 7178, pp. 313–331. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-27954-6_20CrossRefMATH

20.

Hazay, C., Mikkelsen, G.L., Rabin, T., Toft, T., Nicolosi, A.A.: Efficient RSA key generation and threshold paillier in the two-party setting. JCRYPT 32(2), 265–323 (2019)MathSciNetMATH

21.

Hazay, C., Scholl, P., Soria-Vazquez, E.: Low cost constant round MPC combining BMR and oblivious transfer. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 598–628. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_21CrossRef

22.

Ishai, Y., Ostrovsky, R., Zikas, V.: Secure multi-party computation with identifiable abort. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 369–386. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_21CrossRef

23.

Joye, M., Pinch, R.: Cheating in split-knowledge RSA parameter generation. In: Workshop on Coding and Cryptography, pp. 157–163 (1999)

24.

Katz, J., Lindell, Y.: Digital signature schemes. In: Introduction to Modern Cryptography, 2nd edn, pp. 443–486. Chapman & Hall/CRC (2015)

25.

Knuth, D.E.: The Art of Computer Programming, Volume II: Seminumerical Algorithms (1969)

26.

Malkin, M., Wu, T., Boneh, D.: Experimenting with shared RSA key generation. In: NDSS, pp. 43–56 (1999)

27.

Miller, G.L.: Riemann’s hypothesis and tests for primality. J. Comput. Syst. Sci. 13(3), 300–317 (1976)MathSciNetCrossRef

28.

Pietrzak, K.: Simple verifiable delay functions. In: ITCS, pp. 60:1–60:15 (2019)

29.

Poupard, G., Stern, J.: Generation of shared RSA keys by two parties. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 11–24. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49649-1_2CrossRef

30.

Rabin, M.O.: Probabilistic algorithm for testing primality. J. Number Theory 12(1), 128–138 (1980)MathSciNetCrossRef

31.

Rivest, R.L.: A description of a single-chip implementation of the RSA cipher (1980)

32.

Rivest, R.L.: RSA chips (past/present/future). In: Beth, T., Cot, N., Ingemarsson, I. (eds.) EUROCRYPT 1984. LNCS, vol. 209, pp. 159–165. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-39757-4_16CrossRef

33.

Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MathSciNetCrossRef

34.

Wang, X., Ranellucci, S., Katz, J.: Global-scale secure multiparty computation. In: ACM CCS, pp. 39–56 (2017)

35.

Wesolowski, B.: Efficient verifiable delay functions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 379–407. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_13CrossRef

Titel: Multiparty Generation of an RSA Modulus
verfasst von: Megan Chen
Ran Cohen
Jack Doerner
Yashvanth Kondi
Eysa Lee
Schuyler Rosefield
Abhi Shelat
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56876-4

Electronic ISBN: 978-3-030-56877-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-56877-1_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner