22331Pairing-based cryptography and construction of pairing-friendly
elliptic and hyperelliptic curves()

p を素数, C を Fp 上定義された種数 g の超楕円曲線, JC を C のヤコビ多様体, JC (Fp ) をヤコビ群, JC [] を -ねじれ点のなす JC の部分群とする. JC 上の Weil pairing は次のような双線形・非退化写像である.
∗e : JC [] × JC [] → µ ⊂ Fp .

ここで,  は素数, は µ は 1 の  乗根全体のなす部分群である. また, µ ⊂ F∗pk となるような, 最小の拡大次数 k を  に関する埋め込み次数という.
1984 年に Shamir により ID 情報を公開鍵とする Identity-based Encryption (IBE) が提案され,2001 年に Boneh と Franklin により Weil pairing を用いて IBE を効率よく実現するプロトコルが提案された. それから, Pairing-based cryptosytem (PBC) が注目され, 様々な安全性根拠に基づく暗号方式が多く提案されるようになった. 同時に, PBC に適した曲線の構成が必要となった. その安全性を保証するために次の条件が必要である.
1. JC (Fp ) の素数位数部分群の位数  が適度に大きく, JC [] 離散対数問題が計算困難であること.
2. pk が適度に大きく, F∗pk 上の離散対数問題が計算困難であること.
また, 実装の観点から,
3. 埋め込み次数 k が適切に小さいこと.
4. ρ = g log p/ log  が適切に小さいこと.という条件を満たすことが求められる. これらの条件を満たす曲線を pairing-friendly という.
χ(t) を C の p-乗 Frobenius 写像の特性多項式としたとき, JC が  に関する埋め込み次数 k(> 1)を持つための条件はχ(1) ≡ 0

Φk (q) ≡ 0(mod )(mod )である.
pairing-friendly 曲線の構成法に関する既存の研究には, 楕円曲線については Miyaji らによるMNT 曲線, Cocks-Pinch 法, Brezing-Weng 法, Freeman らによる cyclotomic family などがある.
超楕円曲線については, Freeman らの構成法 Kawazoe, Takahashi らの構成法がある. Freeman らは, 任意の埋め込み次数に対する種数 2 の pairing-friendly 超楕円曲線の構成を与えている. ρ 値は 8 程度である. また, 種数 2 の場合は, ある埋め込み次数に関しては, 6 ≤ ρ < 8 を達成している.
Kawazoe らの構成法では, y 2 = x5 + cx のタイプの種数 2 の超楕円曲線のヤコビ群の explicit な公式を与えその構成法は任意の埋め込み次数に対して 3 ≤ ρ ≤ 4 の構成法である. しかしながら,absolutely simple ではない. このように, 超楕円曲線に関しては, 構成法が少ない.
1

