雙線性映射

文章目錄

• 雙線性映射
• • 1 離散對數系統
  • • 1.1 指標
    • 1.2 離散對數（DLP）
  • 2 雙線性映射
  • 3 Diffie-Hellman 問題（DHP）
  • • 3.1 Diffie-Hellman 密鑰交換
    • 3.2 q-Strong Diffie-Hellman（q-SDH）

1 離散對數系統

1.1 指標

定義：設 $p$ 是一素數，$a$ 是 $p$ 的原本根，則 $a,a^2,\dots ,a^{p?1}$ 產生出的 $1～p?1$ 之間所有的值，且每一值只出現一次，即對于 $?b\in \{1,\dots ,p?1\}$ 都唯一存在 $i(1\le i\le p?1)$ ，使得 $b\equiv a^{i}modp$ 。稱 $i$ 為模 $p$ 下以 $a$ 為底 $b$ 的指標，記作 $i=in{d}_{a,p}(b)$ 。

性質：（1） ${ind}_{a,p}(1)=0$ ；

? （2） ${ind}_{a,p}(a)=1$ 。

定理：若 $a^z\equiv a^{p}modp$ ，其中 $p$ 為素數，$a$ 為 $p$ 的原本根，則有 $z\equiv qmod\phi (p)$ 。

性質：（3）${ind}_{a,p}(xy)=[{ind}_{a,p}(x)+{ind}_{a,p}(y)]mod\phi (p)$ ；

? （4）${ind}_{a,p}(y^r)=[r\times {ind}_{a,p}(y)]mod\phi (p)$ 。

1.2 離散對數（DLP）

設 $p$ 是一素數，$a$ 是 $p$ 的原本根，則 $a,a^2,\dots ,a^{p?1}$ 產生出的 $1～p?1$ 之間所有的值，且每一值只出現一次，即對于 $?b\in \{1,\dots ,p?1\}$ 都唯一存在 $i(1\le i\le p?1)$ ，使得 $b\equiv a^{i}modp$ 。稱 $i$ 為模 $p$ 下以 $a$ 為底 $b$ 的離散對數，記作 $i\equiv {log}_a(b)(modp)$ 。

當 $a、p、i$ 已知時，用快指數算法可以比較容易的=地求出 $b$ ，但是如果已知 $a、b$ 和 $p$ ，求 $i$ 則非常困難。目前已知的最快的求離散對數算法的事件復雜度為： $O(exp(lnp{)}^{\frac{1}{3}}ln(lnp{)}^{\frac{2}{3}})$ 所以當 $p$ 很大時，該算法也不可行。

2 雙線性映射

設 $q$ 是一大素數，${\mathbb{G}}_1$ 和 ${\mathbb{G}}_2$ 是兩個階為 $q$ 的群，其上的運算分別為加法和乘法。${\mathbb{G}}_1$ 到 ${\mathbb{G}}_2$ 的雙線性映射 $e:{\mathbb{G}}_1\times {\mathbb{G}}_1\to {\mathbb{G}}_2$ ，滿足下面的性質：

（1）雙線性：如果對任意 $P,Q,R\in {\mathbb{G}}_1$ 和 $a,b\in Z$ ，有 $e(aP,bQ)=e{(P,Q)}^{ab}$ ，或 $e(P+Q,R)=e(P,R)?(Q,R)$ 和 $e(P,Q+R)=e(P,Q)?(P,R)$ ，那么就稱該映射為雙線性映射。

（2）非退化性：映射不把 $e:{\mathbb{G}}_1\times {\mathbb{G}}_1$ 中所有元素對（即序偶）映射到 ${\mathbb{G}}_2$ 中的單位元。由于 ${\mathbb{G}}_1、{\mathbb{G}}_2$ 都是階為素數的群，這意味著：如果 $P$ 是 ${\mathbb{G}}_1$ 的生成元，那么 $e(P,P)$ 就是 ${\mathbb{G}}_2$ 的生成元。

（3）可計算性：對任意 $P,Q\in {\mathbb{G}}_1$ ，存在一個有效算法計算 $e(P,Q)$ 。

3 Diffie-Hellman 問題（DHP）

3.1 Diffie-Hellman 密鑰交換

Diffie-Hellman 密鑰交換過程，其中 $p$ 是大素數，$a$ 是 $p$ 的本原根，$p$ 和 $a$ 作為公開的全程元素。用戶A選擇一個保密的隨機整數 $X_A$ ，并將 $Y_A=a^{X_A}modp$ 發送給用戶B。類似的，用戶B選擇一個保密隨機數 $X_B$ ，并將 $Y_B=a^{X_B}modp$ 發送給用戶A。然后A和B分別由 $K=Y_B^{X_A}modp$ 和 $K=Y_A^{X_B}modp$ 計算出的就是共享密鑰。

因為 $X_A,X_B$ 是保密的敵手只能得到 $p,a,Y_A,Y_B$ ，想要得到 $K$ ，則必須得到 $X_A,X_B$ 中的一個，這意味著要解離散對數。因此求 $K$ 是不可行的。

3.2 q-Strong Diffie-Hellman（q-SDH）

假設 $g$ 是 $\mathbb{G}$ 的生成元，$a\in {\mathbb{Z}}_p$ ，我們說如果給定 $q+1$ 元組 $(g,g^a,g^{a^2},\dots ,g^{a^q})$ ，計算一個對 $(g^{1/a+x},x)x\in {\mathbb{Z}}_p^{?}$ 是困難的。

總結

以上是生活随笔為你收集整理的双线性映射的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。