導 讀

如果關心近年的密碼學成果，可以發現雙線性對作為一個基礎的密碼學工具頻頻出現。雙線性對是一種二元映射，它作為密碼學算法的構造工具，在各區塊鏈平臺中廣泛應用，比如零知識證明、聚合簽名等技術方案大多基于雙線性對構造得來。
本次分為上、下兩個篇章講解雙線性對在密碼學中的應用。

上篇回顧《雙線性對在密碼學中的應用（上）》

本文為下篇進階篇，會從雙線性對的性質開始著手，然后分析三方一輪密鑰交換和SM9數字簽名算法兩個例子的原理，最后介紹一些雙線性對的優秀代碼實現。

雙線性對的性質介紹

▲ 性質介紹
在本科階段的線性代數課程中，讀者可能已經學習過線性映射（linear mapping）的概念，但是對雙線性映射（bilinear mapping）的概念可能會感到陌生。

我們說一個函數f是線性的是指函數f滿足可加性和齊次性，也就是：

可加性：f(a)+f(b)=f(a+b)

齊次性：f(ka)=kf(a)

比如中學就接觸的正比例函數就是一個線性映射。

例如對f(x)=3x，有f(1)=3，f(-2)=-6，則：

可加性：f(1)+f(-2)=f(-1)=-3

齊次性：f(-2)=-6=-2f(1)

理解了線性，那么雙線性就好理解很多。

和線性函數不同的點在于滿足雙線性的函數有兩個輸入，而且對這兩個輸入分別滿足線性。換言之，如果固定其中一個輸入使之成為一元函數，則這個一元函數滿足線性。

而雙線性對就是指群上元素滿足雙線性映射的三個群，它們的關系滿足雙線性，下面是定義：

G?、G?和G?是三個n階循環群，一個雙線性對（雙線性映射）𝑒是一個從G?×G?→G?的雙線性映射，滿足：

1.雙線性性: 𝑒(ag?，bg?) = ab𝑒(g?, g?), 其中g?∈ G?, g? ∈ G?

2.非退化性: 存在g?，g?，使得𝑒(g?，g?) 不為G?中的單位元

3.可計算性: 存在有效的多項式時間算法計算雙線性對的值

上述定義簡單來說就是，一個映射e，能將G?和G?中的兩個元素映射為G?中的一個元素，并且該映射滿足雙線性。這里的定義雖然嚴謹，但不便于讀者接受，我們通過類比來加深理解，例如讀者熟悉的向量內積就滿足雙線性。我們來回顧一下向量內積的特點，內積運算從兩個向量α和β得到數r：

α · β → r

所謂雙線性映射，是從兩個元素到一個元素的映射，并且這個映射對每一個輸入的元素都保持線性。

比方說：我們固定β，則r和α是有線性的關系的：如果用kα代替α，那么結果就是kr；固定α也有同樣的結論，因此內積的運算是有雙線性的。

我們研究的橢圓曲線上的雙線性對也正是有類似的雙線性，并且根據雙線性，我們有下面的推論：

設g?, g?分別是群G?和G?的元素，𝑒是G?×G?→G?的雙線性映射，那么有：

𝑒(ag?, bg?) = ab 𝑒(g? , g?) = 𝑒(abg? , g?) = 𝑒(g? , abg?)

𝑒(ag?, bg?) + 𝑒(cg?, dg?) = (ab+cd) 𝑒(g?, g?)

注意這里G?的群運算用加法表示了，如果用乘法表示則看起來會不同，但是本質一樣，寫成加法還是乘法只是符號的問題。

本文約定都按照加法形式處理（這里的加法并不暗示群一定是交換群），但通常習慣將G?寫成乘法群的形式，如下：

綜上我們可以看到雙線性使得變量前面的系數可以靈活轉化，這是正是雙線性對獨特的性質。利用這些性質，雙線性對在密碼學中可用來構造很多其他數學工具所不能構造的協議或方案。

▲ SM9密鑰協商算法解析
首先我們來理解雙線性對在SM9算法中起到的作用。

下面的介紹中的簽名算法是簡化后的版本，能夠體現算法原理，但是并非SM9標準算法本身，簽名算法的完整流程可以參看參考文獻中的GM/T0044標準。

因為使用到雙線性配對，這里涉及到三個橢圓曲線群，我們記為G?、G?和G?，e是從G?×G?到G?的雙線性映射，G?和G?的生成元分別為P?、P?。并且設e(P?, P?)=P? ∈ G?。

在簽名和驗簽之前，還需要經歷生成主密鑰、生成用戶密鑰兩個步驟，主密鑰只需要生成一次并由密鑰生成中心保管，而用戶密鑰生成則需要為每個用戶生成一次。

可以看到相對于ECDSA算法，SM9的密鑰生成相對要復雜一些。這里的巧妙之處在于將H(ID)+ks的逆元隱藏在用戶私鑰中，稍后這一逆元也會影響到簽名和驗簽。

簽名和驗簽算法的巧妙之處在于計算hash時拼接了re(P?,Ps)，從而將rPs隱藏在hash結果中，驗簽算法正是通過S和公鑰計算rPs的過程——如果簽名中的h和S是正確的，那么按照驗簽流程應該能夠計算出同樣的rPs，然后同樣計算H(M||rPs)，如果該值和h一致，那么簽名被認為是合法的。

