---

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

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

總結

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

---

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

---

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

---

1. 密碼學證明安全性有兩種方式：一種是基於博弈的安全 [Game-based Security]，另一種是基於模擬的安全 [Simulation-based Security] 。關於兩者的區別分析請移至以下連線參考; ↩︎

2. 代數數論中的一個常見概念，在代數數論中，二次域是在有理數域$\mathbb{Q}$上次數為二的數域。二次域可以唯一地表成$\mathbb{Q}(\sqrt{d})$，其中$d$無平方數約數。若$d>0$，稱之為實二次域；否則稱為虛二次域或復二次域。虛實之分在於$\mathbb{Q}(\sqrt{d})$是否為全實域。wiki百科地址; ↩︎

3. 當乘法轉換為密文時，稱為warp-around情形（此點後續進行擴充描述） ↩︎

4. 環論概念 ↩︎