Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Two-Party ECDSA from Hash Proof Systems and Efficient Instantiations

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 11694))

Included in the following conference series:

  • 2990Accesses

Abstract

ECDSA is a widely adopted digital signature standard. Unfortunately, efficient distributed variants of this primitive are notoriously hard to achieve and known solutions often require expensive zero knowledge proofs to deal with malicious adversaries. For the two party case, Lindell [Lin17] recently managed to get an efficient solution which, to achieve simulation-based security, relies on an interactive, non standard, assumption on Paillier’s cryptosystem. In this paper we generalize Lindell’s solution using hash proof systems. The main advantage of our generic method is that it results in a simulation-based security proof without resorting to non-standard interactive assumptions.

Moving to concrete constructions, we show how to instantiate our framework using class groups of imaginary quadratic fields. Our implementations show that the practical impact of dropping such interactive assumptions is minimal. Indeed, while for 128-bit security our scheme is marginally slower than Lindell’s, for 256-bit security it turns out to be better both in key generation and signing time. Moreover, in terms of communication cost, our implementation significantly reduces both the number of rounds and the transmitted bits without exception.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 16015
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 20019
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

Notes

  1. 1.

    From now on we will focus on the elliptic curve variant of the scheme, as this is the most commonly used scheme in applications. We stress that our reasoning apply to the basic DSA case as well.

  2. 2.

    We note here that the very recent two party protocol of [DKLs18] is very fast in signing time and only relies on the ECDSA assumption. However its bandwidth consumption is much higher than [Lin17].

  3. 3.

    \(L[\alpha ,c]\) denotes\(L_{\alpha ,c}(x) := \exp (c\log (x)^\alpha \log (\log (x))^{1-\alpha })\).

  4. 4.

    For Paillier’s scheme, used in [Lin17], this is not an issue: every ciphertext is valid.

  5. 5.

    We also re-implemented Lindell’s protocol to ensure a fair comparison.

