日本応用数理学会研究部会連合発表会

連合発表会のおしらせ

「数論アルゴリズムとその応用」研究部会

9:20--9:40 ○福地弘之，内山成憲，徳永浩雄(首都大学東京)
代数曲面を用いた公開鍵暗号への効率的な攻撃法
量子計算機の実現により，現在広く使われている素因数分解問題や 離散対数問題といった数論的な問題に基づいた公開鍵暗号は 量子計算機の実現の下では安全でなくなることが知られている． この問題に対応するため，現在様々な研究が行われている． 秋山と後藤により提案された代数曲面を用いた公開鍵暗号もその一つであり， 現行の公開鍵暗号を解読できる量子計算機を用いても解読困難 である暗号を目指している． 本講演では秋山-後藤暗号に対して内山-徳永が提案した攻撃法及び Voloch が提案した攻撃の実装実験を行った結果について述べる．

9：40--10：00 前田有宏 (東京海洋大学海洋科学技術研究科M2)
ブレイド群を利用した公開鍵暗号系の実装
2000年にKoたちによりブレイド群の共役問題の困難さを利用した新たな公開鍵暗号が提案された．この暗号系では群の共役問題という「逆問題を解くことが困難な代数的関数」を利用しており，さらなる一般化が期待されている．この暗号系に対する攻撃の研究も活発に行われ，2003年にCheonたちによりLawrence-Krammer表現を用 いた多項式時間の攻撃法が提案された．今回の発表では，上記の暗号系について総合報告を行い，暗号系を構成するのに必要なアルゴリズム，及び攻撃の実装について報告する．

10:00 --10:30 ○山外一徳, 松尾和人, 小崎俊二 (情報セキュリティ大学院大学)
拡大体上の楕円曲線暗号に対するindex calculusについて
Gaudryは拡大体上の(超)楕円曲線暗号にindex calculusを用いるgeneralized Weil descent攻撃を提案した。この攻撃は、グレブナ基底計算を用いてrelation を集める部分と集めたrelationから線形代数方程式を解く部分からなる。また、 Nagaoはrelation収集部に対する別のアルゴリズムを提案した。本講演では、 Nagaoのアルゴリズムを用いた拡大体上の楕円曲線暗号に対するgeneralized Weil descent攻撃のMagma上の実装実験により得られた知見について述べる。

10:45--11:05 ○Christine Abegail Antonio, Tanaka Satoru, Ken Nakamula (Tokyo Metropolitan University)
Comparing Implementation Efficiency of Ordinary and Squared Pairings
In ANTS VI, K. Eisentrager, K. Lauter and P. Montgomery proposed a new pairing technique called squared Weil and squared Tate pairings which they claim are 20 percent faster than the standard Weil/Tate pairings. They also claim that the squared Tate pairings performance is comparable to the Tate pairing using the denominator elimination method. There has been a discussion that their claim may not be correct so in this talk, we will show a concrete evidence that the squared Tate pairing is certainly not 20 percent faster than the standard Tate pairing and it is not comparable in performance to the Tate pairing with denominator elimination method over some pairing-friendly curves of embedding degrees 6, 8 and 10.

11:05--11:25 ○小泉 賢洋, 内山 成憲, 中村 憲(首都大学東京)
Knapsack暗号への攻撃を効果的にするためのSampling Reductionの改良と考察
Knapsack暗号への代表的な攻撃方法に格子基底縮小アルゴリズムを用いるものがある. 近年, 提案されたSampling Reductionとよばれる格子基底縮小アルゴリズムを Knapsack問題から得られる格子に適用した際, 本質的な効果が得られていないことがわかった. その問題を解消したより効果的なSampling Reductionの改良方式を提案する. その改良方式について行った数値実験および考察についても述べる.

11:25--11:45 ○西本　啓一郎，中村　憲（首都大学東京大学院）
虚二次体上のOTU2000が生成するナップサック問題について
本発表では我々が実装したOTU2000のプログラムにより生成される ナップサック問題の困難性について理論的，実験的に検討した結果を 報告する．