Efficient online-friendly two-party ECDSA signature

Haiyang Xue; Man Ho Au; Xiang Xie; Tsz Hon Yuen; Handong Cui

doi:10.1145/3460120.3484803

Efficient online-friendly two-party ECDSA signature

Haiyang Xue
, Man Ho Au
, Xiang Xie
, Tsz Hon Yuen
, Handong Cui

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

43 Citations (Scopus)

Abstract

Two-party ECDSA signatures have received much attention due to their widespread deployment in cryptocurrencies. Depending on whether or not the message is required, we could divide two-party signing into two different phases, namely, offline and online. Ideally, the online phase should be made as lightweight as possible. At the same time, the cost of the offline phase should remain similar to that of a normal signature generation. However, the existing two-party protocols of ECDSA are not optimal: either their online phase requires decryption of a ciphertext, or their offline phase needs at least two executions of multiplicative-to-additive conversion which dominates the overall complexity. This paper proposes an online-friendly two-party ECDSA with a lightweight online phase and a single multiplicative-to-additive function in the offline phase. It is constructed by a novel design of a re-sharing of the secret key and a linear sharing of the nonce. Our scheme significantly improves previous protocols based on either oblivious transfer or homomorphic encryption. We implement our scheme and show that it outperforms prior online-friendly schemes (i.e., those have lightweight online cost) by a factor of roughly 2 to 9 in both communication and computation. Furthermore, our two-party scheme could be easily extended to the 2-out-of-n threshold ECDSA.

Original language	English
Title of host publication	Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security
Editors	Hyoungshick Kim, Jin B. Hong
Place of Publication	New York NY USA
Publisher	Association for Computing Machinery (ACM)
Pages	558-573
Number of pages	16
ISBN (Electronic)	9781450384544
DOIs	https://doi.org/10.1145/3460120.3484803
Publication status	Published - 2021
Externally published	Yes
Event	ACM Conference on Computer and Communications Security 2021 - Online, Korea, South Duration: 15 Nov 2021 → 19 Nov 2021 Conference number: 27th https://dl.acm.org/doi/proceedings/10.1145/3460120 (Proceedings)

Publication series

Name	Proceedings of the ACM Conference on Computer and Communications Security
Publisher	Association for Computing Machinery (ACM)
ISSN (Print)	1543-7221

Conference

Conference	ACM Conference on Computer and Communications Security 2021
Abbreviated title	CCS 2021
Country/Territory	Korea, South
Period	15/11/21 → 19/11/21
Internet address	https://dl.acm.org/doi/proceedings/10.1145/3460120 (Proceedings)

Keywords

blockchain
ECDSA
threshold signature
two-party signature
zero-knowledge proof

Access to Document

10.1145/3460120.3484803

Cite this

Xue, H., Au, M. H., Xie, X., Yuen, T. H., & Cui, H. (2021). Efficient online-friendly two-party ECDSA signature. In H. Kim, & J. B. Hong (Eds.), Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (pp. 558-573). (Proceedings of the ACM Conference on Computer and Communications Security). Association for Computing Machinery (ACM). https://doi.org/10.1145/3460120.3484803

Xue, Haiyang ; Au, Man Ho ; Xie, Xiang et al. / Efficient online-friendly two-party ECDSA signature. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. editor / Hyoungshick Kim ; Jin B. Hong. New York NY USA : Association for Computing Machinery (ACM), 2021. pp. 558-573 (Proceedings of the ACM Conference on Computer and Communications Security).

@inproceedings{512cb3dc8b364b12a043f248463f4d06,

title = "Efficient online-friendly two-party ECDSA signature",

abstract = "Two-party ECDSA signatures have received much attention due to their widespread deployment in cryptocurrencies. Depending on whether or not the message is required, we could divide two-party signing into two different phases, namely, offline and online. Ideally, the online phase should be made as lightweight as possible. At the same time, the cost of the offline phase should remain similar to that of a normal signature generation. However, the existing two-party protocols of ECDSA are not optimal: either their online phase requires decryption of a ciphertext, or their offline phase needs at least two executions of multiplicative-to-additive conversion which dominates the overall complexity. This paper proposes an online-friendly two-party ECDSA with a lightweight online phase and a single multiplicative-to-additive function in the offline phase. It is constructed by a novel design of a re-sharing of the secret key and a linear sharing of the nonce. Our scheme significantly improves previous protocols based on either oblivious transfer or homomorphic encryption. We implement our scheme and show that it outperforms prior online-friendly schemes (i.e., those have lightweight online cost) by a factor of roughly 2 to 9 in both communication and computation. Furthermore, our two-party scheme could be easily extended to the 2-out-of-n threshold ECDSA.",

keywords = "blockchain, ECDSA, threshold signature, two-party signature, zero-knowledge proof",

author = "Haiyang Xue and Au, \{Man Ho\} and Xiang Xie and Yuen, \{Tsz Hon\} and Handong Cui",

note = "Funding Information: We would like to thank Xuyang Song and Xueli Wang for their help in the experiments. Haiyang Xue is supported by the National Natural Science Foundation of China (No. 62172412), the National Key Research and Development Program of China (No. 2020YFB1807502). Man Ho Au is supported by the National Natural Science Foundation of China (No. 61972332), the Research Grant Council of Hong Kong (GRF Project 15211120). Publisher Copyright: {\textcopyright} 2021 ACM.; ACM Conference on Computer and Communications Security 2021, CCS 2021 ; Conference date: 15-11-2021 Through 19-11-2021",

year = "2021",

doi = "10.1145/3460120.3484803",

language = "English",

series = "Proceedings of the ACM Conference on Computer and Communications Security",

publisher = "Association for Computing Machinery (ACM)",

pages = "558--573",

editor = "Hyoungshick Kim and \{B. Hong\}, Jin",

booktitle = "Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security",

address = "United States of America",

url = "https://dl.acm.org/doi/proceedings/10.1145/3460120",

}

