Cab 曲線上のペアリングと暗号への応用
吉野 絵美

1（指導教官：金子 晃）

はじめにC 上の K 有理点の集合を M (X, Y ) = 0 の K における解全体と無限遠点 P∞ からなる集合と定め，1990 年代初頭に楕円曲線暗号の攻撃手段として登場したC(K) := {(X, Y ) ∈ K × K | M (X, Y ) = 0} ∪ {P∞ }ペアリングは，暗号プロトコルの構成手段としての利用価値を見出されて後，非常に大きな関心を集める主題へと急で表す．特に K = Fq のとき C(Fq ) = C と記す．
速な成長を遂げた．そして現在，従来は実現不可能と思われていた暗号プロトコルがペアリングの性質を利用するこ
3 Cab 曲線上のペアリングとで，現実的な方式として数多く提案されている．それに伴い，ペアリングを暗号へ応用した際の安全性や，ペアリ曲線 C の因子類群をングの計算の効率性もまた詳しく調べる必要が生じている．
JC := Div0C /PrincC
その中で，楕円曲線より高い種数を持つ超楕円曲線上でのペアリングを暗号へ応用する提案が自然になされた．本稿
0
では，更に楕円曲線・超楕円曲線の一般化である Cab 曲線 とおき，因子 D ∈ DivC に対応する因子類を D̄ ∈ JC で表上でのペアリング及び，その実装方法について考察する． す．また，座標環 K[C] のイデアル類群を

2

Cab 曲線

H(K[C]) := I(K[C])/P(K[C])

K を任意の体とするとき K で K の代数閉体を表す．
定義 1 a, b ∈ N を 2 ≤ a < b を満たす互いに素な自然数とする．任意の有限体 Fq (q = pl ，p は素数 ) 上の次の形の多項式を定義方程式に持つ曲線を Cab 曲線と呼ぶ；∑M (X, Y ) :=λi,j X i Y j ，ai+bj≤abただし λi,j ∈ Fq , λ0,a ̸= 0, λb,0 ̸= 0．

Cab 曲線 M (X, Y ) = 0 の表示をYa+∑

λab−ai−bj X i Y jとおき，I ∈ I(K[C]) に対応するイデアル類を I¯ ∈ H(K[C])で表す．H(K[C]) の各同値類はその代表元として座標環
K[C] のイデアルを選ぶことができる．実際，各 I ∈ I(K[C])に対して，0 でない f ∈ I を任意に取ると，(f )I −1 ⊂ K[C]より 0 でない有理関数 h ∈ I −1 を多項式関数 f h ∈ K[C] の無限遠点 P∞ での極位数が最小になるように選ぶ．このような h は f の取り方に依らず，0 でない定数倍を除いて一意に決まる．この h を I の被約化関数と呼び，I と同じイデアル類に属する K[C] のイデアル (h)I ⊂ K[C] を I の被約イデアルと呼ぶ．I¯ ∈ H(K[C]) の対応する被約イデアルを ρ(I) ⊂ K[C] で表す．集合 ρ(H(K[C])) に

ρ(I¯1 ) ⊙ ρ(I¯2 ) := ρ(I¯1 I¯2 )ai+bj<ab,i≥0,j≥1= Xb +∑

λab−ai X i ，ただしλi ∈ Fq ．

0≤i<bとして演算 ⊙ を定義する．n ∈ Z と I ∈ I(K[C]) に対して

I ⊙n := ρ(I¯n )と変形すれば (a, b) = (2, 3) のとき楕円曲線の Weierstrassの標準形と一致し，(a, b) = (2, 2g + 1) のときは種数が g 以下の超楕円曲線の標準形となる．以下，M (X, Y ) は非特異（即ち，M (X, Y ) = MX (X, Y ) = MY (X, Y ) = 0 を満たす
(X, Y ) ∈ Fq × Fq は存在しない）とし，C を M (X, Y ) で定義された Cab 曲線として固定する．このとき，曲線 C の種数は g = (a − 1)(b − 1)/2 に等しい．
K を Fq の任意の拡大体とする．X, Y を形式的文字とする
K 上の多項式環 K[X, Y ] の剰余環とし，I n の被約化関数を gn,I ∈ K(C) とするとき hn,I =1/gn,I ∈ K(C) と書くことにする．即ち，I n = (hn,I )I ⊙nである．曲線 C 上の因子類群とイデアル類群は自然な対応
D 7→ {r ∈ K(C) | ordP r ≥ −ordP (D) ∀P ∈ C \ {P∞ }}によって，同型になる．r を，H(K[C]) の位数の素因数でq と互いに素なものとする．k を（r に関する）埋め込み次数（すなわち r | (q k − 1) を満たす最小の k ∈ Z）とする．従って，1 の原始 r 乗根のなす群 µr は Fqk に含まれる．
H(Fqk (C)) の r 捩れ元全体をK[C] := K[x, y] = K[X, Y ]/(M (X, Y ))H(Fqk (C))[r] := {I¯ ∈ H(Fqk (C)) | ρ(I¯r ) = 1}

