量子暗号解読
量子アルゴリズムで暗号を攻撃すること。今日の公開鍵暗号は壊滅するが、共通鍵暗号にとってはせいぜい厄介な程度である。
この分野は1994年に始まった。ショアのアルゴリズムが、素因数分解と離散対数が量子コンピュータ上で多項式時間で解けることを示し、RSAも楕円曲線暗号もまとめて破られることになったのだ。グローバーのアルゴリズムは総当たりに対して二次の高速化しか与えないため、共通鍵は鍵長を倍にすれば生き延びる。
本当に厄介な結果はサイモンのアルゴリズムから出てきた。2010年に桑門と森井がこれで3段のFeistel暗号を破り、2016年にはKaplan、Leurent、Leverrier、Naya-Plasenciaが、攻撃者が重ね合わせ状態で問い合わせを送れるならCBC-MAC、GMAC、OCBが崩れることを示した。この攻撃モデルには異論がある。量子的な問い合わせに答える実システムはほとんどないからだ。それでも、利用モードそのものが周期を漏らすなら鍵長を倍にしても足りないことは証明された。