1．はじめに：量子計算と暗号

　現代暗号は，共通鍵暗号と公開鍵暗号に大別されるが，量子計算機のこの二つの暗号系に対する安全性に関して，その基礎的な結果について説明する^(注1)．特に，共通鍵暗号に対する攻撃は，近年，著しく発展しており，その説明も加える．

　まず，量子計算による暗号の安全性解析に関して，簡単にその歴史を紹介する．1985年のDeutschによる量子チューリング機械の提案から歴史は始まる．1994年に，Simonのアルゴリズム（周期関数の位数発見）⁽³⁾，Shorのアルゴリズム（素因数分解，離散対数問題）⁽⁴⁾が提案された．Shorのアルゴリズムは，隠れた位数を発見するアルゴリズムであるが，このアルゴリズムにより，素因数分解，（だ円）離散対数問題を解くことが（量子）多項式時間で可能である．更に，理論的な整備により，可換群上での隠れ部分群問題にまで拡張されている．

　研究の別の流れとして，1996年にGroverによりデータベース探索問題に対する量子アルゴリズム⁽⁵⁾が提案されている．Groverのアルゴリズムは，共通鍵暗号の秘密鍵探索に自明な形で適用可能である．更に，ハッシュ関数の衝突発見にも応用されている．共通鍵，ハッシュ関数の内部構造が一切使えない状況においては，解読の高速化が可能である．

　最近になり，Simonのアルゴリズムを適用することによる共通鍵暗号への攻撃も示されている^(6),(7)．当初は，特定の暗号構成のみに有効な攻撃であったが，Groverのアルゴリズムと組み合わせることにより，幅広い暗号利用モードに適用可能である⁽⁸⁾．