このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

はじめに

写像\hat{e}:G_{1}~\times~G_{1}~\to~\G_{2}

(1)\hat{e}(\alpha_{1}\alpha_{2},\beta)~\to~\hat{e}(\alpha_{1},\beta)~\cdot~\hat{e}(\alpha_{2},\beta)

(2)\hat{e}(\alpha,\beta)~=~\hat{e}(\beta,\alpha)

(3)\exists~\beta~\not=~1~\,s.t.\,~\hat{e}(\alpha,\beta)=1~\Rightarrow~\alpha~=~1

 このような性質を持つ\hat{e}は本当にあるのだろうか?

 G1がsupersingular楕円曲線、G2が有限体の乗法群なら、存在するという事実が発見されている。

Weilペアリングの定義

[定義]
n~\in~\mathbb{Z}^{+}~,~p~|~n

q~=~p^{k}n~|~p^{k}-1とする。

\mu_{n}~=~\bigl{~s~\in~\mathbb{F}_{q}~|~\zeta^{n}~=~1~\bigr} (#μn=n)

E[n]~\overset{\mathrm{def}}{=}~\bigl{~P~\in~E(\mathbb{F}_{q})~|~n~\cdot~P~=~\infty~\bigr}

とする。

 次の写像を考える。

en:E[n]×E[n]→μn

 これをWeilペアリング(Weil Pairing)と呼ぶ。

Weilペアリングの性質

[定理]Weilペアリングの性質

[1]Bilinearity
 ∀s,s1,s2,t,t1,t2∈E[n];
・en(s1+s2,t)=en(s1,t)・en(s2,t)
・en(s,t1+t2)=en(s,t1)・en(s,t2)

[2]Non-degenearacy(非退化)
・en(s,t)=1,∀t∈E[n]⇒s=∞
・en(s,t)=1,∀s∈E[n]⇒t=∞

[3]∀t∈E[n];en(t,t)=1

[4]∀s,t∈E[n];en(t,s)=en(s,t)-1

[考察1]この4つの性質を持った写像が存在することは証明されている。

[考察2]実際に効率的に作れるアルゴリズムもある。

DLPとWeilペアリングの関係

E[n]∋s0(≠∞)

E[n]~\rightarrow~\mathbb{F}_{q}^{\times} (∵ペアリングの性質より埋め込みできる)

 この写像の要素の対応は次の通り。

t~\mapsto~e_{n}~(s_{0},t)

[定理]E[n]上のDLPは、\mathbb{F}_{q}^{\times}上のDLPに帰着する。

 即ち、E[n]上のDLP≦\mathbb{F}_{q}^{\times}上のDLPとなる。「≦」は帰着の記号。

 これではわざわざ楕円曲線上で演算する意味がなく、素体\mathbb{F}_{p}の拡大体である\mathbb{F}_{q}上において乗法計算すれば済むことになる。ところが、数学的にはこのように帰着されてしまうが、計算量的には無意味な帰着となる。というのも、一般的に\mathbb{F}_{q}^{\times}は非常に大きいからだ。

 ただし、例外もある。

[定理]
「E:supersingular」⇒「\mathbb{F}_{q}が小さく取れる」

E~/~\mathbb{F}_{q}~\Rightarrow~E[n]~\subset~E~/~\mathbb{F}_{p^{6}}

参考文献

  • 授業ノート