International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Yi Deng , the State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences
Shunli Ma , the State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences
Xinxuan Zhang , the State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences
Hailong Wang , the State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences
Xuyang Song , Shanghai Key Laboratory of Privacy-Preserving Computation
Xiang Xie , Shanghai Key Laboratory of Privacy-Preserving Computation
Download:
DOI: 10.1007/978-3-030-92068-5_19
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2021
Abstract: 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 less 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 assumptions. In this paper, under \emph{standard assumptions} we present efficient threshold ECDSA protocols from encryption schemes based on class groups \emph{without parallel repeating the underlying zero knowledge proof}, yielding a significant efficiency improvement in the key generation over previous constructions (even those based on non-standard assumptions). Along the way we introduce a new notion of \emph{promise} $\Sigma$-protocol that satisfies only a weaker soundness called \emph{promise extractability}. An accepting \emph{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 \emph{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.
Video from ASIACRYPT 2021
BibTeX
@inproceedings{asiacrypt-2021-31487,
  title={Promise $\Sigma$-protocol: How to Construct Efficient Threshold ECDSA from Encryptions Based on Class Groups},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-92068-5_19},
  author={Yi Deng and Shunli Ma and Xinxuan Zhang and Hailong Wang and Xuyang Song and Xiang Xie},
  year=2021
}