量子アルゴリズムに対する共通鍵暗号の安全性評価

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

平成13年度の主な成果は以下の通り.1.鍵の総当り攻撃のファイル探索問題への帰着公開された暗号アルゴリズムE,平分m_0および暗号文c_0が与えられたとき,c_0=E(k_0,m_0)の関係をみたす秘密鍵k_0を見つける既知平文攻撃のシナリオでの鍵の総当り攻撃を,ファイル探索問題に帰着させる変換(攻撃法)を提案した.その変換が従来の結果(Groverのアルゴリズムを素朴に適用する場合)よりも有利となる条件を洗い出した.マシン実験を用いて案際に使用されている暗号系において,その条件が成立つかを調べたところ,成立しないことが判明した.よって,ここで提案した変換では安全性の心配はないことを確認した.2.中間一致攻撃型の暗号解読の実現可能性についてChiらが提案しているファイル探索問題の高速化技法(http://xxx.lanl.gov/archive/quant-ph/9707011)の妥当性を評価して,彼等の主張に誤り(存在を仮定しているオラクル関数に問題点)があることを発見した.よって,中間一致攻撃型の暗号解読は,現在のところ,それほどの脅威ではないと思われる.3.NMR計算機に対する共通鍵暗号の安全性NMR計算機等を一般化した,Bulk Quantum Turing Machine (BQTM)による数え上げ(counting problem)技法にを応用した新しい共通鍵解読アルゴリズムを提案した.提案アルゴリズムでは,ブール関数F^<(d)>_rを導入することで,暗号アルゴリズムEを実現するオラクルの呼び出し回数とNMR計算機の観測の精度との間にトレードオフが成立つことを示した.妥当な仮定のもとで計算の複雑度を予想し,小規模な実験を行ったところ,従来の結果をしのぐ可能性があること分かった.現在,このアプローチの有効性を調べるために,マシン実験を継続している.