Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Secure Computation Based on Leaky Correlations: High Resilience Setting Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Fast Secure Two-Party ECDSA Signing

Author : Yehuda Lindell

Published in: Advances in Cryptology – CRYPTO 2017

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

ECDSA is a standard digital signature schemes that is widely used in TLS, Bitcoin and elsewhere. Unlike other schemes like RSA, Schnorr signatures and more, it is particularly hard to construct efficient threshold signature protocols for ECDSA (and DSA). As a result, the best-known protocols today for secure distributed ECDSA require running heavy zero-knowledge proofs and computing many large-modulus exponentiations for every signing operation. In this paper, we consider the specific case of two parties (and thus no honest majority) and construct a protocol that is approximately two orders of magnitude faster than the previous best. Concretely, our protocol achieves good performance, with a single signing operation for curve P-256 taking approximately 37 ms between two standard machine types in Azure (utilizing a single core only). Our protocol is proven secure under standard assumptions using a game-based definition. In addition, we prove security by simulation under a plausible yet non-standard assumption regarding Paillier.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs
next chapter Proving Resistance Against Invariant Attacks: How to Choose the Round Constants
Appendix
Available only for authorised users
Footnotes
1
We base this estimate on an OpenSSL speed test that puts the speed of the entire ECDSA signing operation for P-256 (which consists of one EC multiplication and more) at more than 10 times faster than a single RSA2048 private-key exponentiation. Note that for P-521 and RSA4096 the gap is even larger with the entire ECDSA signing operation being more than 30 times faster than a single RSA4096 private-key exponentiation.
 
2
As before, this is true in the \(\mathcal{F}_\mathsf{zk},\mathcal{F}_\mathsf{com\text {-}zk}\)-hybrid model; by using UC-secure protocols for \(\mathcal{F}_\mathsf{zk},\mathcal{F}_\mathsf{com\text {-}zk}\) the result is computationally indistinguishable.
 
3
This only holds as long as the value encrypted is between 0 and \(q^3+q^2\). Now, since \(x_1,r\in {\mathbb {Z}}_q\) as guaranteed in the range-ZK phase, and V checks that \(q^2<z<q^3+q^2\), it follows that \(z-r-e\cdot x_1\) is in the range between 0 and \(q^3+q^2\), as required.
 
Literature
1.
Blazy, O., Chevalier, C., Pointcheval, D., Vergnaud, D.: Analysis and improvement of Lindell’s UC-Secure commitment schemes. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 534–551. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38980-1_​34 CrossRef
2.
3.
Boyd, C.: Digital multisignatures. In: Cryptography and Coding, pp. 241–246 (1986)
4.
Brickell, E.F., Chaum, D., Damgård, I.B., Graaf, J.: Gradual and verifiable release of a secret (Extended Abstract). In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 156–166. Springer, Heidelberg (1988). doi:10.​1007/​3-540-48184-2_​11
5.
6.
7.
Croft, R.A., Harris, S.P.: Public-key cryptography and reusable shared secrets. In: Cryptography and Coding, pp. 189–201 (1989)
8.
Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001). doi:10.​1007/​3-540-44586-2_​9 CrossRef
9.
Desmedt, Y.: Society and group oriented cryptography: a new concept. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 120–127. Springer, Heidelberg (1988). doi:10.​1007/​3-540-48184-2_​8
10.
11.
Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). doi:10.​1007/​3-540-47721-7_​12
12.
Fujisaki, E.: Improving practical UC-secure commitments based on the DDH assumption. In: Zikas, V., Prisco, R. (eds.) SCN 2016. LNCS, vol. 9841, pp. 257–272. Springer, Cham (2016). doi:10.​1007/​978-3-319-44618-9_​14
13.
Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Robust threshold DSS signatures. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 354–371. Springer, Heidelberg (1996). doi:10.​1007/​3-540-68339-9_​31
14.
Gennaro, R., Goldfeder, S., Narayanan, A.: Threshold-optimal DSA/ECDSA signatures and an application to bitcoin wallet security. ACNS 2016, 156–174 (2016)MathSciNetMATH
15.
Goldreich, O.: Foundations of Cryptography: Volume 2 - Basic Applications. Cambridge University Press, New York (2004)CrossRefMATH
16.
Hazay, C., Lindell, Y.: Protocols, Efficient Secure Two-Party: Techniques and Constructions. Springer, Heidelberg (2010)CrossRefMATH
17.
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). doi:10.​1007/​978-3-642-27954-6_​20 CrossRef
18.
19.
20.
MacKenzie, P.D., Reiter, M.K.: Two-party generation of DSA signatures. Int. J. Inf. Secur. 2, 218–239 (2004). An extended abstract appeared at CRYPTO 2001CrossRefMATH
21.
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). doi:10.​1007/​3-540-48910-X_​16
22.
23.
24.
Shoup, V., Gennaro, R.: Securing threshold cryptosystems against chosen ciphertext attack. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 1–16. Springer, Heidelberg (1998). doi:10.​1007/​BFb0054113
25.
26.
27.
Metadata
Title
Fast Secure Two-Party ECDSA Signing
Author
Yehuda Lindell
Copyright Year
2017
Book
Advances in Cryptology – CRYPTO 2017

Print ISBN: 978-3-319-63714-3

Electronic ISBN: 978-3-319-63715-0

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-63715-0_21

Premium Partner

    Image Credits