計算量弗ヒ教擦敬    指導教授呼㍗㌻教授

修士学位論文

題名手方〃川ペアリングヒ

      簡約丁肪己ペアりンゲの

      計算量弗ヒ教擦敬    指導教授呼㍗㌻教授

平成之千年五月ノ0目  提出

首都大学東京大学院

理工学研究科表疫椅毅舛羊専攻

学修番号／艀7㈹／7

氏名手野正伺

学位論文要旨（修士（理学））

論文著者名 平野 正樹

論文題名：平方Wei1ペアリングと簡約Tateペアリングの 計算量評価と数値実験

 近年，インターネットの普及と発展に伴い，デジタル化した情報が電子商取 引や電子マネーなど重大化してきた。この重大な情報を保護していくためにも，

暗号技術がなくてはならないものになってきている。

 現代暗号は共通鍵暗号と公開鍵暗号の二つに大きく分けられている．共通鍵 暗号で大きな問題であった事前の鍵共有を必要としない公開鍵暗号は今日広く 使われており，数多くの方式が提案されている．また，暗号を構成するうえで 素因数分解問題や離散対数問題等の整数論における古典的な問題が重要な役割 を担うということも注目されている．そのようななか，楕円曲線に基づく公開 鍵暗号が1980年代に発表された［3，5］．これは楕円曲線上の離散対数問題の

困難を安全性の根拠とした暗号で，その攻撃法の一つである指数計算法も適用 できないことから，たちまち研究されるようになった．しかし，1991年に楕円曲 線上の離散対数問題を有限体上の離散対数問題に変換するMOV攻撃が提案さ れ［4］，その後は楕円曲線のペアリングを暗号に利用する研究が進められるよ

うになった．

 本論文では，IDべ一ス公開鍵暗号および署名方式やこのMOV攻撃でも用い られる，楕円曲線の二点を有限体の乗法群に写す単射準同型写像，特にペアリ ングの計算の実験を行った．そのペアリングのなかでも今回はK．Eisentrager 等により提案された平方Wei1ペアリング（Wei1ペアリングの平方値）［2］と，簡 約Tateペアリング（Tateペアリングの値をべき乗したもの）についての計算量 評価と実験を行い比較検証した．なお，その理由としては平方Wei1ペアリング がWei1ペアリングよりも30％高速であり，Tateペアリングは平方Wei1ペアリ

ングよりも高速［1］だが，実用上必要とされる簡約Tateペアリングと平方 Wei1ペアリングの比較がされていなかったからである．

た埋め込み次数5〜20の範囲では，次のようになることがわかった．

・埋め込み次数が18，20と高次において，平方Wei1ペアリングは単純べき（反 復二乗法）の簡約Tateペアリングよりも高速である．

・埋め込み次数がいかなる場合でも簡約Tateペアリングのべき乗の効率化を 図ると平方Wei1ペアリングよりも高速である．

 考察としては，実験に至らなかったが埋め込み次数が奇数，特に素数がつ高 次の場合では簡約Tateペアリングのべき乗の効率を図るのは難しく，平方Wei1 ペアリングの方が高速であることが期待される．

参考文献

［11C．Antonio，田中覚，中村憲．平方ペアリングの実装効率について．日本応  用数理学会論文詩，vo1．18，No．4，pp．703−721．2008．

［21K．Eisentrager，K．Lauter，and P．Montgomery Improved Wei1and Tate  Pairingsおr E11iptic and−Hypere11iptic Curves，λ如。血肋血メ。 Mb血ゐθr  珊θoW畑ρ08ノα血，ANTSW，LNCS vo1．3076，pp．169・183．2004．

［3］Kob1itz，N．：E11iptic Curve Cryptosystems，M身肋θ一㎜∂地80戸Cb㎜ραね血。刀，

 48，pp．203−209．1987．

［4］1M［enezes，A．，Okamoto，T．and−Vanstone，S．：Reducing E11iptic Curve  Logarithms to Logarithms in a Finite Fie1d一，一㎜下土ans．IT，39，

 pp．1639−1646．1993．

［5］lMi11er，VS．：Use ofE11iptic Curvesin CryptographX Proc．ofCRYPT0 85，

 LNCS218，pp．417 426．1986．

平方Wei1ペアリングと簡約Tateペアリングの

      計算量評価と数値実験

平野 ^{正樹（首都大学東京）}

