論文地址：https://eprint.iacr.org/2019/503.pdf
因為該篇文章太長，所以將分兩次進行介紹，該篇博文只介紹背景知識、結論等，核心部分推導我將會在下一篇博文中進行介紹，如果翻譯與理解有不對的地方，還請讀者大大們指摘，（部分翻譯內容也會進行增加補充）>-<

摘要部分

ECDSA is a widely adopted digital signature standard. Unfortunately, efficient distributed variants of this primitive are notoriously hard to achieve and known solutions often require expensive zero knowledge proofs to deal with malicious adversaries. For the two party case, Lindell [Lin17] recently managed to get an efficient solution which, to achieve simulation-based security, relies on an interactive, non standard, assumption on Paillier’s cryptosystem. In this paper we generalize Lindell’s solution using hash proof systems. The main advantage of our generic method is that it results in a simulation-based security proof without resorting to any interactive assumptions.
Moving to concrete constructions, we show how to instantiate our framework using class groups of imaginary quadratic fields. Our implementations show that the practical impact of dropping such interactive assumptions is minimal. Indeed, while for 128-bit security our scheme is marginally slower than Lindell’s, for 256-bit security it turns out to be better both in key generation and signing time. Moreover, in terms of communication cost, our implementation significantly reduces both the number of rounds and the transmitted bits without exception.

譯: ECDSA（橢圓曲線數字簽名）是一個被廣泛采用的資料簽名標準，但不幸的是ECDSA的密碼學原語卻很難實作高效的分布式變種方案，且經常需要高昂的零知識證明去處理惡意攻擊，從現有兩方的案例上看，Lindell最近有做出了一個有效的解決方案去實作基于模擬的安全¹，該方案依賴于一個互動式非標準的Paillier密碼體制的假設，本論文中我們歸納了Lindell使用hash證明體制的解決方案，而我們的泛用方法的主要優勢在于它無需進行任何互動式的假設即可實作基于模擬的安全，在具體的構造上，我們用虛二次域類群²來展示我們怎么實體化方案架構的，我們的實作表明（在Lindell方案上）洗掉此類的互動式假設的實際影響較小，事實而言，在128-bit安全等級下我們的方案比Lindell的要慢一些，但是在256-bit安全等級下，它在密鑰生成和簽名時間上都比Lindell的方案要好，此外，在通信開銷上，我們的方案顯著減少了輪換次數并且沒有遺漏任何傳輸位元，

引言

門限密碼學中允許 n n n個使用者以某種方式去共享一個通用密鑰，任何 t t t方（ t t t為門限閾值）的子集都可以使用這個通用密鑰去解密或者簽名，這個而任何小于t的聯盟都無能為力去解密或簽名，這個范例的關鍵特征在于它允許使用無需重構的共享密鑰，這意味著每當密鑰被使用（去簽名/解密）時， t t t方子集中人員就必須積極參與，
門限密碼學應用范圍比較廣，從多個簽名者需要簽署同一份檔案到分布式場景下敏感檔案需要被定額人數授權，這種多用途引發了對門限密碼學研究的熱潮，主要表征在1990年早期到2000年早期，產生了最廣泛被使用的門限密碼學方案，因為如下的原因近些年可以看出在這個領域的研究興趣又一次高漲：首先，很多初創公司正在使用這種技術去保護現實生活中的應用程式，此外，對于使用ECDSA作為基礎簽名方案的位元幣和其他加密貨幣，即有安全漏洞就會導致實際的金融損失的數字貨幣類，雖說基于多重簽名的對策已經內置到位元幣中，但它們提供的靈活性較差并且在匿名以及可伸縮性上產生了問題（見[GGN16]），最后，一些20年前被開發出的方案并不能滿足當前應用程式所希望的那樣高效，像ECDSA/DSA簽名就是如此，事實上，對于許多其他方案，快速門限變種（例如RSA解密/簽名和ECIES解密）是已知的構造其簽名的有效門限變種比證明它們要困難得多，這種不對等的原因似乎是需要從一個未知 k k k中反推計算出 k ? 1 m o d q k^{-1}mod q k?1modq的結果困難造成的（這邊意譯），為了解釋為何如此，讓我們首先簡單回顧一下ECDSA是如何實際運作的，公鑰是一個橢圓曲線上的點 Q Q Q并且簽名密鑰是 x x x，像 Q ← x P Q\leftarrow xP Q←xP，其中 P P P是一個橢圓曲線上基于 q q q階的生成的點，為了簽名訊息 m m m首先要用一些合適的hah函式 H H H對其進行hash處理，然后根據以下演算法步驟進行處理：

