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