を K 上の C の座標環と呼ぶ．ここで (M (X, Y )) は多項式
M (X, Y ) ∈ K[X, Y ] で生成される K[X, Y ] のイデアルを表す．Fq [C] の元を C 上の多項式関数と呼ぶ．M (X, Y ) はFq [X, Y ] において既約であることが示せ，従って，K[C] は整域であることがわかる．座標環 K[x, y] の商体を K(x, y) =K(C) と書いて K 上の C の関数体と呼ぶ．Fq (C) の元を C上の有理関数と呼ぶ．

とおく．このとき Tate-Lichtenbaum ペアリング が welldeﬁned な非退化双線形写像⟨ , ⟩r : H(Fqk (C))[r] × JC (Fqk )/rJC (Fqk ) → F∗qk /(F∗qk )rとして次のように定義できる．I¯1 ∈ H(Fqk (C))[r]，D̄2 ∈JC (Fqk ) に対して I1 ∈ I¯1 ，D2 ∈ D̄2 が supp(I1 ) ∩supp(D2 ) = ∅ を満たすとする．このとき，hr,I1 ∈ Fqk (C)∗は (hr,I1 ) = I1r を満たす．このとき，I¯1 と D̄2 の TateLichtenbaum ペアリングは∏⟨I¯1 , D̄2 ⟩r ≡ hr,I1 (D2 ) :=hr,I1 (P )ordP (D2 ) ．
P ∈C

定義 2 I を可逆な K[C] のイデアルとする．以下の条件を満たす関数のペア {f (x), u(x, y)} を被約 T-基底と呼ぶ；

1. {f (x), u(x, y)} は T-基底2. f (x) ∈ I はモニックかつ I ∩ K[x] で Cab 次数最小
3. u(x, y) ∈ I はモニックかつ (f 2 , u) = I を満たし，(f 2 , u) = I を満たす中で Cab 次数最小

ここで，≡ は (F∗qk )r を法として等しいということを意味す
上の定義 2 において，f (x) ∈ I ∩ K[x] は，I に対して一意る．因子 D2 の次数が 0 なので，hr,I1 のゼロでない定数倍に決まるが，u(x, y) ∈ I は一般には一意でないことに注意は相殺されるので，この結果は hr,I1 の選び方によらない．
する必要がある．Mumford 表現を用いた効率的な超楕円曲ペアリングの計算結果が剰余類ではなく，一意に決まるよ
線上の群演算のアルゴリズムが T-基底を利用することで，う修正したペアリング e( , ) を被約 Tate-Lichtenbaum ペ
Cab 曲線に対して拡張できる．このことは次に挙げる補題
アリングと呼び，次のように定義する；
から導かれる．
k(q−1)/r∗e(I¯1 , D̄2 ) = ⟨I¯1 , D̄2 ⟩r∈ µr ⊂ Fqk ．
補題 2 {f (x), u(x, y)} を被約イデアル I の被約 T-基底とする．f (x) ∈ K[x] を互いに共通因子を持たない f1 (x),ペアリングの計算，即ち hr,I1 (D2 ) を求めるアルゴリズムを
f2 (x) ∈ K[x] の積 f (x) = f1 (x)f2 (x) で書けているとする．
以下に与える．
このとき (f (x), u(x, y)) = (f 2 (x), u(x, y)) が成り立つことアルゴリズム 1PMiller のアルゴリズムと，(f1 (x), u(x, y)) = (f12 (x), u(x, y)) かつ (f2 (x), u(x, y))j¯1 ∈ H(Fqk (C)), = (f 2 (x), u(x, y)) が成り立つことは同値．
入力：N ∋ n = wn2n∈{0,1},n=1,Ijjwj=02

