Top

Published in:

2021 | OriginalPaper | Chapter

Compact Zero-Knowledge Proofs for Threshold ECDSA with Trustless Setup

Authors : Tsz Hon Yuen, Handong Cui, Xiang Xie

Published in: Public-Key Cryptography – PKC 2021

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Threshold ECDSA signatures provide a higher level of security to a crypto wallet since it requires more than t parties out of n parties to sign a transaction. The state-of-the-art bandwidth efficient threshold ECDSA used the additive homomorphic Castagnos and Laguillaumie (CL) encryption based on an unknown order group G, together with a number of zero-knowledge proofs in G. In this paper, we propose compact zero-knowledge proofs for threshold ECDSA to lower the communication bandwidth, as well as the computation cost. The proposed zero-knowledge proofs include the discrete-logarithm relation in G and the well-formedness of a CL ciphertext.

When applied to two-party ECDSA, we can lower the bandwidth of the key generation algorithm by 47%, and the running time for the key generation and signing algorithms are boosted by about 35% and 104% respectively. When applied to threshold ECDSA, our first scheme is more optimized for the key generation algorithm (about 70% lower bandwidth and 85% faster computation in key generation, at a cost of 20% larger bandwidth in signing), while our second scheme has an all-rounded performance improvement (about 60% lower bandwidth, 46% faster computation in key generation without additional cost in signing).

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 Two-Party Adaptor Signatures from Identification Schemes

next chapter Universal Proxy Re-Encryption

Available only for authorised users

This special requirement on e is needed since computing square roots in class groups of quadratic fields is easy [4]. The assumptions used in this paper do not require such a special arrangement.

Since it is easy to compute \(\log _g w\) if \(g \in F\), it is impossible to construct a ZK proof for \(\mathcal {R}\) if \(g \in F\). Hence, we restrict that \(g \in G \setminus F\).

These are the most popular types of threshold signatures in Bitcoin’s P2SH transactions as shown in https://txstats.com/dashboard/db/p2sh-repartition-by-type?orgId=1. Hence we use these 3 settings for comparison in this paper.

The random encoding for DL-easy subgroup is necessary, since the adversary may obtain some \(g' = \sigma (\pi (a_1, b_1))\) and \(f' = \sigma (\pi (0, b_2))\) from \(\mathcal {O}_1\). The adversary can obtain \(g' \cdot f'\) or \((g')^2/ f'\) from \(\mathcal {O}_2\). The encodings \(b_1\) and \(b_2\) ensure that the value in the DL-easy subgroup is always correct even when the computation involves elements in \(\mathbb {G}_1\).

Non-trivial order hardness is similar to the low order assumption in [5], except that their assumption did not rule out the trivial attack that \(f^q = 1\).

Since \(g = g_1\), if \(Q_1\) is computed from \(f, g_i\) and \(w = g^x = g_1^x\), we can write \(Q_1 = f^{\gamma } \prod _{i=1}^m g_i^{\alpha _i}\).

Boneh, D., Bünz, B., Fisch, B.: Batching techniques for accumulators with applications to IOPs and stateless blockchains. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 561–586. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_20CrossRef

Brown, D.R.L.: Generic groups, collision resistance, and ECDSA. Des. Codes Cryptogr. 35(1), 119–152 (2005)MathSciNetCrossRef

Camenisch, J., Kiayias, A., Yung, M.: On the portability of generalized schnorr proofs. In: Joux, A. (ed.): EUROCRYPT 2009. Lecture Notes in Computer Science, vol. 5479, pp. 425–442. Springer (2009)

Castagnos, G., Catalano, D., Laguillaumie, F., Savasta, F., Tucker, I.: Two-party ECDSA from hash proof systems and efficient instantiations. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 191–221. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_7CrossRef

Castagnos, G., Catalano, D., Laguillaumie, F., Savasta, F., Tucker, I.: Bandwidth-efficient threshold EC-DSA. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. Lecture Notes in Computer Science, vol. 12111, pp. 266–296. Springer (2020)

Castagnos, G., Laguillaumie, F.: On the security of cryptosystems with quadratic decryption: the nicest cryptanalysis. In: Joux, A. (ed.): EUROCRYPT 2009. Lecture Notes in Computer Science, vol. 5479, pp. 260–277. Springer (2009)

Castagnos, G., Laguillaumie, F.: Linearly homomorphic encryption from DDH. In: Nyberg, K. (ed.) CT-RSA 2015. Lecture Notes in Computer Science, vol. 9048, pp. 487–505. Springer (2015)

Damgård, I., Koprowski, M.: Generic lower bounds for root extraction and signature schemes in general groups. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 256–271. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_17CrossRefMATH

Doerner, J., Kondi, Y., Lee, E., Shelat, A.: Secure two-party threshold ECDSA from ECDSA assumptions. In: IEEE SP 2018, pp. 980–997. IEEE Computer Society (2018)

10.

Doerner, J., Kondi, Y., Lee, E., Shelat, A.: Threshold ECDSA from ECDSA assumptions: the multiparty case. In: IEEE SP 2019, pp. 1051–1066. IEEE (2019)

11.

Gennaro, R., Goldfeder, S.: Fast multiparty threshold ECDSA with fast trustless setup. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) CCS 2018, pp. 1179–1194. ACM (2018)

12.

Gennaro, R., Goldfeder, S.: One round threshold ecdsa with identifiable abort. Cryptology ePrint Archive, Report 2020/540 (2020). https://eprint.iacr.org/2020/540

13.

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

14.

Lindell, Y., Nof, A.: Fast secure multiparty ECDSA with practical distributed key generation and applications to cryptocurrency custody. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) CCS 2018, pp. 1837–1854. ACM (2018)

15.

Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_18CrossRef

Title: Compact Zero-Knowledge Proofs for Threshold ECDSA with Trustless Setup
Authors: Tsz Hon Yuen
Handong Cui
Xiang Xie
Publisher: Springer International Publishing
Book: Public-Key Cryptography – PKC 2021
Print ISBN: 978-3-030-75244-6

Electronic ISBN: 978-3-030-75245-3

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-75245-3_18

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner