Bilinear Map 是不少新型 Pairing-based Cryptography 的基礎概念。
當中雖然有不少難明的數學，但我們仍然可以在用最少數學的情況下理解它。
---
假設有兩個 Cyclic Groups (G1 和 G2)。
它們中間有一個 mapping function，可以找出相對應另一個新的 Cyclic Group (Gt)。
只要輸入 G1 和 G2 的成員值，它就會為你找出對應的 Gt 成員值。
我們先稱這個 mapping function 做 e 。
這個 mapping function e 有一些好用的特性：
假設 u 是 G1 的成員，v 是 G2 的成員，w 是 Gt 的成員，它就可以：
e( u^a, v^b ) = e( u,v )^(ab) = w^(ab)
其實這種 mapping function 有點難找，計算上也未必容易，
所以，我們只考慮那些 efficient 的 bilinear map，並稱它們做 admissible bilinear map。
而在加密學中最好用的 mapping，就是當 G1 = G2 的那一種。
所以在不同的文章，普遍都會假定 G = G1 = G2 。
---
目前有兩大方法可以找出 bilinear mapping function，其中一種是 Weil Pairing，另一種是 Tate Pairing。由於牽涉太多數學和計算機科學，而且不好理解，所以不在此詳述。
---
以下一個例子，證明 bilinear map 其實很好用：
1. Decisional Diffie-Hellman
給定 g, g^a, g^b, g^z, 判斷 a*b = z 。
沒有 bilinear map，你必須先試出 a 和 b 的值，然後才知道。
（按：(g^a)*(g^b) = g^(a+b)，所以真的只有不斷試，沒有捷徑）
但當有 bilinear map，事情就十分好辦：
只要先試一下 e(g^a, g^b) = w^(ab)，再試一下 e(g, g^z) = w^(z)，
只要 w^(ab) 和 w^(z) 的數值相同，就等於 w^(ab) = w^(z)，也就是 ab=z。
（註：w^(ab) 的數值是 Gt group space 的值。數字是什麼也不重要啊，反正相同就可以）
2. Computational Diffie-Hellman
給定 g, g^a, g^b，找出 g^(ab) 。
這種情況，即使有 bilinear mapp 也沒有用。
因為 bilinear map 只會給你另一個 group space 的值，根本沒有什麼用。
這種 CDH 困難，DDH 容易的特性，
正好幫助我們用 bilinear map 來加密資料，同時又不易破解。
---
例如 Joux 的 3 Party Diffie Hellman，正正使用了 bilinear mapping。
首先 Alice, Bob 和 Carol 持有 a, b 和 c，而且他們是三角關係：
（就是 A <---> B, B <---> C, C <---> A 的關係）
1. Alice 和 Bob 交換 g^a 和 g^b ，
2. Bob 和 Carol 交換 g^b 和 g^c ，
3. Carol 和 Alice 交換 g^c 和 g^a ,
此刻，Alice 擁有 a, g^b 和 g^c，Bob 擁有 b, g^a 和 g^c，Carol 擁有 c, g^b 和 g^a 。
所以：
Alice 可以計算出 e(g^b, g^c)^a = (w^(bc))^a = w^(abc)
Bob 可以計算出 e(g^a, g^c)^b = (w^(ac))^b = w^(abc)
Carol 可以計算出 e(g^b, g^a)^c = (w^(ba))^c = w^(abc)
他們三人就可以用 w^(abc) 作為共同金鑰。
後來 Boneh Franklin 的 Identity Based Cryptography 都使用了接近的概念，
於加密時放置了 g^r 和 g^s，並使用 bilinear mapping 找出 w^(rs) 進行加密/解密。
---
小記：因為 bilinear mapping 太難理解， 所以當 1993 年被發現的時候，它主要是用作嘗試破解 ECC (MOV reduction) 的。雖然理論上破解的難度由 infinite 變成 finite，但仍然十分困難。直至 2000 年左右，Joux，Boneh 和 Franklin 等人發現到「正當」的新用途，也就是 3-Way DHKE 和 IBE 。
---
引用參考：
https://people.csail.mit.edu/alinush/6.857-spring-2015/papers/bilinear-maps.pdf
https://www.math.uwaterloo.ca/~ajmeneze/publications/pairings.pdf
