Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Journal of Cryptology
Erschienen in: Journal of Cryptology 2/2019

05.02.2018

Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting

verfasst von: Carmit Hazay, Gert Læssøe Mikkelsen, Tal Rabin, Tomas Toft, Angelo Agatino Nicolosi

Erschienen in: Journal of Cryptology | Ausgabe 2/2019

Einloggen

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

search-config
loading …

Abstract

The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is a complete Paillier (in: EUROCRYPT, pp 223–238, 1999) threshold encryption scheme in the two-party setting with security against malicious attacks. We further describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation protocol is comprised of the following subprotocols: (i) a distributed protocol for generation of an RSA composite and (ii) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite for the public key and is comprised of the following subprotocols: (i) a distributed generation of the corresponding secret key shares and (ii) a distributed decryption protocol for decrypting according to Paillier.
Nächster Artikel Automated Analysis of Cryptographic Assumptions in Generic Group Models

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
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Specifically, we set t such that \(2^t\) is smaller than any prime factor of \(N_P\). This guarantees that the difference between challenges is co-prime to \(N_P\).
 
2
In some settings, early abort may not be considered as a breach of security (even if the abort occurs as a result of gaining information about the factorization of the public key). This is due to the fact that the honest party halts as well, outputting \(\bot \). Thus, essentially, no damage was caused. However, this is not true for applications where the shares are chosen based on the honest party’s secret state. Realizing this functionality requires to incorporate into it a secret state of the users. Unfortunately, our protocol cannot compute this functionality in a secure manner, as it must be that the composite generation and the biprimality test run together. Meaning, the parties only learn the composite if it is accepted by the biprimality test.
 
3
Our key differs slightly; however, the principles and the construction are essentially the same.
 
4
See Footnote 2.
 
5
For \(i=j\), the party in question simply computes a dummy sharing of the known value \(p_iq_j\).
 
6
For efficiency, \(P_i\) may send the same encryption to all other parties; we do not demand this behavior, though.
 
7
Note that the application of \(\pi _{\scriptscriptstyle \mathrm {BOUND}}\) on ciphertext \(c_{p_i,j}\) is critical, as this guarantees an honest \(P_j\) that its masking will hide \(q_j\).
 
8
v is invertible except with negligible probability.
 