1. 在 Z / q Z Z/qZ Z/qZ中選擇亂數 k k k
2. 計算 R ← k P R\leftarrow kP R←kP
3. 令 r ← r x m o d q r\leftarrow r_{x}\ mod\ q r←rx? mod q 其中 R = { r x , r y } R=\{r_{x},\ r_{y}\} R={rx?, ry?}
4. 設定 s ← k ? 1 ( H ( m ) + r x ) m o d q s\leftarrow k^{-1}(H(m) + rx)\ mod\ q s←k?1(H(m)+rx) mod q
5. 輸出 ( r , s ) (r, s) (r,s)
   
   現在，最自然實作以上演算法分配步驟應是在參與方之間分享并累加 x x x，然后開始用一個多方計算協議去產生簽名，在兩方案例中，這意味著參與方需開始共享 x 1 x_1 x1?和 x 2 x_2 x2?使得 Q = ( x 1 + x 2 ) P Q=(x_1+x_2)P Q=(x1?+x2?)P，參與方可以繼續產生亂數 k 1 k_1 k1?和 k 2 k_2 k2?進行共享，使得 R = ( k 1 + k 2 ) P R=(k_1+k_2)P R=(k1?+k2?)P，然而在這一點上如何有效地計算 k 1 ′ , k 2 ′ k^{'}_1,k^{'}_2 k1′?,k2′?使得 k 1 ′ + k 2 ′ = k ? 1 m o d q k^{'}_1+k^{'}_2=k^{-1}\ mod\ q k1′?+k2′?=k?1 mod q并不是很清晰，
   從論文[MR04]開始，兩方ECDSA簽名協議開始在 x x x和 k k k間采用共通乘法方式共享，構建的基本思路是非常簡單的，參與方起初持有 x 1 x_1 x1?和 x 2 x_2 x2?使得 Q = x 1 x 2 P = x P Q=x_1x_2P=xP Q=x1?x2?P=xP，每當新簽名產生時，他們產生亂數 k 1 ， k 2 k_1，k_2 k1?，k2?使得 R = k 1 k 2 P = k P R=k_1k_2P=kP R=k1?k2?P=kP，顯然，這樣的方式將允許獲得反置 k ′ k^{'} k′，即 ( k 1 ′ ) ? 1 ( k 2 ′ ) ? 1 = ( k 1 k 2 ) ? 1 m o d q (k^{'}_1)^{-1}(k^{'}_2)^{-1}=(k_1k_2)^{-1}\ mod\ q (k1′?)?1(k2′?)?1=(k1?k2?)?1 mod q，最后他們將會用Paillier的同態加密方案去秘密添加他們自己秘密并完成簽名，舉例而言，就是參與方 P 1 P_1 P1?計算 c 1 ← E n c ( ( k 1 ) ? 1 H ( m ) ) c_1\leftarrow Enc((k_1)^{-1}H(m)) c1?←Enc((k1?)?1H(m))和 c 2 ← E n c ( ( k 1 ) ? 1 x 1 r ) c_2\leftarrow Enc((k_1)^{-1}x_1r) c2?←Enc((k1?)?1x1?r),然后 P 2 P_2 P2?可以利用方案中的同態特性完成簽名，如下：
   c ← c 1 k 2 ? 1 c 2 k 2 ? 1 x 2 = E n c ( ( k 1 ) ? 1 H ( m ) ) E n c ( ( k 1 ) ? 1 x 1 r ) = E n c ( k ? 1 ( H ( m ) + x r ) ) c\leftarrow c_1^{k_2^{-1}}c_2^{k_2^{-1}x_2 }= Enc((k_1)^{-1}H(m))Enc((k_1)^{-1}x_1r)=Enc(k^{-1}(H(m)+xr)) c←c1k2?1??c2k2?1?x2??=Enc((k1?)?1H(m))Enc((k1?)?1x1?r)=Enc(k?1(H(m)+xr))
   
   P 2 P_2 P2?通過將 c c c發回給 P 1 P_1 P1?來結束協議，現在，如果 P 1 P_1 P1?也知道解密密鑰，那么他就能夠從 c c c中提取簽名 s ← k ? 1 ( H ( m ) + x r ) s\leftarrow k^{-1}(H(m)+xr) s←k?1(H(m)+xr)
   但是，證明各方都正確遵守了協議是很難的，最初的嘗試[MR04]通過高昂的零知識證明解決了這一問題，此外最近Lindell在[Lin17]中提供了一個更加簡便和有效的協議，Lindell的協議的關鍵思路是有觀察到在上述兩方ECDSA簽名協議中，不誠實方能制造非常小的麻煩，但事實上，如果在準備階段， P 2 P_2 P2?同時收到了Paillier方案中要用的加密密鑰和 P 1 P_1 P1?的簽名密鑰的加密 E n c ( x 1 ) Enc(x_1) Enc(x1?)，那么根本上來說，一個不誠實的 P 1 P_1 P1?能做的就是參與 R ← k 1 k 2 P R\leftarrow k_1k_2P R←k1?k2?P的產生，但需要注意后者建立在DH協議基礎之上，是非常有效且魯棒性的協議，
   
   另一方面，如果 P 2 P_2 P2?不誠實，那么她能做的就是（除了再次產生一個R）去構造一個有損害的 c c c作為最終反饋給 P 1 P_1 P1?的結果，但是，當 P 2 P_2 P2?真的嘗試那樣做的話，那么通過簡單驗證結果簽名的合法性將很容易檢測到它的惡意行為，
   但是實際證明的話將會引發一些問題，首先第一個問題是由Paillier的明文空間是 Z / N Z Z/NZ Z/NZ（ N N N是一個大合數）而ECDSA簽名依賴于 Z / q Z Z/qZ Z/qZ（ q q q是素數），因此為了避免這個不一致的問題，需要確保將 N N N取得足夠大，以便在整個簽名程序中不會發生wrap-around情形³，這也意味著將 E n c ( x 1 ) Enc(x_1) Enc(x1?)發送給 P 2 P_2 P2?時， P 1 P_1 P1?需要證明明文 x 1 x_1 x1?在正確的范圍內（即足夠小），
   在此證明中使用Paillier加密會產生一個微小的問題，事實上，如果要使用該方案在實際和模擬的執行中分辨敵手的不可區分性，似乎有必要設定一個關于Paillier密碼體系不可區分性的規約， 這意味著必須設計一種證明技術，該技術可以成功使用Paillier加密方案而無需知道相應的密鑰， 根據Lindell的協議，在設計基于模擬的安全策略來應對有惡意參與方 P 2 P_2 P2?時會出現問題， 在這種情形下， P 2 P_2 P2?確實可能會發送一個錯誤的密文 c c c（即不對簽名進行加密）而模擬器根本無法將其識別為錯誤的密文，
   Lindell [Lin17]提出了兩種可替代的證明來克服這一問題， 第一個依靠一個基于博弈的定義，并通過允許仿真模擬器例外終止來避免該問題，概率取決于已提出簽名 q s q_s qs?的數量， 但這似乎導致了不緊密的安全性證明（因為規約減少了一個 q s q_s qs?因子）， 第二個證明是基于模擬的定義避免例外終止，但需要引入有關Paillier加密案的新的互動式的非標準假設，
   因此，可以說，盡管該領域最近有取得了進展，但仍然存在以下公開的問題：
   是否有可能設計出一種實用的兩方ECDSA簽名協議（兩者都就計算效率和帶寬消耗而言）不需要互動性假設并允許一個嚴密的安全規約？

總結

受到Lindell方案的啟發，我們提出了第一個哈希證明系統的兩方ECDSA簽名的通用構造，系統構造是基于同質模數的，理論上來說，由于底層語意安全的同態加密方案的結構，我們的構造可以實作基于模擬的安全性證明，該證明即嚴格且無需互動性假設，事實上而言，我們使用CL框架從虛數二次域類組提供詳細的實體化案并用C實作，與Lindell的基于Paillier的方案相比，在高級別的安全性方面，它產生了更好的性能；在標準級別上（128bit），它具有同樣數量級，我們的解決方案在192bit以后的安全等級上比Lindell的運算要快，虛二次域中理想⁴算術的進步可能會帶來改進（見[IJS10]實體）基于類組的可驗證延遲功能也應激發該領域的最新研究（例如Chia 網路[Chi]也為此展開了競爭），

這一段有點翻譯和理解有些困難，后續進行更新改進，

最后，我們的作業聚焦在兩方案例下，我們相信我們構造方案的想法將引發門限ECDSA簽名案例的改善，我們留至下一步作業，