D̄2 ∈ JC (Fqk ), I¯1 ,D̄2 ∈ JC の代表元で supp(I1 ) ∩ supp(D2 ) = ∅なる I1 ∈ I(Fqk (C)), D2 ∈ Div0C
出力：hn,I1 (D2 )I ← I1 , c ← 1for j = w − 1 down to 0 doI ← I ⊙2c ← c2 GI,I (D2 )if nj = 1 thenI ← I ⊙ I1c ← cGI,I1 (D2 )end ifend for
Return c4

補題 3 {f (x), u(x, y)} を被約イデアルの被約 T-基底とする．f (x) ∈ K[x] を互いに共通因子を持たない f1 (x),f2 (x) ∈ K[x] の積 f (x) = f1 (x)f2 (x) で書けているとする．
このとき(f (x), u(x, y)) = (f1 (x), u(x, y))(f2 (x), u(x, y))が成り立つ．
補題 4 {f (x), u(x, y)}, {h(x), v(x, y)} をそれぞれ異なる被約イデアルの被約 T-基底とする．f (x),h(x) は共通因子を持たないとし，a(x), b(x) ∈ K[x] で a(x)f (x) + b(x)h(x) = 1と書けているとすると

T-基底ペアリングを実際に暗号へ応用する為には，ペアリングが定義されている群の演算が効率的に行えることが必要である．曲線 C 上の因子類群の各イデアル類は代表元に K[C]のイデアルを持つので，因子類群とイデアル類群の自然な対応によって因子類群の計算を，イデアル計算を用いて実現出来る．Cab 曲線に対する計算に対しては従来，多項式環の任意のイデアルが持つ Gröbner 基底が利用されていた．一方で，超楕円曲線の場合では，各因子類を一変数多項式のペアで表すことが出来る（Mumford 表現）．Cab 曲線の各因子類を Gröbner 基底を用いて表現すると最大 a 個の元が必要となり，超楕円曲線と Cab 曲線との計算効率に大きな差が出来てしまう．しかし，次の補題から K[C] のイデアルは高々2 元で生成されることが保証されているので，Gröbner基底を用いずに各因子類を表現することを考えたい．
補題 1 I ∈ I(K[C]) を可逆な分数イデアルとすると，任意に選んだ 0 でない u ∈ I に対して，v ∈ I が存在してI = (u, v) とできる．
上の補題 1 における 0 ̸= u は任意に選んでよいので，特に I ∩ K[x] から取ることができる．従って各 I ∈ I(K[C])に対して 0 ̸= f (x) ∈ K[x] と 0 ̸= u(x, y) ∈ K(x, y) でI = (f (x), u(x, y)) なるものが存在する．このように一方がx だけの式からなる I の２元の生成系 {f (x), u(x, y)} を T基底と呼ぶ．

(f (x), u(x, y))(h(x), v(x, y))= (f (x)h(x), a(x)f (x)v(x, y) + b(x)h(x)u(x, y))が成り立つ．
補題 5 {f (x), u(x, y)}, {h(x), v(x, y)} をそれぞれ被約イデアルの被約 T-基底とする．K[C] のイデアル (f (x)),(h(x)) の根基が等しい（即ち，f (x) と h(x) は同じ因子しか持たない）とすると(f (x), u(x, y))(h(x), v(x, y))= (f (x)h(x), u(x, y)v(x, y))が成り立つ．

5

まとめと今後の課題

Cab 曲線上の群に対してペアリングを構成し，T-基底を導入することで，ペアリング計算を高速化することを提案した．今後は，詳細なアルゴリズムを構成し，より効率的な計算方法を考えるとともに，楕円・超楕円曲線上のペアリングとの比較も行っていく．

参考文献[1] Henri Cohen and Gerhard Frey, 「Handbook of Elliptic and Hyperelliptic Curve Cryptography」, Chapman &Hall/CRC，2006[2] 三浦晋示,“アフィン代数曲線上の線形符号,” 電子情報通信学会論文誌 (A)，Vol.J81-A,no.10,pp.1398-1421,Oct.1998