一般的な迷信に反して、AES 128 はポスト量子の世界ではまったく問題ありません

ヴァルソルダ氏は月曜日、ついに「量子コンピュータは128ビット対称鍵に対する脅威ではない」というタイトルのブログ投稿で、広まった誤解によって煽られた長年の不満を晴らした。

「量子コンピュータは対称鍵のセキュリティを『半分』にし、128ビットのセキュリティには256ビットの鍵が必要になるという誤解がよくある」と同氏は書いている。 「これは量子アルゴリズムによってもたらされる高速化の正確な解釈ではなく、コンプライアンス義務にも反映されておらず、本当に必要な量子移行後の作業からエネルギーと注意をそらす危険性があります。」

それは議論の簡単な部分です。はるかに難しいのは、それを説明する数学と物理学です。最も高いレベルでは、ブルート フォース検索が古典的なコンピューターでどのように機能するか、グローバーのアルゴリズムを使用してどのように機能するかという根本的な違いに要約されます。従来のコンピューターは複数の検索を同時に実行できます。これにより、大きなタスクをより小さなチャンクに分割して、ジョブをより速く完了できます。対照的に、Grover のアルゴリズムでは、各検索が一度に 1 つずつ実行される、長時間実行されるシリアル計算が必要です。

「Grover が特別なのは、並列化すると非量子アルゴリズムに対する利点が小さくなることです」と Valsorda 氏はインタビューで述べました。彼はこう続けた。

小さな数字で想像してみてください。ロックには 256 通りの組み合わせがあるとします。通常の攻撃には 256 回の試行が必要です。それは長すぎると判断したため、3 人の友人がいて、それぞれ 64 回の試行が必要になります。 「これは古典的な並列化です。Grover を使用すると、理論的には √256)=16 回の試行を連続して行うことができますが、それでも長すぎる場合は、戻って 3 人の友人に助けを求めることになります。各人は √256/4)=8 回の試行を行う必要があります。

つまり、合計 8*4=32 回の試行を行うことになります。これは、単独で行う場合の 16 回よりも多くなります。攻撃を並行して支援を求めると、攻撃が全体的に遅くなりました。従来の攻撃ではそうではありません。

もちろん、その数ははるかに大きくなりますが、攻撃者に合理的な制約 (10 年以内にレースを完走しなければならないなど) を適用すると、総作業量は 2 をはるかに超えます。⁶⁴。

また、2⁶⁴ これは、単一の量子ビットに対する単一の操作として AES を実行できるかのように装うため、決して正しい数値ではありませんでした。これはある程度直交しています。これら 2 つの観測結果を組み合わせると、実際のコストは 2 になります。¹⁰⁴ 譲るかどうかは別として、それはセキュリティのしきい値をはるかに超えています。

Googleの上級暗号技術者であるソフィー・シュミーグ氏は、次のように説明しています。