9:00 〜 9:55 林彬（金沢工大）
格子基底縮小と暗号への応用
講演内容：
格子に関する問題を紹介し、特に最短ベクトル問題との関わりにお
いて、格子基底縮小を2次元の場合のガウスのアルゴリズムから始め
て、Lenstra-Lenstra-Lov\'aszの縮小基底の概念とLLLアルゴリズム
について述べる。また最短ベクトル問題などに関する計算量理論の
結果についても触れる。応用として大きな成功を収めた
Lagarias-Odlyzkoの部分集合和問題の解法とMerkle-Hellmanのナッ
プザック暗号の解読の方法を実験結果とともに述べる。
Coppersmithはある状況においてRSA暗号を解読できることを示した。
格子基底縮小を使うこの解読法の理論を述べる。
9:55 〜 10:50 小暮淳（富士通研究所）
暗号と格子
講演内容：
一部の暗号は、格子と密接な関係を持っている。例えばNTRU署名
は格子のapproximate CVP(Closest Vector Problem)の困難性を利
用している。ある場合には、ユニモジュラー行列のグラム行列を
分解する攻撃が考えられ、その実現手段としてLLL reductionを利
用する方法なども知られている。NTRU暗号の安全性は、公開鍵に
より定義されるNTRU格子のSVP(Shortest Vector Problem)と関係
がある。
また、古くはナップサック型暗号に対する低密度攻撃などがあり、
その成功確率評価においては、テータ関数を用いた、球内の整格
子点数評価が本質的な役割を果たしている。
このような暗号と格子との関わりについて概観する。
11:05 〜 12:00 佐藤孝和（東工大）
有限体上の楕円曲線の位数計算
講演内容：
有限体上定義された楕円曲線の定義体上の有理点の個数を
速く求めるアルゴリズムはその数論的な深さと楕円曲線暗号へ
の応用上の重要性から盛んに研究され近年著しい進展を遂げた。
ここでは位数計算の基本となる理論から実装技術まで概説する。
プログラムに戻る ．