2016年連合発表会
「数論アルゴリズムとその応用」 (JANT) 講演要旨

講演者は登壇者○

「3-同種写像を用いた効率的なハッシュ関数の構成」
○立花ひかり 九州大学大学院 数理学府
高島克幸 三菱電機 情報技術総合研究所
高木剛 九州大学 マス・フォア・インダストリ研究所

同種写像問題の困難性を安全性の根拠とするハッシュ関数が提案されている. 　Charlesらは, 超特異楕円曲線の2-同種写像に対して, バックトラッキングとセレクター関数を用いたハッシュ関数を構成した. 吉田らは, Charlesらの方式を高速化し, 2次方程式の解と係数の関係を利用して, 2-同種写像を有限体上の積1回と平方根計算1回で計算可能なアルゴリズムを提案した. 本講演では, これらのハッシュ関数を3-同種写像の場合に拡張し, 3次方程式を解くカルダノの公式を用いて, 有限体上の積15回, 平方根計算1回, 3乗根計算1回という高速な公式を与える. 　さらに, 吉田・高島方式の2-同種写像を用いたハッシュ関数と, 提案方式を適用した　3-同種写像を用いたハッシュ関数をMagmaを用いてそれぞれ実装することで, 楕円曲線の標数が256ビット (128-bit security) の場合に, 提案方式が2-同種写像列を用いた場合と同等の速さで計算できることを示す.

「elliptic netの並列化によるいくつかのpairing写像の計算」
○小貫啓史、首都大学東京
照屋唯紀、産業技術総合研究所、産総研特別研究員
金山直樹、筑波大学
内山成憲、首都大学東京

講演者は日本応用数理学会2015年度年会において、elliptic netを用いたBN曲線上のoptimal ate pairingの並列計算について発表した。 本講演ではこの手法の他の曲線上のpairing計算への適用について論じる。 この手法が適用可能な曲線の条件を提示する。そして、それらの曲線上のpairing写像をelliptic netを用いて計算する方法を示し、その計算コストの評価を行う。

「Bit Coincidence Mining アルゴリズムとその改良」
○長尾孝一、関東学院大学 理工学部

一般の有限体上の楕円離散対数問題を解くアルゴリズムとして、著者はBit Coincidence Miningアルゴリズムと名付けたアルゴリズムを提案した。このアルゴリズムは楕円離散対数問題をある方程式系を解く問題に帰着する。類似のアルゴリズムは多くの研究者が判っていた事と思われるが、実際の方程式系のサイズが大きすぎるので注目される事は無かった。著者の提案はこの方式を微修正することにより、さらに大きな方程式系を作ることである。そうすると方程式系は大きくなり実際にはより解きにくくなるが、その解法にxLアルゴリズムを使い、xLアルゴリズムの計算量に関する甘い見積もりを用いたとすると、方程式系の解法がsubexponentialなクラスに入り、従って楕円離散対数問題の計算量もsubexponentialなクラスに入ることが判る。ここでは、このアルゴリズムとその改良について述べる。

「小さい埋め込み次数をもつ理想的なペアリングフレンドリー完全楕円曲線族の存在性について」
○岡野 恵司、都留文科大学

ペアリングに基づいた暗号方式は，適した楕円曲線(ペアリングフレンドリー楕円曲線)が必要になる．その楕円曲線の族は，ある条件を満たす多項式たちから CM-法を用いて生成される．そのような多項式の組として，さらに「曲線の位数と暗号に使う部分群の位数がほぼ一致する」という，理想的条件をもつものを探すことがこの分野の研究の一つとなっており，様々な構成法によってより理想に近い族を探す試みがなされている． 現在までに知られている理想的条件をもつ曲線の完全族は，埋め込み次数 12 をもつBN-曲線族のみである．実装に際しては様々な埋め込み次数の曲線が必要であり，さらなる理想的曲線族の存在の有無について調べることが望まれている．本公演では，埋め込み次数が 3,4,6 の場合に，理想的条件をもつ曲線の完全族は存在しないこと，および 埋め込み次数 8, 12 の多くの場合について理想的条件をもつ曲線の完全族は存在しないことを述べる．いずれも，部分群の位数を生成する多項式として円分的多項式を用いない場合を含むことが，本結果の大きな特徴である．なお BN-曲線族はこの場合から外れている．

「関数体の塔T={Tm}上のワイエルストラス半群H(Pm)について」
○ 河田　貴久、名古屋工業大学　工学研究科　

PellikaanはGarcia Stichtenothの構成した K=Fq2 上の関数体の塔 T={Tm}；Tm=K(x1,…,xm) (J.Number Theory 61 1996 p257）に対しWeierstrass半群 H(Pm) は数値的半群Sm と一致することを示した(FFTA 4 1998 pp381-392)。また Hoholdt, van Lint,Pellikaan は Algebraic geometry codes (2011 改訂)にて Pmのリーマンロッホ空間の明示的な構成はされていないと述べている（p27 Theorem 2.89）。我々は c≧ cm（cm:コンダクタ）のとき関数体の塔 Tm=K(x1,…,xm)の変数{xi}（ 1≦i≦ m ）を利用し、 リーマンロッホ空間 L(c Pm)の基底として{xi^ai}（ 1≦i≦ m , ai∈[ci, ci+1 /q ）∩ N0 ）が選べることを示した。 また、c m - Σ(c i+1/q - ci) = gm という公式を得た。アイデアとしては空隙値をもつ整数の区間 [0,cm ）を Sm=∪Sm(i) ; Sm(i)=q m-i[ ci, ci+1/q）と小区間に分割し数上げが簡単に出来るようにしたことである。今後の課題としては上記の極値の具体的表示を利用しTm上のゴッパ型符号の最小距離を調べるなど行いたい。また別の関数体の塔についても数値的半群Smの構成とそれを利用した同様の考察を行いたい。

「有限体上の平面三次曲線の行列式表示」
○ 石塚裕大、京都大学大学院理学研究科

平面三次曲線を線形形式成分の行列の行列式で定義できるかという問題を考える．これは非常に古典的な代数幾何の問題で，古くは 19 世紀の Hesse の研究にまで遡ることができるが，近年 Cassels--Tate ペアリングの計算など，数論的な問題意識からの研究が見られるようになった．今回は背景となる研究とともに，有限体上の平面三次曲線における具体的な行列式表示についての計算結果を紹介したい．

問い合わせ先

長尾孝一(関東学院大学)
nagao(at)kanto-gakuin.ac.jp