2.1 楕円曲線

楕円，超楕円曲線上のペアリング表現

Representations of Pairings on the Ellptic and Hyperelliptic Curves

数学専攻　小出裕KOIDE Yu 概 要

本発表では，暗号理論において近年著しい研究成果が出ている楕円曲線，及び超楕円曲線上のペアリング理 論を紹介する．具体的には，楕円曲線上のWeil^{ペアリング，}Tate(-Lichtenbaum)^{ペアリング，そして}Ate^ペ アリング及び，超楕円曲線上のAteペアリングを紹介する．代数幾何学の暗号理論への応用としての研究課題 を記した．

1 ^研究目的

ペアリング演算は，べき乗剰余演算や楕円曲線の点のスカラー倍算等の演算アルゴリズムに比べ，計 算コストを多分に要する．そこで，それを減らす研究がなされている．

その研究の一つの方向性としては，最も一般的なペアリング演算であるMiller^{アルゴリズムのループ} 回数を減らすようなペアリング表現を求めるものである．その研究の成果が，Eta^{ペアリング}([2])^や，

(twisted) Ateペアリング([6],[5])などである．

2 ^{数学的準備}

2.1 ^楕円曲線

体F_{q上の楕円曲線}

E=F_q : y² =x³+ax+b

ここで，a; b2F_qは4a³+ 27b² 6= 0 をみたし，無限遠点と呼ばれる点O ^{も併せて考えている．}

èK-有理点：

E(K) =fP 2E jP = (x; y) x; y2Kg èn-^{等分点全体の集合：}

E[n] =fP 2E(K) jnP =Og

2.2 ^{超楕円曲線}

種数g^{の超楕円曲線}

C : y²+h(x)y =f(x):

但し，h(x); f(x)2k[x]；degh(x)îg; degf(x) = 2g+ 1 をみたす．

種数gの超楕円曲線CのJacobi多様体；

J(C) = Div⁰(C)=ò: 但し，

Div⁰(C) =fD2Div(C) jD=X

P

nP(P);X

P

nP = 0g:

D1 òD2() 9f 2F_q(C)^É : D1ÄD2 = div(f):

èK-有理点全体：JF_q(C).

èr-^{等分点全体の集合}: J(C)[r] =fD2J(C) jrD = 0g.

1

3 ^{ペアリング}

G1とG2を元の位数がnであるアーベル群とする．またG3を位数nの巡回群とする．

ペアリングe:G1ÇG2 Ä!G3

è双線型

e(P1+P2; Q) =e(P1; Q)e(P2; Q) ande(P; Q1+Q2) =e(P; Q1)e(P; Q2) è非退化

e(P; Q) = 1 (8Q) =)P = 0 ande(P; Q) = 1 (8P) =)Q= 0 ここで，P; P1; P22G1，Q; Q1; Q2 2G2 とする．

3.1 Weil ^{ペアリング}

èn2N: (n; q) = 1. P; Q2E[n]に対して，

DP; DQ : DP ò(P)Ä(O); DQ ò(Q)Ä(O); SuppDP \SuppDQ=;:

è関数fP; gQ : (fP) =nDP; (gQ) =nDQ:

èWeilペアリング；en : E[n]ÇE[n]Ä!ñn ; (P; Q)7Ä! fP(DQ) gQ(DP):

3.2 Tate(-Lichtenbaum) ^{ペアリング}

èk2N: 埋め込み次数; F

q^k =F_q(ñn):

èP 2E[n](F_qk) ^{とすると，関数}f : (f) =n(P)Än(O) ^{が存在する．}

èQ2E(F

q^k) とすると，因子D : Dò(Q)Ä(O); Supp(f)\SuppD=;が存在する．

èTate(-Lichtenbaum) ^{ペアリング}; ún : E[n](F

q^k)ÇE(F

q^k)=nE(F

q^k)Ä!ñn

(P; Q+nE(F

q^k))7Ä!f(D)^qkÄ1n

3.3 Ate ^{ペアリング}

èôq：楕円曲線E=F_{q の間の}q乗フロベニウス自己準同型．