而驗簽算法中計算rPs的過程正是利用了雙線性映射。驗簽的第三步驟中通過e(P?,Ps)約減掉了之前提到的H(ID)+ks，從而得到結果。

這個具體過程可以看下面的式子，這個式子也恰好是SM9簽名算法正確性的簡單證明：

▲ 三方一輪密鑰協商算法解析
該算法的關鍵在于三方獨立計算出的a𝑒(bG, cG)、b𝑒(aG , cG) 和c𝑒(aG, bG)要相同，否則就無法協商出一致的密鑰。

但是根據雙線性對能夠將每個參數的系數提出來的這個性質，我們有：

a𝑒(bG, cG) = abc𝑒(G , G)

b𝑒(aG , cG) = abc𝑒(G , G)

c𝑒(aG, bG) = abc𝑒(G , G)

因此三方計算出的密鑰k是相同的，上面三個式子也恰好是該算法正確性的簡單證明。

雙線性對的實現

本文的最后，我們來了解一些雙線性對已有的代碼應用實現。

自Weil提出雙線性對概念時構造出Weil對以來，后續的密碼學家提出很多新的雙線性對的構造，例如Tata對、Ate對、Rate對、最優對等。

雖然雙線性對有諸多優點，但是其計算開銷往往較大。

例如基于配對的BLS簽名，雖然可以方便的實現簽名聚合，但是其驗簽時間相對于傳統的ECDSA簽名上升了兩個數量級。因而不斷研究各種配對函數主要也是為了降低配對函數計算的復雜度，從而使雙線性對這個工具更有實用性。

另外需要強調的是，并非基于任何橢圓曲線都可以構造配對函數，對于能有效實現雙線性對的橢圓曲線，稱為pairing-friendly curves。

BN曲線曾是配對友好曲線的代表，在go語言代碼包golang.org/x/crypto/bn256中提供了基于BN256曲線的雙線性對實現，并且該代碼包中提供了使用BN256完成一輪三方密鑰協商的測試示例。

下圖是該代碼包的介紹性注釋：

不幸的是，2016年的研究（https://moderncrypto.org/mail-archive/curves/2016/000740.html)指出BN曲線配對在NFS數域篩算法的攻擊下達不到宣稱的安全等級（在新攻擊方法下估計強度大約減少1/4）。

此發現的影響范圍非常廣，至少波及zcash等項目使用的zkSNARK實現、Apache Milagro項目、以太坊、任何使用相關曲線的BBS簽名和BLS簽名等，可能影響到intel的SGX和EPID安全性。

鑒于此，該代碼倉庫不再做維護。

但是也不必沮喪，回顧《雙線性對在密碼學中的應用（上）》那句話，進攻和防守只是同一件事的不同方面，這一發現只會促進安全性的又一次進步。

首先對于BN曲線，仍然可以通過提高參數長度來彌補漏洞。建議將曲線大小提高1/3從而到達相同的安全等級。另外，除去BN曲線，仍然有其他可用于配對的曲線可以選擇。IEFT審議的草案pairing-friendly-curve的第七個版本（https://tools.ietf.org/pdf/draft-irtf-cfrg-pairing-friendly-curves-07.pdf）已經完全考慮到相關攻擊的影響，因此該草案中推薦的曲線目前是安全的。

對于128位安全級別，草案推薦嵌入度為12的381位特征的BLS曲線和462位特征的BN曲線，對于256位的安全級別，推薦嵌入度為48且具有581位特征的BLS曲線。

從代碼實現的角度來看，PBC（https://crypto.stanford.edu/pbc/）庫和Miracl（https://miracl.com/）庫是兩個較優的選擇。

總 結

經過十余年的研究，雙線性對的性質、實現方法等研究領域已經有了很大進展。

本文簡要介紹了雙線性對在密碼學中的應用，包括雙線性對的研究歷程、雙線性對的概念和性質以及雙線性對的應用，主要包括三方一輪密鑰協商、SM9標識密碼。

在學界對雙線性對多年的研究之后，多線性映射作為一個自然而然的推廣也得到越來越多的關注，是相關領域下一個值得期待的研究熱點，我們會在以后的介紹中分享，大家敬請期待！

參考文獻與推薦閱讀

[1] cl簽名

https://www.iacr.org/archive/crypto2004/31520055/cl04.pdf

[2] 配對友好的曲線（RFC草案）

https://tools.ietf.org/pdf/draft-irtf-cfrg-pairing-friendly-curves-07.pdf

[3] 三方一輪密鑰交換

https://xueshu.baidu.com/usercenter/paper/show?paperid=5521a92e88e750ae92df7b1cd8287452&site=xueshu_se

[4] 一個關于雙線性對的綜述

http://jos.org.cn/ch/reader/create_pdf.aspx?file_no=3651&journal_id=jos

[5] 基于BN曲線的雙線性對實現

https://cryptojedi.org/papers/dclxvi-20100714.pdf

[6] SM9標識密碼算法GMT0044

http://www.gmbz.org.cn/main/viewfile/20180110024900801385.html

作者簡介

喬沛楊

來自趣鏈科技基礎平臺部

區塊鏈密碼學研究小組

總結

以上是生活随笔為你收集整理的双线性对在密码学中的应用（下）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。