雙線性圖中組的順序必須相同嗎？
我一直在閱讀雙線性映射及其在密碼學中的應用，而我一直看到的一件事還沒有點擊。
如果 $ e:G_1\times G_2\to G_n $ 是一個雙線性映射， $ G_1,G_2,G_n $ 總是被定義為具有相同的順序。
然而，在我看來， $ ord(G_n) $ 應該 $ ord(G_1)\cdot ord(G_2) $ . 我總是看到根據定義具有相同順序的組有什麼原因嗎？一定是這樣嗎？
如果兩者 $ G_1 $ 和 $ G_2 $ 有素數 $ r $ ，那麼這意味著有生成器 $ g_1 $ 和 $ g_2 $ ; 因此，對於每個 $ u_1 \in G_1 $ , 有一個整數 $ x_1 $ 模組 $ r $ 這樣 $ u_1 = g_1^{x_1} $ . 因此，每個配對值 $ e(u_1, u_2) $ 等於 $ e(g_1^{x_1},g_2^{x_2}) = e(g_1, g_2)^{x_1x_2} $ 通過雙線性。它遵循 $ e(g_1,g_2) $ 是所有可能配對值的生成器，雙線性意味著 $ e(g_1,g_2)^r = e(g_1^r, g_2) = 1 $ . 因此，這組可能的配對值也具有素數順序 $ r $ .
現在你可以想像 $ G_n $ 因為更大，可能的配對值只是一個嚴格的子集 $ G_n $ ，但這只是作弊。
請注意，雙線性和非退化意味著如果素數 $ p $ 劃分順序 $ G_1 $ ， 然後 $ 1 = e(u_1^p,u_2) = e(u_1,u_2^p) $ ，從中我們可以得出結論 $ p $ 也劃分了順序 $ G_2 $ , 和的順序 $ G_n $ 也是。所以我們不能對任何組進行配對。
然而，有可能 $ G_1 $ 和/或 $ G_2 $ 大於 $ G_n $ . 在實踐中，目前已知的有效配對都源自於在橢圓曲線上工作的 Weil 或 Tate 配對。從現在開始，我將在 $ G_1 $ 和 $ G_2 $ 另外，因為傳統要求我們談論點加法。Weil 和 Tate 配對的基本設置如下：
讓 $ \mathbb{F}_q $ 是有限的有序域 $ q $ . 讓 $ E $ 是一條橢圓曲線 $ \mathbb{F}_q $ . 讓 $ r $ 是以下順序的主要因數 $ E $ , 這樣 $ r^2 $ 不分順序 $ E $ ， 和 $ r $ 不等於場特性（這是為了避免很多退化的情況）。我們表示 $ Er $ 點的子群 $ r $ -torsion：這些是產生的點 $ 0 $ （“無窮遠點”）乘以 $ r $ , 並且有 $ r $ 其中。
然後有一個嵌入度，它是最小的整數 $ k \geq 2 $ 這樣 $ r $ 劃分 $ q^k-1 $ . 碰巧（Balasubramanian-Koblitz 定理） $ Er $ （該組 $ r $ -曲線上的扭力點 $ E $ , 這次考慮場上的點座標 $ \mathbb{F}_{q^k} $ ) 包含 $ r^2 $ 點。
在這種情況下，Weil 和 Tate 配對都變得不平凡。他們作為輸入 $ r $ -扭轉點在 $ Er $ , 和產量作為輸出值 $ \mathbb{F}_{q^k}^* $ , 更具體地說 $ r $ -th 根 $ 1 $ 在那個擴展的領域。這是大小的子組 $ r $ 領域中的可逆元素。這是我們的小組 $ G_n $ .
所以我們有以下情況：
- $ G_1 $ 和 $ G_2 $ 都是的子群 $ Er $ ，因此可能有順序 $ r $ 或者 $ r^2 $ .
- $ G_n $ 一直訂購 $ r $ ，不多也不少。
在這一點上，我們必須選擇我們的組，以便我們獲得一些理想的屬性：
- $ G_1 $ 和 $ G_2 $ 都有秩序 $ r $ .
- 很容易將任意數據消息散列成 $ G_2 $ （即我們可以“隨機”生成元素 $ G_2 $ 在不知道結果點相對於給定生成器的離散對數的情況下 $ G_2 $ ).
- 存在一個單向非平凡態射 $ G_2 $ 到 $ G_1 $ ：這是一個線性函式，輸出值 $ G_1 $ , 這樣可以實現 0 以外的值，該函式很容易計算，但它的逆在計算上是不可行的。
不幸的是，我們不能同時擁有所有三個屬性。我們最終得到以下通常的選擇：
- 我們使用嵌入度的超奇異曲線 $ 2 $ . $ G_1 $ 是 $ Er $ （這 $ r $ -基本場中曲線上的扭轉點，而不是擴展場）。 $ G_2 $ 是同一組；為了計算配對，我們首先映射 $ G_2 $ 進入另一個子組 $ Er $ 通過失真圖（如果 Weil 或 Tate 配對的兩個操作數都來自未擴展場上的曲線，則配對輸出始終為 1，因此微不足道）。易於計算的失真貼圖很少見，但對於超奇異曲線，我們有一些。對於那種場景， $ G_1 $ , $ G_2 $ 和 $ G_n $ 都有相同的順序 $ r $ ; 很容易將數據散列成 $ G_2 $ ; 之間的同構 $ G_1 $ 和 $ G_2 $ 很容易在兩個方向上計算，因為它們是同一組。
- 我們使用非超奇異曲線。 $ G_1 $ 是 $ Er $ 和 $ G_2 $ 是一個子群 $ Er $ 由傳統的產生 $ r $ -扭力點（不是在 $ G_1 $ ); 因此， $ G_1 $ 和 $ G_2 $ 都有秩序 $ r $ . 我們不知道如何將點散列到 $ G_2 $ . 一點的弗羅貝尼烏斯軌跡 $ P = (X, Y) $ 定義為：
$$ \phi(X,Y) = \sum_{i=0}^{k-1} (X^{q^i}, Y^{q^i}) $$ （它是橢圓曲線點的總和，這些點中的每一個都是通過取輸入點的座標得到的，乘以冪 $ i $ ). $ \phi $ 恰好是從 $ G_2 $ 到 $ G_1 $ ，並且似乎很難反轉。
- 我們使用非超奇異曲線。 $ G_1 $ 是 $ Er $ . $ G_2 $ 是的子集 $ Er $ 由點組成 $ P $ 這樣 $ \phi(P) = 0 $ （“跟踪零點”的集合）。 $ G_2 $ 是一組順序 $ r $ 我們知道如何將點散列到 $ G_2 $ . 然而，我們不知道任何容易計算的非平凡態射 $ G_2 $ 到 $ G_1 $ ，或從 $ G_1 $ 到 $ G_2 $ .
- 我們使用非超奇異曲線。 $ G_2 $ 是完整的 $ Er $ ; 因此，它有秩序 $ r^2 $ . $ G_1 $ 是任何子群 $ G_2 $ （按順序 $ r $ )，可能 $ G_2 $ 本身（有序的 $ r^2 $ ）。很容易散列成 $ G_2 $ .
考慮配對的一種方式是配對是一種產品。如果我們有一個小組 $ G $ 加上一個“加法”，我們可以找到一對元素對 $ G $ 成元素 $ G $ 本身，那麼該配對的行為就像乘法在加法方面的行為一樣（順便說一下，它會完全破壞組中的 Diffie-Hellman $ G $ ）。所以“自然”的情況真的是這樣 $ G_1 $ , $ G_2 $ 和 $ G_n $ 都有相同的順序。