2012年1月10日

概要．本論文では，埋め込み次数が5〜20の楕円曲線における平方W6i1ペアリングと簡約 Tateペアリングの比較を実験および計算量の解析により行った．その結果，簡約Tateペア

リングの方でどのくらいべき乗の効率を考えるかによって，平方Wei1ペアリングの方が高 速になる場合があることがわかった．また，効率化を考えにくい埋め込み次数が素数のとき

は，平方Wei1ペアリングの方が有用であろうと期待される事が理論的，実験的にも確かめら

れた．

目次

1

2

3

4

5

6

2．1

2．2

2．3

3．1

3．2

3．3

3．4

3．5

3．6

3．7

4．1

4．2

はじめに

準備

ペアリング．．．．

Fina1Exponentiation．

平方ペアリング

利用した楕円曲線について 埋め込み次数5．．

埋め込み次数7．．

埋め込み次数9．．．

埋め込み次数11．

埋め込み次数12．

埋め込み次数18．

埋め込み次数20．．．．

計算機実験 アルゴリズム実験 実験結果．

計算量の解析

むすび

4

4 4 7 8

9 9 10 10 11 11 11 12

12 12 13

14

14

付録A 今回の実装で使用したアルゴリズム 17

1 はじめに

 近年，暗号利用を目的とした双線型ペアリングの効率的な計算研究が行われている．そ のなかでも，Eisentrager，Lauter，Montgomery［2］はWei1ペアリングおよびTateペア

リングの平方値（平方ペアリング）を高速に計算する手法をANTS VIで提案している．

さらにはAntonio，田中，中村［11により平方ペアリングにおける計算量が解析されてお り実験結果を保証する理論的結論も得られていて，平方Wei1ペアリングは既存のWei1ペ アリングよりも1．5倍程度高速であり，その一方で平方Tateペアリングは既存のTateペ アリングよりも決して高速ではないことが確認されている．また，Tateペアリングは平方 Wei1ペアリングよりも高速である．しかし，暗号の応用等のためにはTateペアリングに 最後にべき乗することが必要とされる．そこで今回は，素数やより高い埋め込み次数であ

る5〜20に関しての平方Wei1ペアリングと（Tateペアリングをべき乗した）簡約Tate ペアリングの実験比較を行った．

2準備

2．1ペアリング

 この節では，楕円曲線暗号におけるペアリングを説明する．ペアリングは簡単にいうと 楕円曲線のねじれ点二点を有限体の乗法群に写す関数で，IDべ一ス公開鍵暗号および署 名方式や楕円曲線の離散対数問題を有限体での離散対数問題に還元するMOV攻撃［51に 有効なものである．

定義2．1．G1，G2を加法に関してのアーベル群，G3を乗法に関してのアーベル群とする．

このときフ写像

       ε：GlXG2一一＞G3 が以下の条件全てを満たすとき，eをペアリングという．

．任意のP1，片∈G1，Q∈G2に対してe（P1＋易，Q）＝e（P1，Q）e（乃，ρ）．

．任意のP∈G1，Q1，Q2∈G2に対してe（P，Q1＋Q2）＝e（P，Q1）e（P，Q2）．

．任意のP∈G1∩G2に対してe（P，P）＝1．

．任意のQ∈G2に対して，e（P，ρ）＝1ならばP＝0である．

 qを素数べきとする．暗号で用いられるペアリングの入力は有限体1Fq上の楕円曲線の ねじれ点などを考えることになり，ペアリングの像は定義体Fqの拡大体に含まれる．像を 含む最小の拡大体の拡大次数を定義しなければならない．以下より，亙（Fq）を楕円曲線五 のFq有理点，珂ザ1を｛P∈五（lFq）けP＝0｝として，まず次のように定義する．

定義2．2．亙をFq上の楕円曲線，rをqと互いに素で井五（Fq）を割り切る素数とする．

このとき，ザψ一1となるような最小の正整数んを埋め込み次数という．

 そして，次の定理で埋め込み次数んでペアリングの像が亙ψに納まることを保証して

いる．

定理2↓ρα1α舳6mm㎝乞㎝，Ko脇zノ∬をlFq上の楕円曲線，グをqと互いに素で

井∬（lFq）を割り切る素数とする・なお，r＋q−1と仮定する・このとき，珂r1⊂五（Fqん）で あることとr Iψ＿1が成り立つ亨とは同値である．

