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

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

平成14年度の主な成果は以下の通り.1.NMR量子計算機に対する共通鍵暗号の安全性評価公開された暗号化アルゴリズムE,平文m_0及び暗号文c_0が与えられた時,c_0=E(k_0,m_0)の関係をみたす秘密鍵K_0を見つける既知平文攻撃のシナリオにおける,共通鍵暗号の安全性の評価を行った.平成13年度にNMR量子計算機を一般化した,Bulk Quantum Turing Machine(BQTM)による数え上げ技法を応用した新しい共通鍵暗号解読アルゴリズムの提案を行ったが,今年度は,数値実験により,本提案アルゴリズムの有効性に関して詳細に検討を行った.その結果,NMR量子計算機の観測精度Lと秘密鍵の長さnが,L>(3n+2)/4となる場合には,提案方式が従来の結果(Groverのアルゴリズムの適用)を上回ることを明らかにした.現在の状況では,この条件式は,数値実験により求めたいくつかの仮定に基づいているため,今後の研究課題として,この仮定の理論的な証明が残されている.また,今後,暗号化関数の内部構造を利用した新たな攻撃法に関する研究を行う予定である.2.量子アルゴリズムに対する公開鍵暗号の安全性共通鍵暗号に対してだけでなく,量子アルゴリズムに対する公開鍵暗号の安全性評価も開始した.Shorの素因数分解アルゴリズムにおいて,もっとも計算時間が必要であり,難しい制御が必要なのは,べき乗剰余演算であると言われている.このべき乗剰余演算を行う量子回路の構成に関して,いくつかの成果を出した.例えば,Montgomery Reductionや右向きBinary Methodを量子回路に導入すれば,効率的にべき乗剰余演算を行えることを明らかにした.今後の課題として,さらなる効率的な量子回路の探索および,物理デバイスに応じた回路の探索を考えている.