References

  1. Boneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part I. LNCS, vol. 10991, pp. 757–788. Springer, Cham (2018).https://doi.org/10.1007/978-3-319-96884-1_25

    Chapter  Google Scholar 

  2. Boneh, D., Bünz, B., Fisch, B.: A survey of two verifiable delay functions. Cryptology ePrint Archive, Report 2018/712 (2018).https://eprint.iacr.org/2018/712

  3. Buchmann, J., Hamdy, S.: A survey on IQ cryptography. In: Proceedings of Public Key Cryptography and Computational Number Theory (2001)

    Google Scholar 

  4. Bauer, M.L., Hamdy, S.: On class group computations using the number field sieve. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 311–325. Springer, Heidelberg (2003).https://doi.org/10.1007/978-3-540-40061-5_19

    Chapter  Google Scholar 

  5. Biasse, J.-F., Jacobson, M.J., Silvester, A.K.: Security estimates for quadratic field based cryptosystems. In: Steinfeld, R., Hawkes, P. (eds.) ACISP 2010. LNCS, vol. 6168, pp. 233–247. Springer, Heidelberg (2010).https://doi.org/10.1007/978-3-642-14081-5_15

    Chapter  Google Scholar 

  6. Boyd, C.: Digital multisignature. In: Baker, H., Piper, F. (eds.) Cryptography and Coding, pp. 241–246. Clarendon Press (1989)

    Google Scholar 

  7. Castagnos, G., Catalano, D., Laguillaumie, F., Savasta, F., Tucker, I.: Two-party ECDSA from hash proof systems and efficient instantiations. Cryptology ePrint Archive, Report 2019/503 (2019).https://eprint.iacr.org/2019/503

  8. Croft, R.A., Harris, S.P.: Public-key cryptography and reusable shared secrets. In: Baker, H., Piper, F. (eds.) Cryptography and Coding, pp. 189–201. Clarendon Press, Oxford (1989)

    Google Scholar 

  9. Chia.https://www.chia.net/

  10. Castagnos, G., Imbert, L., Laguillaumie, F.: Encryption switching protocols revisited: switching modulop. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 255–287. Springer, Cham (2017).https://doi.org/10.1007/978-3-319-63688-7_9

    Chapter  Google Scholar 

  11. Camenisch, J., Kiayias, A., Yung, M.: On the portability of generalized schnorr proofs. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 425–442. Springer, Heidelberg (2009).https://doi.org/10.1007/978-3-642-01001-9_25

    Chapter  Google Scholar 

  12. Castagnos, G., Laguillaumie, F.: On the security of cryptosystems with quadratic decryption: the nicest cryptanalysis. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 260–277. Springer, Heidelberg (2009).https://doi.org/10.1007/978-3-642-01001-9_15

    Chapter  Google Scholar 

  13. Castagnos, G., Laguillaumie, F.: Linearly homomorphic encryption from\(\sf DDH\). In: Nyberg, K. (ed.) CT-RSA 2015. LNCS, vol. 9048, pp. 487–505. Springer, Cham (2015).https://doi.org/10.1007/978-3-319-16715-2_26

    Chapter  Google Scholar 

  14. Castagnos, G., Laguillaumie, F., Tucker, I.: Practical fully secure unrestricted inner product functional encryption modulop. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part II. LNCS, vol. 11273, pp. 733–764. Springer, Cham (2018).https://doi.org/10.1007/978-3-030-03329-3_25

    Chapter  Google Scholar 

  15. Cohen, H.: A Course in Computational Algebraic Number Theory. Springer, Heidelberg (2000)

    Google Scholar 

  16. Cramer, R., Shoup, V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 13–25. Springer, Heidelberg (1998).https://doi.org/10.1007/BFb0055717

    Chapter  Google Scholar 

  17. Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45–64. Springer, Heidelberg (2002).https://doi.org/10.1007/3-540-46035-7_4

    Chapter  Google Scholar 

  18. Camenisch, J., Shoup, V.: Practical verifiable encryption and decryption of discrete logarithms. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 126–144. Springer, Heidelberg (2003).https://doi.org/10.1007/978-3-540-45146-4_8

    Chapter  Google Scholar 

  19. 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).https://doi.org/10.1007/3-540-48184-2_8

    Chapter  Google Scholar 

  20. Desmedt, Y., Frankel, Y.: Threshold cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307–315. Springer, New York (1990).https://doi.org/10.1007/0-387-34805-0_28

    Chapter  Google Scholar 

  21. Damgård, I., Fujisaki, E.: A statistically-hiding integer commitment scheme based on groups with hidden order. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 125–142. Springer, Heidelberg (2002).https://doi.org/10.1007/3-540-36178-2_8

    Chapter  Google Scholar 

  22. Doerner, J., Kondi, Y., Lee, E., Shelat, A.: Secure two-party threshold ECDSA from ECDSA assumptions. In: 2018 IEEE Symposium on Security and Privacy, pp. 980–997. IEEE Computer Society Press (2018)

    Google Scholar 

  23. Doerner, J., Kondi, Y., Lee, E., Shelat, A.: Threshold ECDSA from ECDSA assumptions: the multiparty case. In: 2019 IEEE Symposium on Security and Privacy, pp. 980–997. IEEE Computer Society Press (2019)

    Google Scholar 

  24. Gennaro, R., Goldfeder, S.: Fast multiparty threshold ECDSA with fast trustless setup. In: ACM CCS 2018. ACM Press (2018)

    Google Scholar 

  25. Gennaro, R., Goldfeder, S., Narayanan, A.: Threshold-optimal DSA/ECDSA signatures and an application to bitcoin wallet security. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 156–174. Springer, Cham (2016).https://doi.org/10.1007/978-3-319-39555-5_9

    Chapter MATH  Google Scholar 

  26. 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).https://doi.org/10.1007/3-540-68339-9_31

    Chapter  Google Scholar 

  27. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput.18, 186–208 (1989)

    Article MathSciNet  Google Scholar 

  28. Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001)

    Book  Google Scholar 

  29. Girault, M., Poupard, G., Stern, J.: On the fly authentication and signature schemes based on groups of unknown order. J. Cryptol.19, 463–487 (2006)

    Article MathSciNet  Google Scholar 

  30. Hazay, C., Lindell, Y.: Efficient Secure Two-Party Protocols: Techniques and Constructions, 1st edn. Springer, Heidelberg (2010).https://doi.org/10.1007/978-3-642-14303-8

    Book MATH  Google Scholar 

  31. Hemenway, B., Ostrovsky, R.: Lossy trapdoor functions from smooth homomorphic hash proof systems. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 16, no. 127 (2009). 01

    Google Scholar 

  32. Imbert, L., Jacobson Jr., M.J., Schmidt, A.: Fast ideal cubing in imaginary quadratic number and function fields. Adv. Math. Commun.4, 237–260 (2010)

    Article MathSciNet  Google Scholar 

  33. Jacobson Jr., M.J.: Computing discrete logarithms in quadratic orders. J. Cryptol.13, 473–492 (2000).https://doi.org/10.1007/s001450010013. Springer, Heidelberg

    Article MathSciNet MATH  Google Scholar 

  34. Lindell, Y.: How to simulate it - a tutorial on the simulation proof technique. Cryptology ePrint Archive, Report 2016/046 (2016).http://eprint.iacr.org/2016/046

  35. Lindell, Y.: Fast secure two-party ECDSA signing. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part II. LNCS, vol. 10402, pp. 613–644. Springer, Cham (2017).https://doi.org/10.1007/978-3-319-63715-0_21

    Chapter  Google Scholar 

  36. Lindell, Y., Nof, A.: Fast secure multiparty ECDSA with practical distributed key generation and applications to cryptocurrency custody. In: ACM CCS 2018, pp. 1837–1854. ACM Press, October 2018

    Google Scholar 

  37. MacKenzie, P.D., Reiter, M.K.: Two-party generation of DSA signatures. Int. J. Inf. Secur.2, 218–239 (2004).https://doi.org/10.1007/s10207-004-0041-0

    Article MATH  Google Scholar 

  38. PARI Group, University Bordeaux. PARI/GP version 2.11.1 (2018).http://pari.math.u-bordeaux.fr/

  39. Schnorr, C.-P.: Efficient signature generation by smart cards. J. Cryptol.4, 161–174 (1991)

    Article  Google Scholar 

  40. Sepior.http://www.sepior.com

  41. I. D. P. Services.https://security.intuit.com/

  42. 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).https://doi.org/10.1007/BFb0054113

    Chapter  Google Scholar 

  43. Shoup, V.: Practical threshold signatures. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 207–220. Springer, Heidelberg (2000).https://doi.org/10.1007/3-540-45539-6_15

    Chapter  Google Scholar 

  44. Terelius, B., Wikström, D.: Efficiency limitations of\(\sum \)-protocols for group homomorphisms revisited. In: Visconti, I., De Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 461–476. Springer, Heidelberg (2012).https://doi.org/10.1007/978-3-642-32928-9_26

    Chapter MATH  Google Scholar 

  45. Unboundtech.https://www.unboundtech.com/

  46. Vanstone, S.: Responses to NIST’s proposal. Commun. ACM35, 50–52 (1992). Communicated by John Anderson

    Article  Google Scholar 

  47. 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_13

    Chapter  Google Scholar 