定義2．3．五を亙q上の楕円曲線，rをgと互いに素で井田（Fq）を割り切る素数，んを埋 め込み次数とする．さらに，μ。を乗法群F〆上の1のr乗根全体のなす群とする．この

とき，

      ∫P（Q＋R）∫Q（一R）

     e、（＊，＊）：五［r］×亙［r］一一合μ、，  e、（P，Q）＝

       ∫P（R）∫Q（P−R）

をWei1ペアリングといい，

  ／・，・／。：五（㌦）［・1・五（F。馬）／画F。κ）一1F〆／（F〆）「，／P，Q／。＝∫P（Q）

をTateペアリングという．ただし，∫pは因子がr（P）一（rP）一（r−1）（0）である任意の 関数，Rは｛αP一うQ11＜α，6＜r｝のランダムな点としてよい．

 実際の暗号の利用で！よTateペアリングの計算値を一意とするために最後の結果を

（〆一1）／r乗する一この操作を一般に丘na1exponentiationという．そして，この丘na1 exponentiationを含めての関数

／・，・／！・為一1）／・：五（F，1）［・1・叩、1）／画F，1）→F，1＊，／則／！・L1）／「一∫。（Q）（・馬一1）／・

を簡約Tateペアリングという．

一般的にWei1ペアリングの計算はMi11erのアルゴリズム［6］により計算される．ここ では簡約Tateペアリングのアルゴリズムをあげておくことにする．

アルゴリズム1．簡約Tateペアリング．

入力：P∈五（Fq）［r1，P≠P。。，Q∈亙（Fq為）＼亙（Fq）・

     qL1

_{出力 〈P，Q〉、「}

1：T←P，∫←1．

2：for乞←L1og。（r）」一1down to0do

3：

4：

5：

6：

7：

8：

9：

10：

∫＝∫2・1T，T（Q）

T＝2T

9＝92・町（Q）

ifη＝1then

∫二∫・lT，P（Q）

 T＝T＋P

9＝9・ηT（Q）

end if 11：end for

12：ω←（∫／9）（・L1）／・

13：Retumω．

なお，このアルゴリズム内の1λ，Bは楕円曲線上の二点λ，Bを通る傾きmの直線，〜十B は点λ十Bを通る垂線としての関数である．これらの関数の値は，任意の点Qの座標を

（πQ，蜘）と与えたとき，

       zλ，B（Q）＝（μQ一服）一m（πQ一 A）

及び

      ｝十B（Q）＝ Q一 λ十B

で与えられる．

2．2  Fi na l Exponentiation

 Tateペアリングの暗号の応用のためには計算値を一意とするために最後に（〆＿1）／r 乗する丘nal exponentiationをしなければならない．具体的にはアルゴリズム1の12番

目のステップのことを指す．

 ここで丘na1exponentiationの効率を上げることを考える．まず，Φんを円周ん等分多項 式とする．んが偶数であれば（〆一1）／rを次のように3つのパートに分けて考えることが

でき，

        （qL1）／・＝（q冶／2−1）（（qん／2＋1）／Φん（q））（蚕ん（q）／ヅ）

となる．なお，外（q）がザによって割り切れることは次の定理からわかる．

定理2．2．んを正の整数，五をFq上の楕円曲線，ヅを井亙（lFq）を割り切る素数とする．

なお，r＋畑と仮定する．このとき，E／Fqがrに関する埋め込み次数んをもつことと，

Φん（q）≡0（modヅ）を満たすことは同値である．

証明．亙がrに関する埋め込み次数んをもっとする．このとき，r lψ一1，r＋qL1（1≦

乞＜ん）が成り立つ．〆一1＝nd■んΦd（ ）とrが素数であることによりr lΦん（q）となる．

 逆に，r IΦん（q）であるとr〆＿1なので，亙／Fqの埋め込み次数は高々んである．そ こで，r＋♂一1（1≦乞＜ん）であることを示す．まず，∫（ ）＝〆一1，lF＝・Z／rZとする．

このとき1Fは体である．r＋んなので，∫（π），∫ （ ）はF［ 1で互いに素である．ゆえに，∫は

 また，んが奇数の時には〆＿1をできるだけ項の少ないqの多項式の積に分解して考えた い．しかし，奇素数の時にはΦん（q）がqの多項式として既約なので，ψ＿1＝（q＿1）Φん（q）

