可以解釋一下密碼學中什麼叫雙線性配對嗎？

---

雙線性配對（Bilinear Pairing, 也叫雙線性映射）最早在密碼學中是扮演者負面的角色。2000年，Joux[1]利用雙線性配對構造了一個三方密鑰交換協議。隨後在2001年，Boneh和Franklin[2]利用它構造了第一個實用並且可證安全的基於身份的加密方案（Identity-Based Encryption， IBE）。從此開始，雙線性配對才在密碼學中得到了廣泛的應用。

具體的來說，雙線性映射定義了三個素數p階群乘法循環群，,和。並且定義在這三個群上的一個映射關係，並且滿足以下的性質：

1. 雙線性：對於任意的，均有成立；

2. 非退化性：滿足。
3. 可計算性：存在有效的演算法，對於，均可計算。

如果則稱上述雙線性配對是對稱的，否則是非對稱的。

另外，上述的雙線性配對是素數階的，還存在一種合數階的雙線性配對，最早也是由Boneh等人在[3]中引入密碼學領域的。合數階雙線性配對利用子群的正交性可以在實現更加複雜的功能前提下完成安全性證明。

更詳細的雙線性映射的分類和實現可以參考[4][5]等文章。

註：在某些定義中，和可以為加法循環群。

參考文獻：

1. Joux, Antoine. "A one round protocol for tripartite Diffie–Hellman."Algorithmic number theory. Springer Berlin Heidelberg, 2000. 385-393.

2. Boneh, Dan, and Matt Franklin. "Identity-based encryption from the Weil pairing." Advances in Cryptology—CRYPTO 2001. Springer Berlin Heidelberg, 2001.

3. Boneh, Dan, Eu-Jin Goh, and Kobbi Nissim. "Evaluating 2-DNF formulas on ciphertexts." Theory of cryptography. Springer Berlin Heidelberg, 2005. 325-341.

4. Galbraith, Steven D., Kenneth G. Paterson, and Nigel P. Smart. "Pairings for cryptographers." Discrete Applied Mathematics 156.16 (2008): 3113-3121.

5. Freeman, David, Michael Scott, and Edlyn Teske. "A taxonomy of pairing-friendly elliptic curves." Journal of cryptology 23.2 (2010): 224-280.

---

突然發現這裡我竟然寫錯了。。所有的g^(ab)都寫成了g^(a+b+c)，已改正

====================

@SDKany 在前面的答案中已經講的很詳細了。補充一點關於雙線性對的安全性假設就完美了~

在一般的群裡面，密碼學protocol一般是基於DDH(Decisional Diffie-Hellman)或者是CDH(computational Diffie-Hellman)問題來構造的。(即假設這兩個問題是不存在多項式時間的演算法的)

DDH：任意選取(a,b,c), 在多項式時間內將(g^a,g^b,g^(ab)) 和(g^a,g^b,g^c)兩者明顯的區分開來。（一般protocol多用這個假設來構造，因為目前比較認可的安全定義都是IND- 和這個假設的條件類似）

CDH： 任意選取(a,b)，在多項式時間內計算出g^(ab).

可以明顯看出，如果存在GxG -&>G" 的一個雙線性對的話DDH問題實際上是可以被快速解決的（CDH並不能解決）。所以，一般基於雙線性對的密碼學protocol都是基於BDDH(Bilinear Decisional Diffie-Hellman)：

BDDH：任意選取(a,b,c,d), 在多項式時間內將(g^a,g^b,g^c,g^(abc)) 和(g^a,g^b,g^c,g^d)兩者明顯的區分開來。

BCDH： 任意選取(a,b,c)，在多項式時間內計算出g^(abc).

目前的假設是BDDH即使實在有pairing的情況下仍然是一個困難的問題(即不存在多項式演算法)。

---

不考慮密碼學上的安全性的話，e(x, y) = g^(x*y)就是一個，g隨便取個數字。

---

推薦閱讀：