雙線性映射的優點
考慮配對 $ e: G_1*G_2 \to G_t $ .
為什麼我們要從組中映射元素 $ G_1 $ 和組 $ G_2 $ 到一個元素 $ G_t $ . 它們在密碼學中是如何使用的？它們提供了哪些優勢？
如果我們要用一句話來概括事物，假設配對允許三方數學協議。
例如考慮基於身份的加密。在用於加密消息（例如電子郵件）的經典公鑰密碼系統中，發送者必須知道接收者的公鑰才能加密消息。公鑰的分發是一個已知的麻煩問題（比秘密密鑰的分發困難，但仍然很困難）。IBE 努力使收件人的公鑰實際上等於收件人的姓名（或電子郵件地址），因為發件人已經知道它。如果你想用 RSA 做 IBE，你通常會得到一個集中式系統，其中有一個中央系統C，所有消息都通過它。每個使用者都知道一個公鑰，即C中的一個，並使用該公鑰加密消息。C解密消息，並使用預期接收者的公鑰重新加密它（C知道所有使用者的公鑰）。
這種 IBE 的經典模型不能很好地擴展，因為中央系統必須接收、解密、加密和發送每封電子郵件。配對通過將中央系統轉移到純粹的數學來解決這個問題。通過配對，中央系統C仍然存在，但不需要為每封電子郵件呼叫它。事情或多或少是這樣的：
- 中央系統C有一個私鑰，對應的公鑰K是每個使用者都知道的。
- 每個使用者U從C獲得他的私鑰K U。
- 當發件人S想向收件人R發送電子郵件時，他可以“以某種方式”僅使用R的姓名（電子郵件地址）和中央系統公鑰K來計算**R的公鑰。
- 收件人R使用K R來解密消息。
配對就是存在於這個“不知何故”中的東西。這是一個涉及K、R的名稱和來自**U的一些輸入的計算。它將C移出物理圖片。C在數學上仍然存在（特別是，C知道每個使用者的私鑰，因為C計算這些私鑰），但C在發送電子郵件時不需要做任何特別的事情。這可以防止C在流量增加時成為網路瓶頸。
以類似的方式，配對對於電子現金協議（買方、商家和銀行之間的三方協議，我們不希望每次交易都與銀行進行實際交談）很方便。
從歷史上看，配對是 1950 年代的一種數學奇思妙想，在 1986 年被米勒證明可用於密碼學，並首次用於打破橢圓曲線。的確，一對來自 $ G_1\times G_2 $ 至 $ G_3 $ 打開離散對數問題 $ G_1 $ 成離散對數 $ G_3 $ . 對於橢圓曲線上的已知配對， $ G_1 $ 是一個 $ n $ -位曲線，和 $ G_3 $ 是大小有限域中的乘法子群 $ kn $ ， 在哪裡 $ k $ 是曲線的嵌入度。在有限域上破壞 DL 的次指數算法是已知的，所以如果 $ k $ 小，應用配對使 DL 問題更容易。
幸運的是，對於實踐中使用的大多數曲線， $ k $ 是天文數字，因此配對不會破壞這些曲線上的 DL。一些特定的曲線（尤其是大多數超奇異曲線）的嵌入度非常低，對它們來說，配對是一種有用的破壞工具。
配對的建設性使用（對於 IBE）依賴於使用“稍微弱化”的曲線，即嵌入程度足夠小以允許有效計算配對，但不足以使 DL 生效的曲線 $ G_3 $ 太容易了。例如，IBE 將使用嵌入度為 2 的 800 位超奇異曲線；1600 位有限域上的深度學習仍然遠遠超出了技術上的可行性。這仍然是一種相當微妙的舞蹈，它解釋了許多密碼學家在配對存在時感到不安。
您可以乘以加密值。例如考慮 Paillier 公鑰加密。加密值可以通過乘以密文來相加，因為密文的形式為 $ g^mr^n $ 在哪裡 $ m $ 是消息（ $ r $ 通過提高到密鑰來取消）。通過將兩個 Paillier 密文相乘，您可以添加指數。所以你有一種加法同態。通常，您可以評估指數上的仿射電路 ( $ g^{a+b+c+ \cdots} $ ) 沒有配對。但是通過配對，您也可以對指數進行乘法運算。也就是說，在某些限制下，不受信任的一方可以同態地評估需要在某個門檻值下進行乘法運算的電路（BGN 密碼系統）
但這並不是配對有用的唯一情況。配對的第一個主要密碼學用途是通過將其簡化為更簡單組上的離散對數問題來打破特定組（某些橢圓曲線組，MOV攻擊）中的離散對數問題。