如果關(guān)心近年的密碼學(xué)成果，可以發(fā)現(xiàn)雙線性對作為一個基礎(chǔ)的密碼學(xué)工具頻頻出現(xiàn)。
雙線性對是一種二元映射，它作為密碼學(xué)算法的構(gòu)造工具，在各區(qū)塊鏈平臺中廣泛應(yīng)用，比如零知識證明、聚合簽名等技術(shù)方案大多基于雙線性對構(gòu)造得來。
本次將分為上、下兩個篇章講解雙線性對在密碼學(xué)中的應(yīng)用。
本文為上篇入門篇，會從概念介紹、發(fā)展歷程、實際應(yīng)用三個方面展開說明，下篇為進階篇，將從原理層面深入剖析。
雙線性對的研究歷程
▲1946年作為一個數(shù)學(xué)工具被提出（Weil對）
1946年雙線性對首先被法國數(shù)學(xué)家Weil提出并成為代數(shù)幾何領(lǐng)域重要的概念和研究工具。
在最初的時候，雙線性對的概念并非為了密碼學(xué)的研究，甚至Weil在提出雙線性對時現(xiàn)代密碼學(xué)還未成為系統(tǒng)的科學(xué)（3年后C.E.香農(nóng)發(fā)表著名論文《保密系統(tǒng)的通信理論》奠定現(xiàn)代密碼學(xué)理論基礎(chǔ)，而公鑰密碼學(xué)的發(fā)展更在30年之后）。
▲1996年Menezes、Okamoto和Vanstone提出利用雙線性對將ECDLP問題規(guī)約到DLP問題的MOV攻擊
在19年火熱的電影《羅小黑戰(zhàn)記》中，主人公擁有控制自己“領(lǐng)域”的能力。電影中的“領(lǐng)域”指自己專有的一個空間，在此空間中可以主宰一切。
不嚴謹?shù)恼f，雙線性映射的功能也有幾分相似——雖然攻擊橢圓曲線系統(tǒng)在離散數(shù)域解決起來很難，但是如果被映射到特定的擴域從而規(guī)約為一般的離散對數(shù)問題，解決起來就相對容易。
但與攻擊橢圓曲線系統(tǒng)的目的恰恰相反，MOV（一種攻擊手段，詳細說明見文末）最終促進了橢圓曲線密碼學(xué)的發(fā)展。
這當然也是密碼學(xué)家去研究攻擊方法的本意——畢竟攻和防從來都是對立統(tǒng)一的兩個方面而已。
MOV攻擊并非能作用于全部的橢圓曲線，而是只能對參數(shù)滿足一定條件的曲線進行攻擊。這促使人們在選擇橢圓曲線參數(shù)時更加謹慎，更加注重抗MOV攻擊。
今天我們再選用橢圓曲線參數(shù)時都會考慮避開MOV攻擊的條件從而使所選的參數(shù)更安全。
例如國標《SM2橢圓曲線公鑰密碼算法》就充分重視了受到MOV攻擊的可能性，不僅在第一部分《總則》中用附錄A的部分篇幅介紹驗證曲線參抗MOV攻擊的方法，而且也在第五部分《參數(shù)定義》中給出了安全曲線的推薦參數(shù)。
▲2000年雙線性對開始在密碼學(xué)領(lǐng)域得到重視，成果有基于身份的密碼體制（IBE）、三方一輪密鑰協(xié)商、BLS簽名算法等
基于身份的密碼體制是公鑰密碼學(xué)的一個研究方向，其特點是直接用標識用戶身份的字符串作為公鑰。大家熟悉的國密SM9算法就屬于該類算法，這是目前國產(chǎn)密碼算法中唯一一個基于雙線性對的密碼算法。
三方一輪密鑰協(xié)商是一種可以在一輪交互內(nèi)完成三方的密鑰協(xié)商的密鑰協(xié)商協(xié)議，效率高于DH密鑰協(xié)商。
傳統(tǒng)的DH密鑰協(xié)商可以完成兩兩之間的密鑰協(xié)商。雖然能夠通過兩兩之間多輪協(xié)商完成三方之間的密鑰協(xié)商，但是增加了通信復(fù)雜度。
基于雙線性對能夠在三方之間通過一輪通信完成密鑰協(xié)商，大大降低了通信復(fù)雜度。
BLS簽名是Boneh、Lynn和Shacham三人基于雙線性映射構(gòu)造的短簽名方案，其特性之一就是能用于構(gòu)造聚合簽名。
除了上述的代表成果，雙線性對在隱私保護方面、可證明執(zhí)行、可信計算等方面也有大量成果，例如可信計算組（The Trusted Computing Group，TCG）在可信平臺模塊規(guī)范中推薦的橢圓曲線直接匿名證明協(xié)議（ECDAA），適用于通用問題的零知識證明（zk-SNARK），intel的可信計算環(huán)境SGX以及加強隱私ID（EPID）等。
雙線性對的應(yīng)用
雖然雙線性對有大量的應(yīng)用案例，但是限于篇幅，本文挑選了三方一輪密鑰交換和SM9數(shù)字簽名算法作為例子。
本部分先將算法過程剝離開來，還沒有太多去分析算法的原理，這是因為在不了解雙線性對的前提下理解這些算法是有困難的。
我們建議讀者先簡單閱讀本部分了解算法能實現(xiàn)的功能，然后在閱讀下篇的雙線性對的性質(zhì)介紹后再回來品味算法的優(yōu)美。
▲三方一輪密鑰交換
密鑰交換（key exchange）又叫密鑰協(xié)商（key agreement），是一種能夠讓參與者在公共信道上通過交換某些信息來公共建立一個共享密鑰的密碼協(xié)議。
最常見的是兩方DH密鑰交換，橢圓曲線群上的DH（ECDH）依據(jù)的橢圓曲線群是循環(huán)群這個性質(zhì)。
如下圖：
1.用戶A生成隨機數(shù)a，計算aG，并將aG發(fā)送給對方
2.用戶B生成隨機數(shù)b，計算bG，并將bG發(fā)送給對方
3.A和B利用手中信息分別計算出abG作為協(xié)商密鑰，原因是abG=baG
通過上述的DH算法可以輕松地完成兩方的密鑰協(xié)商，但是較難滿足需要三方密鑰協(xié)商的場景。
利用雙線性對可以僅做一輪通信完成密鑰協(xié)商。
如下圖所示：
1.A選擇隨機數(shù)a，計算aG，將結(jié)果發(fā)送給B和C
2.B選擇隨機數(shù)b，計算bG，將結(jié)果發(fā)送給A和C
3.C選擇隨機數(shù)c，計算cG，將結(jié)果發(fā)送給A和B
4.A計算ae(bG,cG)
5.B計算be(aG,cG)
6.C計算ce(aG,bG)
A、B、C分別計算出的結(jié)果就是協(xié)商出的密鑰。這個協(xié)議是雙線性配對在密碼學(xué)研究中的第一次正面應(yīng)用。
SM9數(shù)字簽名算法
SM9標識密碼算法包括數(shù)字簽名算法、密鑰協(xié)商算法、加解密算法三部分，我們主要來關(guān)注數(shù)字簽名算法。
不同于傳統(tǒng)簽名算法的由用戶隨機選擇私鑰然后計算得到公鑰的方式，SM9能夠?qū)崿F(xiàn)用戶指定公鑰，密鑰生成中心通過公鑰計算私鑰。
這樣可以將一些有意義的字符串，例如身份證號碼、郵箱地址等作為用戶公鑰，從而能在公鑰中直接反應(yīng)出用戶信息，這也是標識密碼（IBC）的含義。
簽名算法包括參數(shù)生成、密鑰生成、簽名和驗簽等幾個步驟。和一般簽名驗簽不同的地方在于，密鑰生成分為主密鑰生成和用戶密鑰生成兩部分，主私鑰由密鑰生成中心（KGC）保管。
可以看到不論是在三方一輪密鑰協(xié)商中，還是在SM9簽名驗簽中，e都扮演了重要的角色。當不知道e是指什么的情況下要理解上面兩個算法是不現(xiàn)實的，而這個映射e也正是本文的核心：雙線性映射。
e的計算是一個計算復(fù)雜度較高的操作，我們不打算介紹關(guān)于e的原理和細節(jié)，讀者只需要了解e的一些屬性就足夠理解上面兩個例子的思想。
因為篇幅原因，雙線性映射的性質(zhì)將在下篇介紹。在下篇的開始我們就會先幫助讀者理解什么是雙線性，然后緊接著再回顧上面的兩個算法，介紹并分析它們的思想和原理。
雙線性對的性質(zhì)介紹
▲性質(zhì)介紹
在本科階段的線性代數(shù)課程中，讀者可能已經(jīng)學(xué)習過線性映射（linear mapping）的概念，但是對雙線性映射（bilinear mapping）的概念可能會感到陌生。
我們說一個函數(shù)f是線性的是指函數(shù)f滿足可加性和齊次性，也就是：
可加性：f(a)+f(b)=f(a+b)
齊次性：f(ka)=kf(a)
比如中學(xué)就接觸的正比例函數(shù)就是一個線性映射。
例如對f(x)=3x，有f(1)=3，f(-2)=-6，則：
可加性：f(1)+f(-2)=f(-1)=-3
齊次性：f(-2)=-6=-2f(1)
理解了線性，那么雙線性就好理解很多。
和線性函數(shù)不同的點在于滿足雙線性的函數(shù)有兩個輸入，而且對這兩個輸入分別滿足線性。換言之，如果固定其中一個輸入使之成為一元函數(shù)，則這個一元函數(shù)滿足線性。
而雙線性對就是指群上元素滿足雙線性映射的三個群，它們的關(guān)系滿足雙線性，下面是定義：
綜上我們可以看到雙線性使得變量前面的系數(shù)可以靈活轉(zhuǎn)化，這是正是雙線性對獨特的性質(zhì)。利用這些性質(zhì)，雙線性對在密碼學(xué)中可用來構(gòu)造很多其他數(shù)學(xué)工具所不能構(gòu)造的協(xié)議或方案。
首先我們來理解雙線性對在SM9算法中起到的作用。
下面的介紹中的簽名算法是簡化后的版本，能夠體現(xiàn)算法原理，但是并非SM9標準算法本身，簽名算法的完整流程可以參看參考文獻中的GM/T0044標準。
可以看到相對于ECDSA算法，SM9的密鑰生成相對要復(fù)雜一些。這里的巧妙之處在于將H(ID)+ks的逆元隱藏在用戶私鑰中，稍后這一逆元也會影響到簽名和驗簽。
簽名和驗簽算法的巧妙之處在于計算hash時拼接了re(P?,Ps)，從而將rPs隱藏在hash結(jié)果中，驗簽算法正是通過S和公鑰計算rPs的過程——如果簽名中的h和S是正確的，那么按照驗簽流程應(yīng)該能夠計算出同樣的rPs，然后同樣計算H(M||rPs)，如果該值和h一致，那么簽名被認為是合法的。
而驗簽算法中計算rPs的過程正是利用了雙線性映射。驗簽的第三步驟中通過e(P?,Ps)約減掉了之前提到的H(ID)+ks，從而得到結(jié)果。
這個具體過程可以看下面的式子，這個式子也恰好是SM9簽名算法正確性的簡單證明：
▲三方一輪密鑰協(xié)商算法解析
該算法的關(guān)鍵在于三方獨立計算出的ae(bG,cG)、be(aG,cG)和ce(aG,bG)要相同，否則就無法協(xié)商出一致的密鑰。
但是根據(jù)雙線性對能夠?qū)⒚總€參數(shù)的系數(shù)提出來的這個性質(zhì)，我們有：
ae(bG,cG)=abce(G,G)
be(aG,cG)=abce(G,G)
ce(aG,bG)=abce(G,G)
因此三方計算出的密鑰k是相同的，上面三個式子也恰好是該算法正確性的簡單證明。
雙線性對的實現(xiàn)
本文的最后，我們來了解一些雙線性對已有的代碼應(yīng)用實現(xiàn)。
自Weil提出雙線性對概念時構(gòu)造出Weil對以來，后續(xù)的密碼學(xué)家提出很多新的雙線性對的構(gòu)造，例如Tata對、Ate對、Rate對、最優(yōu)對等。
雖然雙線性對有諸多優(yōu)點，但是其計算開銷往往較大。
例如基于配對的BLS簽名，雖然可以方便的實現(xiàn)簽名聚合，但是其驗簽時間相對于傳統(tǒng)的ECDSA簽名上升了兩個數(shù)量級。因而不斷研究各種配對函數(shù)主要也是為了降低配對函數(shù)計算的復(fù)雜度，從而使雙線性對這個工具更有實用性。
另外需要強調(diào)的是，并非基于任何橢圓曲線都可以構(gòu)造配對函數(shù)，對于能有效實現(xiàn)雙線性對的橢圓曲線，稱為pairing-friendly curves。
BN曲線曾是配對友好曲線的代表，在go語言代碼包golang.org/x/crypto/bn256中提供了基于BN256曲線的雙線性對實現(xiàn)，并且該代碼包中提供了使用BN256完成一輪三方密鑰協(xié)商的測試示例。
下圖是該代碼包的介紹性注釋：
不幸的是，2016年的研究指出BN曲線配對在NFS數(shù)域篩算法的攻擊下達不到宣稱的安全等級（在新攻擊方法下估計強度大約減少1/4）。
此發(fā)現(xiàn)的影響范圍非常廣，至少波及zcash等項目使用的zkSNARK實現(xiàn)、Apache Milagro項目、以太坊、任何使用相關(guān)曲線的BBS簽名和BLS簽名等，可能影響到intel的SGX和EPID安全性。
鑒于此，該代碼倉庫不再做維護。
但是也不必沮喪，回顧《雙線性對在密碼學(xué)中的應(yīng)用（上）》那句話，進攻和防守只是同一件事的不同方面，這一發(fā)現(xiàn)只會促進安全性的又一次進步。
首先對于BN曲線，仍然可以通過提高參數(shù)長度來彌補漏洞。建議將曲線大小提高1/3從而到達相同的安全等級。另外，除去BN曲線，仍然有其他可用于配對的曲線可以選擇。IEFT審議的草案pairing-friendly-curve的第七個版本（https://tools.ietf.org/pdf/draft-irtf-cfrg-pairing-friendly-curves-07.pdf）已經(jīng)完全考慮到相關(guān)攻擊的影響，因此該草案中推薦的曲線目前是安全的。
對于128位安全級別，草案推薦嵌入度為12的381位特征的BLS曲線和462位特征的BN曲線，對于256位的安全級別，推薦嵌入度為48且具有581位特征的BLS曲線。
從代碼實現(xiàn)的角度來看，PBC（https://crypto.stanford.edu/pbc/）庫和Miracl（https://miracl.com/）庫是兩個較優(yōu)的選擇。
總結(jié)
經(jīng)過十余年的研究，雙線性對的性質(zhì)、實現(xiàn)方法等研究領(lǐng)域已經(jīng)有了很大進展。
本文簡要介紹了雙線性對在密碼學(xué)中的應(yīng)用，包括雙線性對的研究歷程、雙線性對的概念和性質(zhì)以及雙線性對的應(yīng)用，主要包括三方一輪密鑰協(xié)商、SM9標識密碼。
在學(xué)界對雙線性對多年的研究之后，多線性映射作為一個自然而然的推廣也得到越來越多的關(guān)注，是相關(guān)領(lǐng)域下一個值得期待的研究熱點，我們會在以后的介紹中分享，大家敬請期待！