Literatur
1.
J. Algesheimer, J. Camenisch, V. Shoup, Efficient computation modulo a shared secret with application to the generation of shared safe-prime products, in M. Yung, editor, CRYPTO. Lecture Notes in Computer Science, vol. 2442 (Springer, 2002), pp. 417–432
2.
J. Bar-Ilan, D. Beaver, Non-cryptographic fault-tolerant computing in a constant number of rounds of interaction, in P. Rudnicki, editor, Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing (ACM Press, New York, 1989), pp 201–209
3.
4.
R. Bendlin, I. Damgård, C. Orlandi, S. Zakarias. Semi-homomorphic encryption and multiparty computation, in EUROCRYPT (2011), pp. 169–188
5.
6.
O. Baudron, P. A. Fouque, D. Pointcheval, G. Poupard, J. Stern. Practical multi-candidate election system, in PODC (ACM Press, 2001), pp. 274–283
7.
F. Boudot. Efficient proofs that a committed number lies in an interval, in B. Preneel, editor, EUROCRYPT. Lecture Notes in Computer Science, vol. 1807 (Springer, 2000), pp. 431–444
8.
9.
R. Canetti, Universally composable security: a new paradigm for cryptographic protocols, in FOCS (2001), pp. 136–145
10.
R. Cramer, I. Damgård, On the amortized complexity of zero-knowledge protocols, in CRYPTO (2009), pp. 177–191
11.
R. Cramer, I. Damgård, J. B. Nielsen, Multiparty computation from threshold homomorphic encryption, in EUROCRYPT (2001), pp. 280–299
12.
D. Catalano, R. Gennaro, N. Howgrave-Graham, P. Q. Nguyen, Paillier’s cryptosystem revisited, in ACM Conference on Computer and Communications Security (2001), pp. 206–214
13.
R. Cramer, R. Gennaro, B. Schoenmakers, A secure and optimally efficient multi-authority election scheme, in EUROCRYPT (1997), pp. 103–118
14.
J. Camenisch, A. Kiayias, M. Yung, On the portability of generalized Schnorr proofs, in EUROCRYPT 2009 (2009), pp. 425–442
15.
R. Cleve, Limits on the security of coin flips when half the processors are faulty (extended abstract), in STOC (1986), pp. 364–369
16.
C. Cocks, Split generation of RSA parameters with multiple participants, in Proceedings of 6th IMA Conference on Cryptography and Coding. LNCS 1355 (1997), pp. 200–212
17.
D. Coppersmith, Small exponents to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptol. 10, 233–260 (1997)CrossRefMATH
18.
D. Chaum, T. P. Pedersen, Wallet databases with observers, in CRYPTO (1992), pp. 89–105
19.
N. DeBruijn, On the number of uncanceled elements in the sieve of eratosthenes, in Proc. Neder. Akad. Wetensh. (53), pp. 803–812. (Reviewed in LeVeque Reviews in Number Theory, 4, N-28, page 221)
20.
Y. G. Desmedt, Threshold cryptography. Eur. Trans. Telecommun. 5(4), 449–457 (1994)CrossRef
21.
I. Damgård, E. Fujisaki, A statistically-hiding integer commitment scheme based on groups with hidden order, in ASIACRYPT (2002), pp. 125–142
22.
23.
I. Damgård, M. Jurik, A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system, in Public Key Cryptography (2001), pp. 119–136
24.
I. Damgård, M. Jurik, Client/server tradeoffs for online elections, in Public Key Cryptography (2002), pp. 125–140
25.
I. Damgård, G. L. Mikkelsen, Efficient, robust and constant-round distributed RSA key generation, in TCC (2010), pp. 183–200
26.
I. Damgård, J. B. Nielsen, Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor, in CRYPTO (2002), pp. 581–596
27.
I. Damgård, J. B. Nielsen, Universally composable efficient multiparty computation from threshold homomorphic encryption, in CRYPTO (2003), pp. 247–264
28.
I. Damgård, V. Pastro, N. P. Smart, S. Zakarias, Multiparty computation from somewhat homomorphic encryption, in CRYPTO (2012), pp. 643–662
29.
30.
T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Info. Theory, IT 31, 469–472 (1985)
31.
32.
Y. Frankel, P. D. Mackenzie, M. Yung, Robust efficient distributed RSA-key generation, in STOC 98 (ACM Press, 1998), pp. 663–672
33.
E. Fujisaki, T. Okamoto, Statistical zero knowledge protocols to prove modular polynomial relations, in CRYPTO (1997), pp. 16–30
34.
P. A. Fouque, G. Poupard, J. Stern, Decryption in the context of voting or lotteries, in Financial Crypto’00 (Springer, 2000)
35.
A. Fiat, A. Shamir, How to prove yourself: practical solutions to identification and signature problems, in CRYPTO (1986), pp. 186–194
36.
N. Gilboa, Two party RSA key generation, in CRYPTO (1999), pp. 116–129
37.
R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin, Robust threshold DSS signatures. Inf. Comput. 164(1), 54–84 (2001)MathSciNetCrossRefMATH
38.
R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin, Secure distributed key generation for discrete-log based cryptosystems. J. Cryptol. 20(1), 51–83 (2007)
39.
R. Gennaro, H. Krawczyk, T. Rabin, Robust and efficient sharing of RSA functions. J. Cryptol. 13(2), 273–300 (2000)
40.
41.
C. Hazay, Oblivious polynomial evaluation and secure set-intersection from algebraic PRFS, in TCC (2015), pp. 90–120
42.
C. Hazay, Y. Lindell, Efficient oblivious polynomial evaluation with simulation-based security. IACR Cryptol. ePrint Arch. 2009, 459 (2009)
43.
C. Hazay, Y. Lindell, Efficient Secure Two-Party Protocols—Techniques and Constructions (Springer, 2010)
44.
S. Jarecki, X. Liu, Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection, in TCC (2009), pp. 577–594
45.
S. Jarecki, V. Shmatikov, Efficient two-party secure computation on committed inputs, in EUROCRYPT (2007), pp. 97–114
46.
N. Koblitz, A. J. Menezes, Y.-H. Wu, R. J. Zuccherato. Algebraic Aspects of Cryptography (Springer, New York, 1998)
47.
N. Koblitz, A Course in Number Theory and Cryptography (Springer, New York, 1987)
48.
Y. Lindell, Fast cut-and-choose based protocols for malicious and covert adversaries, in CRYPTO (2013), pp. 1–17
49.
H. Lipmaa, On diophantine complexity and statistical zero-knowledge arguments, in ASIACRYPT (2003), pp. 398–415
50.
Y. Lindell, B. Pinkas, Secure two-party computation via cut-and-choose oblivious transfer, in TCC (2011), pp. 329–346
51.
52.
53.
54.
T. Nishide, K. Sakurai. Distributed Paillier cryptosystem without trusted dealer, in WISA (2010), pp. 44–60
55.
P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, in EUROCRYPT (1999), pp. 223–238
56.
G. Poupard, J. Stern, Generation of shared RSA keys by two parties, in Asiacrypt 98 (Springer, 1998), pp. 11–24
57.
58.
M. O. Rabin, How to Exchange Secrets with Oblivious Transfer. Techincal Report TR-81, Aiken Computation Lab, Harvard University (1981)
59.
T. Rabin, A simplified approach to threshold and proactive RSA, in CRYPTO (1998), pp. 89–104
60.
C. P. Schnorr, Efficient signature generation by smart cards. J. Cryptol. 4, 161–174 (1991)CrossRefMATH
61.
Standards for efficient cryptography group, sec 2: recommended elliptic curve domain parameters. SECG2 (2000)
62.
V. Shoup, Practical threshold signatures, in EUROCRYPT (2000), pp. 207–220
63.
J. H. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves. Graduate Texts in Mathematics (Springer, 1994)
64.
J. H. Silverman, The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics (Springer, 2009)
Metadaten
Titel
Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting
verfasst von
Carmit Hazay
Gert Læssøe Mikkelsen
Tal Rabin
Tomas Toft
Angelo Agatino Nicolosi
Publikationsdatum
05.02.2018
Verlag
Springer US
Erschienen in
Journal of Cryptology / Ausgabe 2/2019
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-017-9275-7

Weitere Artikel der Ausgabe 2/2019

Journal of Cryptology 2/2019 Zur Ausgabe

OriginalPaper

From Physical to Stochastic Modeling of a TERO-Based TRNG

OriginalPaper

Non-black-box Simulation in the Fully Concurrent Setting, Revisited

OriginalPaper

Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials

OriginalPaper

Automated Analysis of Cryptographic Assumptions in Generic Group Models

OriginalPaper

(Efficient) Universally Composable Oblivious Transfer Using a Minimal Number of Stateless Tokens

OriginalPaper

Cryptanalysis of the CLT13 Multilinear Map