の一回までしか分解できない．そして，分解したあとのrで割る部分はq進展開をして qのべき菜を指数とするところはフロベニウス写像を用いた．ここでんが素数の時で Φん（q）／グをg進展開してもqのべき乗指数が多く効率化が見込めないことがわかる．

2．3 平方ペアリング

 この節では平方ペアリングの公式と，実験した平方Wei1ペアリングのアルゴリズムを

紹介する．

定理2．3．標数が2でない体Fq上の楕円曲線において平方Tateペアリングおよび平方 Wei1ペアリングはそれぞれ

       〈則〉・一∫・（Q）

      ∫P（一Q）

      、、（則）・一（一1）・∫・（Q）∫・（一P）

       ∫P（一Q）∫Q（P）

で与えられる．

証明．Eisentrager［2］参照．

 そして，この公式から平方Wei1ペアリングのアルゴリズムは以下のようになる．

アルゴリズム2．平方Wei1ペアリング．

入力：P∈五（Fq）［r1，P≠ん，Q∈亙（Fqん）［r1＼亙（Fq）［r1・

出力：e、（只Q）2

1：Tく＿一P，8く一＿Q，∫く＿1，g÷＿1

2：for乞←L王。g2（r）」一1down to0d−o 3：∫＝∫2・1T，。（Q）1・，・（一P）

4：9＝92・1T，T（一ρ）18，8（P）

5： T＝2T，8＝28

6：  ifη＝1七hen

7： ∫＝∫・lT，P（Q）lT，Q（一P）

8： 9＝9・18，P（1Q）18，Q（P）

9： T＝T＋P，8＝3＋Q

10： end if

11：end for

 この手法の特徴は，η（Q）＝ω（＿Q）が成り立つことと分母分子がキャンセルされること により，既存のWei1ペアリングでの垂線の計算が省略できることである．

3 利用した楕円曲線について

 今回利用した楕円曲線はrが240ビット前後，埋め込み次数が5，7，9，11，12，18，20で あるもので，いずれもqは素数べきを扱わず素数で設定した．このうち5，7，11，20の曲線 はパラメータq（π），r（ ），ψ）から虚数乗法を使い曲線を卒めたのでその手順だけここで

述べておく．

．パラメータについてはFreeman，Scott，Teske［31から引用して用意した。

。g（α），r（α）が素数となるようなαをPARI−GPを使って探した．

・q（α）に対してNZMATHの。mm．orderという関数を使って曲線を探した．

 また，埋め込み次数が13，17，19，23と高次の素数についても上記のような方法で試みた が，rが240ビット前後でq，rがともに素数となるものではうまく取れなかった．さらに qが400ビット前後で曲線を得たことはあったものの今回の実験環境では楕円曲線の点を ランダムに取るにあたりかなりの長時間がかかると思われたので断念した．

 具体的には以下に述べる曲線を構成した．

3．1 埋め込み次数5

曲線としては有限体Fq上でWeierstrass標準形が        万：μ2＝・3−25 の曲線を利用し，

q＝17715364607922948236843494979エ34875711349091  25965355824849626373481853801521348280261018  07656063479817

r：65611641361464274693300486857637877543680941  380228256080631034098451

でqは336ビット，rは225ビットである．この拡大体の構成は1Fq。＝Fル1／（ 5＋ 十11）

で構成した．

3．2 埋め込み次数7

曲線としては有限体Fq上のWeierstrass標準形が       五：μ2＝・3−243

の曲線を利用し，

q＝14456185298640633914015093255509870463238445  786851760644303028621440091429！4501325920485  2109702080383

r＝53441848805986137689412457884947872507296997  1294045941224498781280578675192489

でqは342ビット，rは258ビットである．この拡大体の構成はFq・＝Fq［π1／（ 7＋π十21）

で構成した．

3I3 埋め込み次数9

曲線としては有限体Fq上でWeierstrass標準形が        五：μ2＝・3＋1 の曲線を利用し，

       9＝30614511059595723509929042182415171927183158         02710560373001011629795786952195361197243921         70588602764112177

       r＝175859236024437609423345540022962797459272736         402347141193268746504567484534417

でqは348ビット，rは260ビットである．この拡大体の構成はFq。＝1Fq［ ］／（ 9＋ 十1）

と1Fq。＝Fg［π1／（ し3），Fq。＝Fq小1／（ 3一ω）の2通りで構成した．ただし，ωは 3−3

