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

情報セキュリティ研究室

日本応用数理学会 2016年度 年会への参加報告

■参加会議名:日本応用数理学会 2016年度 年会
http://annual2016.jsiam.org/
■日時:2016年7月12~14日
■場所:北九州国際会議場(福岡県北九州市小倉)
■報告者:ISIT情報セキュリティ研究室  奥村伸也 (研究員)

概要

2016年7月12~14日に、北九州国際会議場(福岡県北九州市小倉)にて、「日本応用数理学会 2016年度 年会が開催された。報告者は、12日の午後に行われた研究部会OS「数論アルゴリズムとその応用」に参加し、研究成果の発表を行った。参加人数(数論アルゴリズムとその応用)は20名程度であった。

謝辞

本学会参加および発表に関し、報告者はJST, CRESTの支援を受けています。

講演

数論アルゴリズムとその応用(1) 座長:内田 幸寛(首都大学東京)
講演:F4アルゴリズムを用いた2次多変数連立方程式の求解の高速化
伊藤 琢真・内山 成憲 (首都大学東京)
(講演は伊藤氏による)
講演概要:
多変数二次連立方程式に対する、F4アルゴリズムというグレブナー基底を
計算するアルゴリズムの高速化についての発表で、MQ-Challengeという解読
コンテストで良い結果を得ていた。耐量子暗号の候補である、多変数公開鍵暗号
への攻撃に適用できると考えられる。
高速化のアイディア
・S多項式の還元順
・S多項式の還元の打ち止め
・並列化
・還元の際の計算順
・多項式の格納方法
・乗算用関数の作成

質疑応答:
Q:(安田貴徳准教授(岡山理科大)) n(変数の数)を増やして試す予定はあるか?
A:その予定です。
Q:3次以上の連立方程式の場合には何か不都合があるのか?
A:まだ試していないのでわからない。
Q:係数体によって何か違いが出てくるか?
A:体には依りません。
Q:(高木剛教授(九大IMI))5種類の高速化を提案されているが、それぞれ何倍高速になるかを第三者が再現できるか?
A:上二つの高速化は厳密には調べていませんが、並列化した分だけ早くなることが分かっています。
 また、一番下のアイディアは2~3倍の高速化を実現していることを確かめられます。
Q:reductionをするのをある程度さぼって、後でまとめてやると高速になったりしますが、今回はそうしていますか?
A:今回はreductionを適宜行っています。

数論アルゴリズムとその応用(2) 座長:長尾 孝一(関東学院大学)
講演:p=(3V^2+1)/4を持つ合成数の楕円曲線法による素因数分解
白勢 政明 (公立はこだて未来大学)
講演概要:
講演題目にあるような特殊な合成数の楕円曲線法による因数分解
・楕円曲線法(ECM)はP∈E(Z/NZ)のL倍を計算(L:十分大)
・L=NでECMが成功する条件は?
・Eがアノマラスの時上の条件でO.K.
・アルゴリズムを繰り返し適用可

質疑応答:
Q:(座長) Pを取る困難性を解決できそう、ということだがどのように解決したのか?
A:楕円曲線の係数を与えると一つ有理点(有理数体上の)を見つけるアルゴリズムが存在し、
mod NすることでPが得られると考えています。

講演:整数計画法による格子最短ベクトル探索問題の解読報告
安田 雅哉・脇 隼人 (九州大学マス・フォア・インダストリ研究所)
(講演は安田氏による)
講演概要:
格子基底縮約アルゴリズムに最適化の手法を組み込んだ、最短ベクトル問題(SVP)に対する新しい解法に関する発表で、SVPは耐量子暗号の構成にも利用されているので、今後の発展が期待される。
・混合整数二次計画問題に定式化してSVPを解読する方法を提案および適用例の報告
・SVPを最適化する方法を紹介
・最適化エンジンCPLEXの概要を紹介(方法はLLL+CPLEX)
・BKZ+CPLEXならCPLEXの時間が大幅に短縮可(格子縮約の時間は増大)
・整数上ではなく実数上で考える

質疑応答:
Q:(座長)どのようにR実数体で見るというのはどういうことか?
A:整数で考えるのが通常だが、実数で考えるのは(緩和問題)と呼ばれ、
 係数を大小で分割して、どっちにより短いベクトルがあるかを絞っていきます。

講演:円分体に対するイデアル格子上の短い生成元の復元可能性について
奥村 伸也 (公益財団法人九州先端科学技術研究所), 安田 雅哉・高木 剛 (九州大学マス・フォア・インダストリ研究所)
(講演は奥村(報告者)による)
講演概要:
いくつかのイデアル格子暗号(耐量子)へのある攻撃について、その攻撃の効率的な適用法と防御法について講演した。
・効率的な適用:攻撃に必要な、log-unit格子の双対格子の基底の高速計算法を提案
-先行研究:サイズの大きな行列の演算(逆行列1回、掛け算2回)
-本研究:ある線形連立方程式を解くことに帰着→高速フーリエ変換で効率的に解けるように工夫できる
・防御法:攻撃回避可能な小さな円分体上の短い生成元を暗号で使う大きな円分体上の短い生成元に持ち上げて攻撃回避

質疑応答:
Q:(高島氏(三菱電機)) その攻撃は成功するということで決着がついたのではないか?
A:実験的には多くの場合に成功するが、理論的にはまだ解析する余地がある、という結果を得ました。

数論アルゴリズムとその応用(3) 座長:横山 俊一(九州大学)
講演:ZHFEに対する選択暗号文攻撃
橋本 康史 (琉球大学)
講演概要:
多変数多項式暗号の中でも安全性が高いと考えられている、
ZHFEと呼ばれる暗号への選択暗号文攻撃についての発表で、
ある仮定の下では、ZHFEの安全性が低下し実用的でなくなることが分かった。

質疑応答:
Q:像が暗号文空間の中に入っていることは簡単に確かめられるか。
A:できると考えています。
Q:具体例の実装はやっているのか?
A:パラメータが小さいところでやっていますが、大きいところだとメモリがオーバーします。
Q:攻撃のどの部分でメモリを食うのか?
A:Min-rank攻撃の部分です。