Paper 2022/297

Promise $\Sigma$-protocol: How to Construct Efficient Threshold ECDSA from Encryptions Based on Class Groups

Yi Deng, Shunli Ma, Xinxuan Zhang, Hailong Wang, Xuyang Song, and Xiang Xie


Threshold Signatures allow $n$ parties to share the ability of issuing digital signatures so that any coalition of size at least $t+1$ can sign, whereas groups of $t$ or fewer players cannot. The currently known class-group-based threshold ECDSA constructions are either inefficient (requiring parallel-repetition of the underlying zero knowledge proof with small challenge space) or requiring rather non-standard low order assumption. In this paper, we present efficient threshold ECDSA protocols from encryption schemes based on class groups with neither assuming the low order assumption nor parallel repeating the underlying zero knowledge proof, yielding a significant efficiency improvement in the key generation over previous constructions. Along the way we introduce a new notion of promise $\Sigma$-protocol that satisfies only a weaker soundness called promise extractability. An accepting promise $\Sigma$-proof for statements related to class-group-based encryptions does not establish the truth of the statement but provides security guarantees (promise extractability) that are sufficient for our applications. We also show how to simulate homomorphic operations on a (possibly invalid) class-group-based encryption whose correctness has been proven via our promise $\Sigma$-protocol. We believe that these techniques are of independent interest and applicable to other scenarios where efficient zero knowledge proofs for statements related to class-group is required.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2021
threshold signaturesECDSAclass groups
Contact author(s)
deng @ iie ac cn
shunlima @ foxmail com
zhangxinxuan @ iie ac cn
wanghailong9065 @ iie ac cn
songxuyang @ matrixelements com
xiexiang @ matrixelements com
2022-03-07: received
Short URL
Creative Commons Attribution


      author = {Yi Deng and Shunli Ma and Xinxuan Zhang and Hailong Wang and Xuyang Song and Xiang Xie},
      title = {Promise $\Sigma$-protocol: How to Construct Efficient Threshold ECDSA from Encryptions Based on Class Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2022/297},
      year = {2022},
      doi = {10.1007/978-3-030-92068-5_19},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.