の根を表す．

3．4 埋め込み次数11

曲線としては有限体Fq上でWeierstrass標準形が        亙：μ2＝・3−625 の曲線を利用し，

       q＝。51686212357185838299055876310634409843575172         42526415602639317257729896369859909955107300         041884297

       r＝982089328276043398515255916442731307309674836          360504275100481225258719819407640211

でqは321ビット，rは269ビットである．この拡大体の構成はlFq・・＝Fq［ 1／（ 11＋ 十

11）で構成した。

3．5 埋め込み次数12

曲線としては有限体Fq上でWeierstrass標準形が       亙・：μ2：π3＋5

を利用し，

       q＝16030569034403128277756688287498649515636838          101184337499778392980116222246913

       r＝16030569034403128277756688287498649515510226          217719936227669524443298095！69537

でgは254ビット，rは254ビットである．この拡大体の構成はlFqユ。＝Fル1／（ 12＋5）

で構成した．

3．6 埋め込み次数18

曲線としては有限体Fq上でWeierstrass標準形が

の曲線を利用し，

       q＝58709285320900073406925617811693805623564304          04913482030243997510873476960788527967330721          5755454161141

       r＝10786994225696144150491191871486839136978135          4128945134119237266728176832001

でqは335ビット，rは246ビットである．この拡大体の構成は亙q・・＝Fq同／（π18＋ 十3）

で構成した．

3．7 埋め込み次数20

曲線としては有限体Fq上でWeierstrass標準形が        五：μ2＝・3−19 の曲線を利用し，

       q＝16598806790704045783622246422207693679663260          34839422512557521899867521866788370800781250          205824267

       ・＝2114571087517752625513520447354282275330T643          382361230380090172492522501

でqは319ビット，rは233ビットである．この拡大体の構成はlFq。。＝1Fq［ ］／（ 20＋ 十7）

で構成した．

4 計算機実験

4．1 アルゴリズム実験

 今回の実験には計算機代数システムMAGMA［4］を用いた．なお，アルゴリズムは Antonio，田中，中村［11にあるソースファイルSquarePairing．mに少しの修正を加えて 実験した．実際修正したところは点に対してπ座標，μ座標を返す関数の呼び出しを少な

くするために一回呼び出したら保存しておくようにしたところである．なお，実際に実験 したアルゴリズムは巻末の付録Aに掲載した．

4．2実験結果

VMware P1ayer3．1．4土で実験を行い，実験環境は次のようになっている．

ホストOS

   OS：Microso筑Windows Server2008R2Standard

   CPU ：AMD Phenom II X61090T Processor（3．2GHz6cores）

   メモリ ：8Gbyte ゲストOS

   OS ：CentOS5．5（32bit）

   CPU ：4cores    メモリ ：2Gbyte

利用ソフトウェア MAGMA：2．17−4（re1eased on4February2011）

 付録Aに示しているアルゴリズムに対して，3節で紹介した曲線を用いて数値実験を 行った．各々の曲線に対して10組の有理点を準備し，それらに対して5回の計算を行って 平均時間を計測した．

ん

9 9＋

tate＋fe

1．272 1．850

1．180 1．198

3．208

 なお，表の単位は秒で，9＋は逐次拡大の場合を表している．

 tate＋feはTateペアリングを求めた上で単純に（反復二乗法）（〆＿1）／r果を施した だけであり，tate＋fe＊は（ψ＿1）／r乗で因数分解，g進展開，フロベニウス写像を用いた．

詳細は2．4節参照．

 今回の実験の結果としては，んが素数の時で効率化を考えた簡約Tateペアリングは単 純なべき乗（反復二乗法）での簡約Tateペアリングと比べてあまり時間短縮になってい ないことがわかった．また，んが18，20と高いときには平方Wei1ペアリングの方が単純な

5 計算量の解析

 実験の結果に対して，アルゴリズムに必要な計算量について説明する．今回の実験の 中で，最も大きなウェイトを占めるのはMi11erループ内で演算される有限体の元の乗算，

丘na1exponentiationによるべき乗計算である．Mi1Ierループ内の計算量について詳細は Antonio，田中，申付［1］に譲る．まずFq，Fψ上の乗算をそれぞれM，Mだとし，逆元の計 算を同様に∫，∫たとする．この上で，M た島1．5ん2M，∫た島5M ん，∫層5Mの近似評価を用 いるとMi11erループ1回の乗算回数はTateペアリングで（12ん2＋17）M，平方Wei1ペア