Xue, H, Au, MH, Xie, X, Yuen, TH & Cui, H 2021, Efficient online-friendly two-party ECDSA signature. in H Kim & J B. Hong (eds), Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. Proceedings of the ACM Conference on Computer and Communications Security, Association for Computing Machinery (ACM), New York NY USA, pp. 558-573, ACM Conference on Computer and Communications Security 2021, Korea, South, 15/11/21. https://doi.org/10.1145/3460120.3484803

Efficient online-friendly two-party ECDSA signature. / Xue, Haiyang; Au, Man Ho; Xie, Xiang et al.
Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. ed. / Hyoungshick Kim; Jin B. Hong. New York NY USA: Association for Computing Machinery (ACM), 2021. p. 558-573 (Proceedings of the ACM Conference on Computer and Communications Security).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Efficient online-friendly two-party ECDSA signature

AU - Xue, Haiyang

AU - Au, Man Ho

AU - Xie, Xiang

AU - Yuen, Tsz Hon

AU - Cui, Handong

N1 - Conference code: 27th

PY - 2021

Y1 - 2021

N2 - Two-party ECDSA signatures have received much attention due to their widespread deployment in cryptocurrencies. Depending on whether or not the message is required, we could divide two-party signing into two different phases, namely, offline and online. Ideally, the online phase should be made as lightweight as possible. At the same time, the cost of the offline phase should remain similar to that of a normal signature generation. However, the existing two-party protocols of ECDSA are not optimal: either their online phase requires decryption of a ciphertext, or their offline phase needs at least two executions of multiplicative-to-additive conversion which dominates the overall complexity. This paper proposes an online-friendly two-party ECDSA with a lightweight online phase and a single multiplicative-to-additive function in the offline phase. It is constructed by a novel design of a re-sharing of the secret key and a linear sharing of the nonce. Our scheme significantly improves previous protocols based on either oblivious transfer or homomorphic encryption. We implement our scheme and show that it outperforms prior online-friendly schemes (i.e., those have lightweight online cost) by a factor of roughly 2 to 9 in both communication and computation. Furthermore, our two-party scheme could be easily extended to the 2-out-of-n threshold ECDSA.

AB - Two-party ECDSA signatures have received much attention due to their widespread deployment in cryptocurrencies. Depending on whether or not the message is required, we could divide two-party signing into two different phases, namely, offline and online. Ideally, the online phase should be made as lightweight as possible. At the same time, the cost of the offline phase should remain similar to that of a normal signature generation. However, the existing two-party protocols of ECDSA are not optimal: either their online phase requires decryption of a ciphertext, or their offline phase needs at least two executions of multiplicative-to-additive conversion which dominates the overall complexity. This paper proposes an online-friendly two-party ECDSA with a lightweight online phase and a single multiplicative-to-additive function in the offline phase. It is constructed by a novel design of a re-sharing of the secret key and a linear sharing of the nonce. Our scheme significantly improves previous protocols based on either oblivious transfer or homomorphic encryption. We implement our scheme and show that it outperforms prior online-friendly schemes (i.e., those have lightweight online cost) by a factor of roughly 2 to 9 in both communication and computation. Furthermore, our two-party scheme could be easily extended to the 2-out-of-n threshold ECDSA.

KW - blockchain

KW - ECDSA

KW - threshold signature

KW - two-party signature

KW - zero-knowledge proof

UR - https://www.scopus.com/pages/publications/85119353497

U2 - 10.1145/3460120.3484803

DO - 10.1145/3460120.3484803

M3 - Conference Paper

AN - SCOPUS:85119353497

T3 - Proceedings of the ACM Conference on Computer and Communications Security

SP - 558

EP - 573

BT - Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

A2 - Kim, Hyoungshick

A2 - B. Hong, Jin

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

T2 - ACM Conference on Computer and Communications Security 2021

Y2 - 15 November 2021 through 19 November 2021

ER -

Xue H, Au MH, Xie X, Yuen TH, Cui H. Efficient online-friendly two-party ECDSA signature. In Kim H, B. Hong J, editors, Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. New York NY USA: Association for Computing Machinery (ACM). 2021. p. 558-573. (Proceedings of the ACM Conference on Computer and Communications Security). doi: 10.1145/3460120.3484803

Efficient online-friendly two-party ECDSA signature

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this