本論文では
1. Cheon の攻撃アルゴリズムを考慮した pairing-friendly 楕円曲線の構成法
2. y 2 = x5 + c, y 2 = x9 + cx のタイプの超楕円曲線の位数公式を用いた pairing-friendly な超楕円曲線の構成法について述べている.
2002 年に Mitsunari らにより, q-weak Diffie-Hellman 問題に基づいた traitor tracing schemeが提案された. また, 2004 年に Boneh と Boyen は, q-strong Diffie-Hellman 問題に基づいた shortsignature scheme を提案した. どちらの scheme も pairing 写像を用いている. 2006 年に, Cheonは q-weak/strong Diffie-Hellman 問題を効率よく解くアルゴリズムを提案した. このアルゴリズムは, 楕円曲線の部分群の位数を  としたとき,  − 1 または  + 1 の因子を用いた攻撃法である.
また, 2007 年に Kozaki らは, Cheon のアルゴリズムの改良版を与えた. このアルゴリズムは, 因√ /d + d 回の群演算で解くことがで
子 d|( − 1) に対して, q-weak Deffie-Hellman 問題を Oきる.
先に述べた cyclotomic family は, 位数を表す多項式を円分多項式 (x) で与えているため, (x)−1は可約である. よって, ある整数 x0 に対して,  = (x0 ) が素数となるとき,  − 1,  + 1 の因子を考慮した楕円曲線の構成が必要になる. 本論文では, ρ の値を小さくしたまま, 位数を表す円分多項式の次数の小さくした構成法を与え, Cheon のアルゴリズムに対する安全性を保つために因子の満たすべき条件の考察を行い構成アルゴリズムを与えた. そのアルゴリズムで用いた, pairingfriendly√ 楕円曲線の構成法の特徴を以下に述べる. Freeman らの cyclotomic family では ρ が小さ
く, −D, ζk ∈ Q(ζhk ) となるような円分体を考え, nk 次円分多項式 Φhk (x) を位数を表す式 (x)として用いている. 筆者の構成法では, 埋め込み次数 k = 2n に対し円分体の拡大を行わずに, ρ の値を (x) = Φk (x) となるように工夫を行った. ρ の値は, ρ ∼ (n + 2)/(n − 1) であり, 特に, n ≡ 1(mod 4) のとき, ρ ∼ (n + 1)/ϕ(n − 1) である. この値は, Freeman らの cyclotomic family の ρ 値と同じ, あるいは同程度を実現している. これらにより, Cheon のアルゴリズムに対してできるだ
け安全性を損なわないような曲線を Freeman らの構成法より多く生成できることを計算実験により示した.
また本論文では, y 2 = x5 + c, y 2 = x9 + cx の形の pairing-friendly 超楕円曲線の構成法も与えている. その構成法とは, 位数公式を用いた方法である. 以下, 構成法について述べる.
p を奇素数とする. h を正整数, τ ∈ {0, 1}, c ∈ F∗p としたとき, Hh,τ,c を y 2 = xτ (xh + c) で定義される超楕円曲線とする. そして, Hh,τ,c のヤコビ多様体を Jh,τ,c とする. まず, 超楕円曲線
Hh,τ,c のヤコビ群の位数公式を求める. Jacobstahl sumφh,r (c) = x∈F∗r η2 (x)η2 (xh + c) を用いp

ると, Hh,τ,c 上の Fpr 有理点の集合 Hh,τ,c (Fpr ) の濃度は次のように表すことができる.

#Hh,0,c (Fpr ) = pr + 1 + η2 (c)(φh,r (c−1 ) + 1)
#Hh,1,c (Fpr ) = pr + 1 + φh,r (c)また, 種数 2 の超楕円曲線の p-乗 Frobenius 写像の特性多項式は χ(t) = t4 − s1 t3 + s2 t2 − ps1 t + p2 .
で表され, そのヤコビ群の位数は χ(1) であることが知られている. よって #J5,0,c は #J5,0,c (Fp ) =χ(1) = s2 − s1 (p + 1) + p2 + 1 となる. さらに #H5,0,c (Fp ) と #H5,0,c (Fp2 ) は, この特性多項式の係数 s1 , s2 で表され, Jacobstahl sum を用いて s1 , s2 を表すことができる. ここで, p ≡ 1 (mod 2h)となる素数 p に対して, Haneda らの結果より,

φh,r (c) = (−1)

r−1

η̂(−1)η̂

h+1(c)h−1η̂ 2j (c)K(η 2j+1 )rj=0と計算することができるので, H5,0,c のヤコビ群の位数公式は, ある条件を満たす整数 u, v, z, w に2対して,χ(1) = u2 − 10uz + up + u + 15v 2 + 10vw − 20vz+5vp + 5v + 15w2 − 20wz + 5wp + 5w+5z 2 − 5zp − 5z + p2 + 1.と表すことができる. また, H8,1,c のヤコビ群の位数公式は, Haneda らにより, explicit な式が与えられている. この 2 つの公式を用いて, 種数 2 と 4 の pairing-friendly 超楕円曲線の条件をあげ,構成アルゴリズムを与えた. それぞれの ρ 値は, 前者は 8 程度, 後者は 16 程度と見積もることができる. また, これらのアルゴリズムを用いて, たくさんの曲線を構成することができた. 種数 4 のpairing-friendly 超楕円曲線の構成法としては今までで初めてのものである.

3