リングで（46．5ん2＋17）Mであって，これはWei1ペアリングに比べて30％前後の高速化

となる．

 次にTateペアリングの丘na1exponentiationでは，単純に（〆一1）／r乗する（反 復二乗法）と平均乗算回数は1g（〆一1／ヅ）Mん＜1g（ψ／r）Mた二（ん1gq−gr）Mん＝

1．5ん2（ん1gq＿1gr）Mである．

 そして，rを2進展開したときの1の個数をひ（r）とすると平方Wei1ペアリングと単純 なべき乗での簡約Tateペアリングの計算量はそれぞれ

         Wε11＝｛1g・（25．5ん2＋9）十μ（・）（21ん2＋8）｝M ，

   1α亡ε十∫ε＝｛1g・（7．5ん2＋9）十・（・）（4．5ん2＋8）十1．5ん2（ん1gザ1g・）｝M

となる．つまり，単純なべき乗の簡約Tateペアリングについてはんについての3次式で，

またqの大きさにも影響してくる．その点，平方Wei1ペアリングの方はMi11erのループ 内の乗算回数は多いもののんについての2次式で，qの大きさは影響されないので，高い 埋め込み次数で比較すると高速ということが考えられる．

6 むすび

今回，平方Wei1ペアリングど簡約Tateペアリングを計算機上で実験し，計算を行った 結果について理論的に正しいかどうか計算量の精密な解析を行った．実験結果からは埋め 込み次数が高いときの平方Wei1ペアリングは単純なべき乗（反復二乗法）での簡約Tate ペアリングよりも高速であることがわかった．しかし，効率化を考えた簡約Tateペアリ

ングの場合との比較では今回実験したいかなる埋め込み次数の場合でもかなり遅いものと

なった．そして，次の表が平方Wei1ペアリングと単純なべき乗の簡約Tateペアリングの 比の実験値と理論値である．実験値は4．2節の表にあるtate＋feとsqwei1による．理論値 は5節の式に具体的なん，q，rを代入したものである．

ん 5

（tate＋fe）／sqwei1（実） 0，49 0，53 0，58 0，62 0，67 0，65 1，23 1．27

（舌α加十！e）／5qωε乞Z（理） 0，55 0，54 0，63 0，63 0，78 0．78 L27 1．36

これより，理論的にも埋め込み次数が高いときの平方Wei1ペアリングは単純なべき乗（反 復二乗法）の簡約Tateペアリングよりも高速であることがわかった．

 なお，今回の実験ではDenomimtor e1imination，Twist map，Distortion mapを利用 しておらず，さらには丘m1exponentiationの効率化を考慮した計算量評価も行っていな い．そのため，今後の課題としてはこれらを踏まえた上での平方Wei1ペアリングと簡約 Tateペアリング，さらにはんが13，17，19，23のときの平方Wei1ペアリングと効率化を考 慮した簡約Tateペアリング，の数値実験と計算量評価があげられる．

謝辞

 論文を作成するにあたり，多くの方のご協力を頂きました．ご多忙の身にも関わらず，終 始御指導下さった中村憲教授に深く御礼申し上げます．また，不明な点を解決するための 有益なご助言及ひご教示を頂きました田中覚研究員に深く感謝申し上げます．2年間の博 士前期課程の輪講で困難を共にし，ご助言を頂きました宮本泰徳さんに深く感謝致します．

参考文献

［1］C．A．Antonio，田中覚，中村憲．平方ペアリングの実装効率について．日本応用数理  学会論文詩，vo1．18，No．4，703−721．2008．

［21K．Eisentrager，K．Lauter，and P．Montgomery．Improved Wei1and Tate pair−

 ings for e11iptic and hypereI王iptic curves．λZgor批んmづ。ハ〜mうεr rんeorひ8Vmρ05乞um，

 ANTS VI，LNCS vo1．3076，169−183．2004．

［31D．Freeman，M．Scott，and E，Teske．A taxonomyofpairing−friend−1y e11iptic curves．

［41MAGMA Group，MAGMA，

   http：／／magma・maths・usyd・edu．au／mag皿a／

