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

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

平成15年度の主な成果は以下の通り.1.量子アルゴリズムに対する公開鍵暗号に対する安全性Shorのアルゴリズムにより,素因数分解が多項式時間で完了することは明らかになっている.しかしながら,量子計算機固有の問題,すなわち,原理的に可逆計算でなければならないこと,一回の演算時間が古典計算機より遅いこと,などの理由により,必ずしも,意味のある時間で素因数分解が完了するかどうかは明らかではない.本研究では,Shorのアルゴリズムをいくつかの手法により,量子回路で記述し,実際に必要となるgate数,qubit数を厳密に求め,必要となる計算時間を評価した.その結果,演算時間の遅いデバイスを用いた場合や,qubitを節約する回路を用いた場合には,現実的な時間で素因数分解が完了しないことを示した.具体的には,古典計算機よりも,量子計算機が真に有効であるためには,1592qubit以上で,演算時間が70μ秒以内,もしくは,1064qubitで,演算時間が16μ秒以内の量子計算機が実現しなくてはならないこと明らかにした.2.NMR量子計算機に対する共通鍵暗号の安全性評価平成13,14年度に引き続き,量子計算機に対する共通鍵暗号の安全性評価を行った.本年度は,GroverのアルゴリズムのNMR量子計算機への適用可能性に関して考察を行なった.さまざまな物理的条件(すなわち,可能な観測誤差)に対して評価を行ない,従来の量子計算機よりも高速に,暗号化鍵の探索が行なえることを確認した.具体的には,58bit鍵の探索において,測定誤差が1/256であるとき,従来の方式よりも12.5倍高速実行可能であることを数値実験により確認した.