Download references

Acknowledgements

The authors would like to thank Benoît Libert for fruitful discussions. This work was supported by the Universita’ degli Studi di Catania, “Piano della Ricerca 2016/2018 Linea di intervento 2”, and the French ANR ALAMBIC project (ANR-16-CE39-0006).

Author information

Authors and Affiliations

  1. Université de Bordeaux, Inria, CNRS, IMB UMR 5251, F-33405, Talence, France

    Guilhem Castagnos

  2. Università di Catania, Catania, Italy

    Dario Catalano & Federico Savasta

  3. Univ Lyon, EnsL, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, France

    Fabien Laguillaumie & Ida Tucker

  4. Scuola Superiore di Catania, Catania, Italy

    Federico Savasta

Authors
  1. Guilhem Castagnos

    You can also search for this author inPubMed Google Scholar

  2. Dario Catalano

    You can also search for this author inPubMed Google Scholar

  3. Fabien Laguillaumie

    You can also search for this author inPubMed Google Scholar

  4. Federico Savasta

    You can also search for this author inPubMed Google Scholar

  5. Ida Tucker

    You can also search for this author inPubMed Google Scholar

Corresponding authors

Correspondence toGuilhem Castagnos orDario Catalano.

Editor information

Editors and Affiliations

  1. Georgia Institute of Technology, Atlanta, GA, USA

    Alexandra Boldyreva

  2. University of California at San Diego, La Jolla, CA, USA

    Daniele Micciancio

Rights and permissions

Copyright information

© 2019 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Castagnos, G., Catalano, D., Laguillaumie, F., Savasta, F., Tucker, I. (2019). Two-Party ECDSA from Hash Proof Systems and Efficient Instantiations. In: Boldyreva, A., Micciancio, D. (eds) Advances in Cryptology – CRYPTO 2019. CRYPTO 2019. Lecture Notes in Computer Science(), vol 11694. Springer, Cham. https://doi.org/10.1007/978-3-030-26954-8_7

Download citation

Publish with us

Societies and partnerships

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 16015
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 20019
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp