ここから本文です
研究室
情報セキュリティ研究室

情報セキュリティ研究室

代数学と計算2015参加報告

■参加会議名:代数学と計算2015
URL:http://tnt.math.se.tmu.ac.jp/ac/2015/index.ja.html
■日時:2015年12月14日~12月16日
■場所:首都大学東京 南大沢キャンパス
■主催者:首都大学東京
■報告者:ISIT情報セキュリティ研究室  安田貴徳 研究員

謝辞

本研究集会参加および発表に関し、報告者は下記の研究費の支援を受けております。
総務省戦略的情報通信研究開発推進事業(SCOPE)平成27年度イノベーション創出型
研究開発フェーズII(no. 0159-0016)

概要

代数学と計算2015(11th Symposium on Algebra and Computation (AC2015) ) は主に代数学と計算機科学との関わりを中心に幅広い分野から話題をとりあげ、普段独立して議論されることが多い各分野の交流を深めることを目的として始められた研究集会である。1995年から始まり、2年に1度のペースで開催され、今年で11回目を迎えた。報告者は暗号系の講演が集まっていた12月16日のみ参加し、1件の成果発表を行い、また関連研究を聴講した。その日の参加者は40名程であった。12月16日に聴講した講演をいくつか抜粋し、内容を報告する。

講演

  • 講演1 岡野恵司(都留文科大学)
    “ペアリング暗号に適した楕円曲線族が理想的条件をもつ可能性について”
    楕円曲線を用いたペアリング暗号において、ρ値と呼ばれる不変量があるが、これはペアリングの安全性や、スカラー倍算の効率性を決定する重要な値である。ρ値は小さい方が良いが1が下限であることが知られている。多項式を用いて構成されるペアリング用の楕円曲線としてρ値が1となるものは現在ただ1つのみ知られているが、本発表では他にρ値が1となるものが存在する可能性について論じていた。これは埋め込み次数と呼ばれる値と関係があり、例えば素数の値を持つ埋め込み次数ではρ値が1となることはないことを理論的に証明していた。
  • 講演2 横山俊一(九州大学)
    “数論データベース LMFDB の開発について”
    数論統合データベースLMFDB(the database of L-functions, Modular forms, and related objects)の紹介。これは数論における巨大データベースの一つ、およびその開発・運営プロジェクトのことである。データベースの具体例を用いて使い方を実践してみせた。例えば、2次体上の至るところ良い還元を持つ楕円曲線や同種37を持つ楕円曲線などのデータが含まれている。Sage、pari、magmaでどうプログラム記述されるかも教えてくれる。また、分からない用語があればそれをクリックすると解説が出る。
  • 講演3 特別講演:谷口哲也(金沢工業大学)
    “円分体の相対類数の計算について”
    円分体の類数を最大実部分体の類数(実類数)で整除したものを相対類数と呼ぶ。この円分体の相対類数h_p^-の計算方法の歴史と効率的アルゴリズムを紹介した。相対類数の計算手法は主に「行列式」「有限体」「多項式」を用いたものに分類される。一般にpが増えるとh_p^-は爆発的に増大することが知られており、発表者は、モジュラー計算の効率化、FFTの使用、Karatsuba乗算の使用などを用いてアルゴリズムを効率化した。
  • 講演4 特別講演:篠原直行(情報通信研究機構)
    “小標数の有限体上の離散対数問題の解法”
    ペアリング暗号に大きな影響を与えた小標数の有限体上の離散対数問題の解読手法について説明された。小標数の有限体の場合は素体を用いる場合と異なり、関数体篩法を用いる攻撃が効率的となる。関数体篩法は数体篩法には適用できない2つの大きな効率化手法が存在し、それにより近年、攻撃オーダーが大幅に改善された。一つはピンポインティングと呼ばれる手法でもう一つがフロベニウス表現アルゴリズムと呼ばれる手法である。但し、これらを適用するには拡大体に条件が必要となるため、全ての小標数の有限体上の離散対数問題が効率的に解読されるようになったわけではない。パラメータの選択次第ではまだ、十分安全な離散対数問題が構成可能である。

報告者発表

「環の既約分解を用いたNTRU型格子暗号の安全性評価」
安田貴徳(ISIT), Xavier Dahan(お茶の水女子大学), 櫻井幸一(九州大学,ISIT)

発表時間は20分で、聴講者は約30名であった。格子ベース暗号のNTRUと呼ばれる暗号方式の拡張として群環NTRUというものを考え、その安全性を解析するという内容であった。群環の場合は環の既約分解が群の表現論を用いて記述することができ、その事実が安全性評価の計算を容易にしていることを説明した。いくつかの具体的な群に対する群環NTRUの安全性を見積もり、それらを比較した。調べた中ではオリジナルのNTRUが最も安全であるということが分かった。しかし、有限群は他にも無限に存在するため、中にはオリジナルNTRUよりも安全性の高いものが存在する可能性があり、それが今後の研究課題である。

Q1(岡崎助教(信州大学)). オリジナルNTRUが最も安全というよりも、同じ安全性での鍵サイズの違いを説明した方が良いのでは?
A1. そのような説明方法もあったが、安全性比較という観点からこの説明方法を選んだ。
Q2(岡野講師(都留文科大)). 群の準同型を用いてより効率の良い攻撃方法が見つかる可能性は?
A2. ある。