超楕円曲線上の Ate ペアリングについて Around Ate pairings on hyperlliptic curves

超楕円曲線上の Ate ペアリングについて Around Ate pairings on hyperlliptic curves

数学専攻 山口 将史

Masashi Yamaguchi

序

本論文は，有限体の上に定義された楕円曲線さらに超楕円曲線に関わるアルゴリズムについて論述され た論文

C.-A. Zhao, F. Zhang, J. Huang, A note on the Ate pairing

R. Granger, F. Hess, R. Oyono, N. Th´ eriault, F. Vercauteren, Ate pairing on hyperelliptic curves

Jacobi

Weil pairing

´ etale cohomology

Poincar´ e

duality

Weil

pairing

て盛んに研究されるようになった．さらに，有限体の上の楕円曲線あるいは代数曲線の

Jacobi

Tate pairing

Ate pairing

本論文では先行する総合報告ではふれられていなかった，Tate pairingや

Ate pairing

ElGamal

Weil paring

Jacobi

Tate paring，Miller

Ate paring

Miller

1 _準備

定義

1.1. C

F q

g

= p ⁿ (p

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

によって与えられるとしてよい．ここで，h, f

∈ F q [x], degh ≤ g, f

1

= 2g + 1

P _∞

定義

1.2. F q

K

C(K) = { (x, y) ∈ K × K | y ² + h(x)y = f(x) } ∪ { P _∞ }

C

K

定義

1.3. ι(x, y) = (x, − y − h(x))

ι : C(K) → C(K)

C

定義

1.4. C( F q )

D = ∑

P ∈ C( F

)

c P P

1

を

C

p ∈ Z

P

c P = 0．C

Div C

定義

1.5. D = ∑

P ∈ C( F

)

c P P

degD = ∑

P ∈ C( F

)

c P

と記し，

deg D

D

0

Div ⁰ _C

ord _P (D) = c _P

定義

1.6. D = ∑

P ∈ C( F

)

c P P

D = { P ∈ C( F q ) ; c P ̸ = 0 }

定義

1.7. φ(x, y) = (x ^q , y ^q )

φ : C( F q ) → C( F q )

F q

Frobenius

定義

1.8.

f ∈ F q (C) ^∗

div(f ) = ∑

P ∈ C( F

)

ord P (f )(P )

と定義する．ここで，ord

P (f )

P

f

)

f

Prin C = { div(f ) ; f ∈ F q (C) ^∗ }，J C = Div ⁰ _C /Prin C

C

D

命題

1.9. D ∈ Div C 0

とする．このとき，ρ(D)

∈ Div C 0

が存在して次が成立する．

(1) ρ(D) = D．

(2) ρ(D) = ε(D) − deg(ε(D))(P _∞ )．ここで，ε(D) =

∑ m

i=1

(P i )，m = deg(ε(D))，P i ̸ = P _∞

i ̸ = ι(P j ) (i ̸ = j)．

定義

1.10. ρ(D)

ρ(D)

D ∈ J C

命題

1.11. D 1

2 ∈ Div ⁰ _C

(1) ρ((D ₁ ) + ρ((D ₂ ) = ρ(D ₁ + D ₂ )．

(2) ε((D 1 ) + ε((D 2 ) = ε(D 1 + D 2 )．

定義

1.12. D ∈ Div ⁰ _C

∈ Z

[n]D = ρ(nD)

定義

1.13. f ∈ F _q

(C) ^∗

) = nD − [n]D

f _n,D

0

2

2 Tate-Lichtenbaum Pairing

定義

2.1. C

F q

#J C ( F q )

( ̸ = p)，k

r | (q ^k − 1)

1

2 ∈ Div ⁰ _C

1 ) ∩ supp(D ₂ ) = ∅

< D 1 , D 2 > r = f r,D

(D 2 )

< , > r : J C ( F q

)[r] × J C ( F q

)/rJ C ( F q

) → F ^∗ q

/( F ^∗ q

) ^r

定義

2.2. < , > _r

C

Tate-Lichtenbaum paring

補題

2.3. D 1 ∈ J C ( F q

)[r]，D 1 = ρ(D 1 )，D 2 ∈ J C ( F q

)

1 ) ∩ supp(ε(D 2 ))

< D 1 , D 2 > r ≡ f r,D

(ε(D 2 ))

Ate Pairing on hyperelliptic curves

定理

2.4. E

F q

#E( F q )

F q ) = q + 1 − t

= t − 1

∈ G 2 = E[r] ∩ Ker(φ − [q])

P ∈ G 1 = E[r] ∩ Ker(φ − [1])

(1)

(P, Q) 7→ f _{T ,Q} (P)

(2) k

T ^k − 1, q ^k − 1

^k − 1 = LN

e(Q, P ) ^L = f _{T ,Q} (P ) ^c(q

^{− 1)/N}

が成立する．ここで，c

=

k − 1

∑

i=0

T ^{k − a − i} q ⁱ ≡ kq ^{k − 1} mod r．

(3) r ∤ L

定理

2.5. C

F q

r

#J C ( F q )

G 2 = J C [r] ∩ Ker(φ − [q])，

G 1 = J C [r] ∩ Ker(φ − [1])

1 ) ∩ supp(D 2 ) = ∅

D 2 = ρ(D 2 ), D 1 ∈ D 1

(D 2 , D 1 ) 7→ f q,D

(D 1 )

a( , ) : G 2 × G 1 → µ r

は非退化で双線形である．さらに，被約

Tate-Lichtenbaum paring

e(D 2 , D 1 ) = a(D 2 , D 1 ) ^kq

によって与えられる．

定義

2.6. a( , ) : G 2 × G 1 → µ r

C

Ate paring

3

3 Miller _{のアルゴリズム}

楕円曲線上における

Miller

² = x ³ + ax + b

F q

(x, y)

O

E( F q )

以下，楕円曲線上における

Tate paring e

r

e : E( F q )[r] × E( F q

)/rE(F _q

) → µ r

e(P, Q) = f P (Q)

で定義される関数である．ここで

k

r | q ^k − 1

E( F q )[r] = { P ∈ E( F q ) | rP = O }，µ r = { x ∈ F q

| x ^r = 1 }

iP

jP

l _iP,jP

+ j)P

y

v _(i+j)P

f _h

div(f h ) = h(P) − (hP ) − (h − 1)(O)

f _i+j = f _i f _j l _iP,jP v (i+j)P

が得られる．

Miller

r ) = r(P ) − r(O)

paring

f _r

Miller

f := 1，V := P

:= s − 1

Step1

r

2

= n _s · 2 ^s + n _{s − 1} · 2 ^{s − 1} + · · · + n ₀ · 2 ⁰

s = { 0, 1 }．Step2

Step2

f := f ² · l _V,V

v 2V

:= 2V

Step3

n t = 1

:= f · l V,P

v _{V +P}

:= V + P

n t = 0

Step4

t ≥ 0

:= t − 1

t < 0

f

Miller

曲線の有理点を列挙するプログラム，楕円曲線上の点

P

n

f P

+ y + 0)

(x + y)

参考文献

[1]

[2]

[3]

[4] R.Granger，F.Hess，R.Oyono，N.Th´ eriault，F.Vercautren，Ate Paring on Hyperelliptic Curves [5] C.-A. Zhao, F. Zhang, J. Huang, A note on the Ate pairing，Journal of Information Security 2008

4