Pairings

它是雙線性配對的一個例子嗎?

  • May 27, 2022

考慮一個雙線性對 $ e: G_1 \times G_2 \rightarrow G_T $ . 讓我們假設, $ G_1 = G_2 = G_T = (\mathbb{Z}_n,+) $ , 即整數模的加法群 $ n $ 和 $ e(x,y) = xy $ 反對 $ n $ . 它不是雙線性映射的一個例子嗎?

$ G_1 = G_2 = G_T = (\mathbb{Z}_n,\ast) $ , 即整數模的乘法群 $ n $ 和 $ e(x,y) = y^x $ 反對 $ n $ ,它仍然是雙線性映射嗎?

是否可以定義其他雙線性映射 $ \mathbb{Z}_n $ ?

編輯


實際上我所有的問題都是理解Groth-Sahai 證明系統。在這裡,他們重鑄了一般方程以適應二次方程的形式。(請參閱下面突出顯示的部分)。但是,他們怎麼能說所有的地圖都帶有 $ f(x,y) = xy $ 反對 $ n $ 會滿足雙線性對的性質嗎?

在此處輸入圖像描述

在此處輸入圖像描述

不僅是 $ \mathbb G_1 = \mathbb G_2 = \mathbb G_T = \mathbb Z_p $ 和 $ e(x,y) = x \cdot y \pmod{p} $ “雙線性群”的一個範例(具有雙線性映射的三組群),但每個素數雙線性群都與這種形式中的一種同構。因此,原則上您想了解的有關此類組的任何資訊,都可以根據此範例進行計算。我以前自己用它作為一些協議的健全性檢查。

例如,雙線性群的 ECC 實現的安全性取決於以下事實: $ \mathbb Z_p $ 形式不是(被認為是)有效計算的。

當然,它在密碼學上是無用的——正如評論者所指出的那樣,離散日誌很容易。但是密碼學定義通常分為兩部分,功能和安全。例如,加密方案是具有正確性屬性的三元組(KeyGen、Enc、Dec);因此,Enc 和 Dec 是恆等映射的方案是一種加密方案。只有當我們在第二步中引入安全要求時,這個方案才被證明是缺乏的。這同樣適用於 $ \mathbb Z_p $ :它當然是一個“雙線性群”,但不是特別安全的群。

編輯:回答你的最後一個問題是否可以定義其他雙線性映射 $ (\mathbb Z_p, +) \times (\mathbb Z_p, +) $ : 注意 $ 1 $ 是一個生成器 $ \mathbb Z_p $ 所以 $ e(x,y) $ 完全決定了所有人 $ x,y $ 經過 $ e(1,1) $ . 如果你想要一個非退化的雙線性映射, $ e(1,1) $ 必須是生成器 $ \mathbb G_T = \mathbb Z_p $ 同樣,無論您選擇哪種生成器,您獲得的結構都是同構的。如果您放棄非退化要求,則將所有內容髮送到的地圖 $ 0 $ 是一個不同的,微不足道的雙線性。

通常,使用乘法組。回憶配對的定義時,它必須是雙線性的、非退化的且易於計算的。請注意,e(x,y)=xy 的定義可以解釋為外積。(xy = y+…+y: n-times) 而不是作為內部群律。

我同意 Maeher 的回答。第一個例子是雙線性對,但不是第二個,因為它不是對稱的。但是第一個範例不能用於加密協議。給定:x $ \ne 0\cdots $ 、mx、nx 和 sx,很容易計算 (mns).e(x,x)。例如,我們可以建構其他雙線性對,只需考慮所有滿足非退化的線性映射 u, v 和對 (x,y) -> u(x).u(y),可計算性是顯而易見的。使用乘法結構時,仍然滿足配對的定義,但不能用於密碼學,因為BDHP是微不足道的。

**編輯:**考慮最終結論, (x,y)->xy 不是配對。有什麼額外的建議嗎?

引用自:https://crypto.stackexchange.com/questions/22523