整数論及び組合せ論的アルゴリズム研究とその次世代公開鍵暗号への応用

点击翻译按钮获取中文摘要

今年度は、昨年度に引き続き量子計算機を用いた攻撃に対して安全と期待される公開鍵暗号の安全性解析、また、関連するアルゴリズムを用いた新しい暗号方式の提案とその安全性解析について研究し、主に次の4つの結果を得た。まず、量子計算機に関して耐性があると思われる方式の安全性解析については、最初に、EUにおける暗号標準化組織であるNESSIE推奨の公開鍵暗号の1つであるディジタル署名SFLASHに対して、最も一般的な条件の下で効率的な攻撃が可能なことを実装実験により示した。(小椋直樹氏、中村憲氏(首都大学東京)との共同研究、2008年暗号と情報セキュリティシンポジウム(2008)にて口頭発表)。次に、代数曲面暗号の安全性評価として、昨年度研究代表者等により提案された攻撃手法と、後に、Volochにより提案された別の攻撃手法のその効率の比較を行い、研究代表者等によって提案された手法がある条件では効果的であることを実装実験によって示した。(福地弘之氏、徳永浩男氏(首都大学東京)との共同研究、平成20年日本応用数理学会研究部会連合発表会(2008)で口頭発表)3つ目は格子における最短ベクトルを求める問題の困難性に基づくナップザック暗号の安全性評価についてである。これは、昨年度に引き続きSampling Reductionと呼ばれるアルゴリズムの改良法の提案を行った。サイズが大きくなると計算量が増えてしまうので、実装実験できる範囲が限られてしまうのだが、ある条件の下では提案手法が高速であることを示した。(小泉賢洋氏、中村憲氏との共同研究、上記研究部会連合発表会(2008)で口頭発表)最後に、格子に関連するアルゴリズムを用いて安全性の解析を必要とする素因数問題の困難性に基づく公開鍵暗号で、1995年にVanstone等によって提案された、データ通信量を軽減する手法に対し、オリジナルの手法とは異なる法を用いた方式の提案およびその方式に対する安全性解析を行った。(金山直樹氏(筑波大学)との共同研究、IEICE Trans. Fund.(2007)に論文が掲載)