{ G₁=E[n]\Ker(ôqÄ[1])^． { G₂=E[n]\Ker(ôqÄ[q])^． èúr: Tate(-Lichtenbaum)^{ペアリング．}

è正の整数T：T ëq (modr).

2

èN = (T^kÄ1; q^kÄ1). L= T^kÄ1 N . ècT =PkÄ1

i=0 T^kÄ1Äiqⁱëkq^kÄ1 mod r.

èAte ペアリング；

aT : G₂ÇG₁ Ä!ñr

(Q; P)7Ä!f_T;Q(P)^{cT(qkÄN 1)}: èTate(-Litchenbaum)ペアリングとの関係；

úr(Q; P)^L=aT(Q; P):

3.4 ^超楕円的 Tate(-Lichtenbaum) ^{ペアリング}

èr :rj#JF_q(C)をみたす大きな素数． k :埋め込み次数 èfr;D12F_qk(C)^É: ^因子類D1 2JF

qk(C)[r]^{に対して，}div(fr;D1) =rD1をみたす. è超楕円曲線C上のTate(-Lichtenbaum)ペアリング；

úr : JF

qk(C)[r]ÇJF

qk(C)=rJF

qk(C)Ä!ñr

(D1; D2)7Ä!f_r;D1(D2)^qkÄ1N :

3.5 ^超楕円的 Ate ^{ペアリング}

èû: Jacobi多様体J(C)の間のq乗フロベニウス自己準同型．

{ G₁=J(C)[r]\Ker(ûÄ[1]) { G₂=J(C)[r]\Ker(ûÄ[q])

èD2=ö(D2) : ^因子類D2における唯一の被約因子．

è^種数g^{の超楕円曲線}C^のAte ^{ペアリング ；}

a : G₂ÇG₁Ä!ñr

(D2; D1)7Ä!fq;D2(D1):

èTate(-Lichtenbaum)ペアリングとの関係 ；

úr(D2; D1) =a(D2; D1)^kqkÄ1:

4 ^研究課題

ペアリング理論における研究課題としては，[1] 等で認識されている．本節では，それらには言及せ ず，代数幾何学の暗号理論への応用という視点で研究課題，または研究の方向性について言及する．

3

è^{超楕円曲線上の}twisted Ate ペアリングの表現に関する数学的証明；超楕円曲線上のtwisted Ate ペアリングは，F.Zhang^により，[11]で記されている．しかし，この証明には，数学的に誤りがあ る．そこで，[11]^の定理2に証明を与える必要がある．これは，コホモロジカルな手法によって解 決できると考えている．

è一般代数曲線のPicard群を用いたペアリングの構成；三浦晋司氏により提案されたC_ab曲線の

Picard群の具体的な表現を求め，(^超)楕円曲線上のペアリング演算アルゴリズムに匹敵するよう

な演算アルゴリズムを設計する([10])．注意しなければいけないのは，種数の大きな曲線に対して，

指数計算法という攻撃が有効に働くことが知られていることに注意しなければならない．

èアーベル多様体や有限群スキームの暗号理論への応用；楕円曲線や超楕円曲線のJacobi^{多様体は，}

アーベル多様体であり，群スキームである．そこで，アーベル多様体や群スキームの理論を俯瞰し て，暗号系に適する群を見つける．このことによって，暗号系に利用できる群の可能性が拡がる ことが期待される．

参考文献

[1] J. Balakrishnan et al. Pairings on Hyperelliptic Curves. jp.arXiv.org e-Print 2009.

http://jp.arxiv.org/abs/0908.3731

[2] P.S.J.M. Barreto, S.Galbraith, C. ìOh ìEigeartaigh, and M.Scott. Eécient Pairing Computation on Supersingular Abelian Varieties. Designs, Codes and Crypography 42(2007), 239-271.

[3] D. Boneh, M.Franklin. Identity- Based Encryption from the Weil Pairing. CRYPTO2001.

LNCS2139, pp.213-229, 2001.

[4] D. Boneh, B. Lynn, and H. Shacham. Short Signatures from the Weil Pairing. Journal of Cryp- tology 17(2004),no.4, 297-319.

[5] R. Granger, F. Hess, R. Oyono, N. Thìeriault, and F. Vercauteren. Ate Pairing on Hyperelliptic Curves. Asvances in Cryptology - Eurocrypt 2007. LNCS,vol.4515:419-436. Springer-Verlag. 2007.

[6] F.Hess, N.Smart and F.Vercauteren. The Eta Pairing Revisited. IEEE Transactions on Informa- tion Theory, vol 52:4595-4602, Oct. 2006.

[7] A. Joux. A One Round Protocol for tripartite Diée-Hellman. Journal of Cryptology 17(2004),no.4, 263-276

[8] A.Menezes, T.Okamoto, S.Vanstone. Reducing elliptic curve logarithms to logarithms in a ånite åeld. IEEE Transactions on Information Theory, 39; 1639-1646.1993.

[9] R.Sakai, K. Ohgishi, and M.Kasahara. Cryptosystems Based on Pairing. SCIS2000,C20,2000.

[10] 吉野絵美，金子晃，三浦晋示．C34曲線上のペアリング．SCIS 2008, 2008.

[11] F. Zhang. Twisted Ate Pairing on Hyperelliptic Curves and Applications. Preprint, 2008.

4