Threshold Elliptic Curve Digital Signature Algorithm (Threshold ECDA)

橢圓曲線數位簽章演算法 (ECDSA) 是被廣為應用的簽章標準。我們推演出了門檻式的橢圓曲線數位簽章演算法。在我們提出的機制中，原本的 ECDSA 簽署者被分散成 n 個成員的群體。在 t<n/2 的前提下，該群體以秘密分享的方式共享某個橢圓曲線私密金鑰。 簽署一個合法的簽章需要群體中至少 t 個成員，任何少於 t 的共謀將無法偽造簽章也無法獲得其他成員的部分私密金鑰。 即使在某些成員企圖破壞運算過程的情況下，其他的成員可藉著互動式零知識驗證的技巧辨識出欺騙者。我們的機制混合了可驗證秘密分享、零知識與分散式運算的技巧。ECDSA is a widely adopted standard. We present a (t,2t,n) threshold Elliptic Curve Digital Signature Algorithm (ECDSA) scheme. In our scheme, the regular ECDSA signer is distributed into a $n$-participant group which shares the elliptic curve private key by Secret Sharing (SS) with the parameter 2t<n. To sign a valid signature with no one's secret revealed, it takes at least 2t participants of the group to collaborate. Coalition of less than t participants can not forge any signature nor require other's partial private keys. Even when some cheaters try to spoil the final result, the other honest participants still can identify them by interactive zero-knowledge proof. Our scheme is composed of verifiable secret sharing, zero knowledge proof and many distributed computation skills.1. Introduction---3 2. ECC and ECDSA---6 2.1 Elliptic Curve Cryptosystem---6 2.2 ECDSA---8 3. Preliminaries---10 3.1 Shamir's Secret Sharing---10 3.2 Verifiable Secret Sharing---11 3.3 Distributed Multiplication---12 3.4 Distributed inverse Derivation---15 4. Proposed Threshold ECDSA---17 4.1 System Model---17 4.1.1 Communication Model---17 4.1.2 Adversary Model---17 4.2 Threshold-ECDSA Scheme---18 4.3 Cheater Detection---19 4.4 Discussions---20 4.5 Threshold Level---20 5. Security Analysis---22 5.1 Correctness---22 5.2 View---22 5.3 Unforgeability---23 6. Conclusions---26 Appendix A Pedersen's Distributed Key Generation---29 Appendix B BGW-Method---31 Appendix C Zero-Knowledge Proof for Multiplication---3