［5］A．J．Menezes，T．Okamoto，and−S．A，Vanstone．Reducing e11iptic curve1ogarithms    to1ogarithms i早a丘nite丘e1d、∫五五五珊αη8αc左乞。η50η∫ψormα切。η丁加。rV，39．

   1639＿1646．1993．

［6］V．Mi11er．Short programs for function on curves．unpub1ished−manuscript，1986．

付録A 今回の実装で使用したアルゴリズム

 以下に示すプログラムは，今回の実装で平方Wei1ペアリングとTateペアリングを計算 したものである．プログラムは計算機代数システムMAGMAで動作するように言己述され

ている．

／／ The coordinate functions

／／ x（P）： return x−coord． of point P x ：＝ function（P）

  assert not 工sZero（P）；

 return Eltseq（P）［1］；

end funct ion；

／／ y（P）： return y−coord・ o士 p◎int P

y ：； functio工1（P）

 assert not IsZero（P）；

 return Eltseq（P）［2］；

end ＝EunCtiOn；

／／ 1ine（A，B，C）：return 1＿A，B（C）．

／／ 1＿A，B is line throug11two points A a皿d−B．

／／ example：

／／ waエユt g＿j P，kP（Q） is value on Q of line g s・t・ through j P a工Ld kP，

／／ we input 二Line（j P，kP，Q）．

1ine ：＝ function（A， B， C）

／／ Q皿ay be zero then problem if IsZero（C） then

 error lIC is zero in f ll；

if IsZero（A） aエLd IsZero（B） then    retur工1BaseRing（Curve（A））！1；

end if；

if IsZero（A） then

   return x（C） 一 x（B）；

end if；

if IsZero（B） then

   return x（C） 一 x（A）；

end if；

xa ：＝ x（A）；

xb ：＝ x（B）；

if xa ne xb then

   yc ：＝y（C）；

   yb ：＝ y（B）；

   ya ：＝ y（A）；

   xc ：＝ x（C）；

   return （xb − xa） ＊ yc 一 （yb − ya） ＊ xc

end．if；

ya ：＝y（A）；

xc ：＝x（C）；

if ya ne y（B） then

else

   yc ：＝ y（C）；

   a ：＝ Eltseq（Curve（A））；

   return （ 一 （xa＋xa＋xa） ＊ xa − a［4］ ） ＊          （XC−Xa）十

         （ ya＋ ya ） ＊ （ yC − ya ）；

end if；

end funct ion；

／／ 1ine2（A，B，C）： return 1＿A，B（C）， 1＿A，B（一C）．

／／ 1＿A，B is line through two points A a皿d B．

1ine2 ：＝ 士unction（A， B， C）

／／ Q may be zero then problem

   error 11C is zero in二1ミ11；

end if；

if Characteristic（BaseRing（Curve（C））） eq 2 then    returエ1 1ine（A，B，C）， 1ine（A，B，一C）； ／／ too slow end if；

if 工sZero（A） a1d IsZero（B） then    ret ：＝BaseRing（Curve（A））11；

   return ret， ret；

end if；

if 工sZero（A） then    ret ：＝x（C） 一x（B）；

   return ret， ret；

end if；

if 工sZero（B） then

   ret ：＝ x（C） 一 x（A）；

   return ret， ret；

end．if；

xa ：＝ x（A）；

xb ：＝ x（B）；

if xa ne xb then ／／ nor皿al line

   ya ：： y（A）；

   xc ：； x（C）；

   yc ：＝ y（C）；

   d文 ：＝ （xb − xa）；

   ad ：＝ 一 （yb − ya） ＊ xc − xb ＊ ya ＋ xa ＊ yb；

   dxy ：＝ dx＊yc；

   return dxy＋ad， 一dxy＋ad；

end．if；

ya ：＝y（A）；

xc ：＝x（C）；

if ya ne y（B） then ／／ vertical line

   ret ：＝ XC − Xa；

   return ret， ret；

