このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
  • 追加された行はこの色です。
  • 削除された行はこの色です。
  • Weilペアリング へ行く。

*目次 [#a0372d49]

#contents


*はじめに [#ofeaa450]

写像&mimetex("\hat{e}:G_{1} \times G_{1} \to \G_{2}");

(1)&mimetex("\hat{e}(\alpha_{1}\alpha_{2},\beta) \to \hat{e}(\alpha_{1},\beta) \cdot \hat{e}(\alpha_{2},\beta)");

(2)&mimetex("\hat{e}(\alpha,\beta) = \hat{e}(\beta,\alpha)");

(3)&mimetex("\exists \beta \not= 1 \,s.t.\, \hat{e}(\alpha,\beta)=1 \Rightarrow \alpha = 1");

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

 GSUB{1};がsupersingular楕円曲線、GSUB{2};が有限体の乗法群なら、存在するという事実が発見されている。



*Weilペアリングの定義 [#nc131ac0]

[定義]~
&mimetex("n \in \mathbb{Z}^{+} , p | n");

&mimetex("q = p^{k}");を&mimetex("n | p^{k}-1");とする。

&mimetex("\mu_{n} = \bigl{ s \in \mathbb{F}_{q} | \zeta^{n} = 1 \bigr}"); (#μSUB{n};=n)

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

とする。

 次の写像を考える。

eSUB{n};:E[n]×E[n]→μSUB{n};

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


*Weilペアリングの性質 [#f3f46ff2]

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

[1]Bilinearity~
 ∀s,sSUB{1};,sSUB{2};,t,tSUB{1};,tSUB{2};∈E[n];~
・eSUB{n};(sSUB{1};+sSUB{2};,t)=eSUB{n};(sSUB{1};,t)・eSUB{n};(sSUB{2};,t)~
・eSUB{n};(s,tSUB{1};+tSUB{2};)=eSUB{n};(s,tSUB{1};)・eSUB{n};(s,tSUB{2};)

[2]Non-degenearacy(非退化)~
・eSUB{n};(s,t)=1,∀t∈E[n]⇒s=∞~
・eSUB{n};(s,t)=1,∀s∈E[n]⇒t=∞

[3]∀t∈E[n];eSUB{n};(t,t)=1

[4]∀s,t∈E[n];eSUB{n};(t,s)=eSUB{n};(s,t)SUP{-1};


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

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


*DLPとWeilペアリングの関係 [#e366a6f0]

E[n]∋sSUB{0};(≠∞)

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

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

&mimetex("t \mapsto e_{n} (s_{0},t)");

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

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

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

 ただし、例外もある。

[定理]~
「E:supersingular」⇒「&mimetex("\mathbb{F}_{q}");が小さく取れる」

&mimetex("E / \mathbb{F}_{q} \Rightarrow E[n] \subset E / \mathbb{F}_{p^{6}}");


*参考文献 [#y376565f]

-授業ノート