else ／／ ta皿gent ：Line（anyway ca］一］一）

   a ：： Elt seq（Curve（A））；

   if Characteristic（BaseRing（Curve（C））） eq3then

       ad ：＝ （ a［1］ ＊ ya 一 （a［2］ 十 a［2］）一＊ xa − a［4］

      （XC−Xa）；

   else

       ad ：＝ （一 （xa＋xa＋xa） ＊xa−a［4］ ） ＊       （XC−Xa）；

   end．if；

   dy ：＝ （ ya ＋ ya ÷ a［1］ ＊ xa ＋ a［3］ ）；

   inVS ：＝ ad−dy＊ya；

   yc ：＝ y（C）；

   dyyc ：＝ dy＊yc；

   return invs＋dyyc ， invs−dyyc；

   ／＊

   ad ：＝ （ a［1］ ＊ ya 一 （a［2］ 十 a［2］） ＊ xa − a［4］ ） ＊    dy ：＝ （ ya ＋ ya ＋ a［1］ ＊ xa ＋ a［3］ ） ＊ yc；

   i…：＝・d＋・［3］＊・・一・［5］一a［5コ・！a［4］一xa｛

   return invs＋dy ， invs−dy；

   ＊／

）＊

XC；

2）＊xa；

end if；

end f㎜ction；

／／ SqWei1（P，Q，1）： co皿pute Squared Weil Pairing e＿］一（P，Q）＾2．

／／ we assume P，Q in E（F）［1］．

SqWei1 ：＝ function（P， Q， 1）

／／ check degenerate pattern（＝return 1）

assert ］＝sOdd（1）；

E  ＝ Curve（P）；

if IsZero（P） or 工szero（Q）

    return BaseRing（E）11；

end if；

or x（P） eq x（Q）

／／ create addition chain（binary chain）

bc：＝［］；

11：＝1；

while not IsZero（11） do     Append（〜bc， IsOdd（11）

   11 ：＝ 11 div 2；

end while；

t ：＝ ＃bc − 1；

assert ＆；十 ［bc［i＋1］ ＊ 2＾i

select ＝し else O）；

： i in ［O．．t］ ］ eq1；

／／ initialize PP：＝P；

QQ：：Q；

n：：BaseRing（E）！1；

d ：＝ BaseRing（E）！1；

／／ Miller loop

for i in Reverse（［O．．t−1］） do     ／／ doubling Part

 np， dp ：＝ 1ine2（PP，PP，Q）；

 dq， nq ：＝ 1ine2（QQ，QQ，P）；

    n ：＝n＊n＊np＊nq；

    d ：＝ （1＊d一＊（1p＊dq；

  PP ：＝ PP＋PP；

    QQ ：＝ QQ＋QQ；

    r ：＝r＋r；

        ／／ ad．dition（十1） Part

        if not 工sZero（bc［i＋1］） then

         dq， nq ：＝ 1ine2（QQ，Q，P）；

      n ：＝ n＊np＊nq；

      d ：＝ d＊dp＊dq；

      PP ：＝ PP＋P；

      QQ ：＝ QQ＋Q；

      r：＝r＋1；

        end if；

    end for；

    assertreq1；

    if not IsZero（n＊d） then         retum−n／d；

    else

return BaseRing（E）！1；

    end if；

end f㎜ction；

／／ TatePai工一（P，Q，二L）： co㎜pute optimized Tate Pairing e（P，Q）＿1．

／／ we assume P in E（F）［1］．

TatePair ：； function（P，

Q，1）

E ：＝ Curve（P）；

if 工sZero（P） or ＝［sZero（Q）

    return BaseRing（E）11；

end if；

then

／／ create addition chain（binary chain）

bc：＝［］；

ユ1：＝ユ；

while not IsZero（11） do

    Append（ bc， IsOdd一（11） select ＝し else O）

   11 ：： 11 div2；

end whi］一e；

t ：＝ ＃bc − 1；

assert ＆；十 ［bc［i＋1］ ＊ 2＾i ： i in ［O．．t］一］

；

eq1；

／／ initialize 0：＝E！O；

T：＝P；

n ：＝ BaseRing（E）！1；

d ：＝ BaseRing（E）！1；

r：＝1；

／／ Mi11er loop

for i in Reverse（［O．．t−1］） do     ／／ doubling Part

    n ：＝n＾2＊1ine（T，T，Q）；

  T：＝T＋T；

    d ：＝ d｛2＊1ine（T，0，Q）；

    r：＝r＊2；

        ／／ addition（十五） Part         if not 工sZero（bc［i＋1］）

      n：＝n＊1ine（T，P，Q）．

      T：＝T＋P；

      d ：＝ d＊1ine（T，0，Q）；

      r ：＝r＋1・

      ，         end−if；

    end for；

    assertreq1；

    if not IsZero（n＊d） then

        retum（n／d）；

    else

return BaseRing（E）11；

    end if；

end function；

then