プレゼント、ギフト64、およびレクタングル: 3 つはすべて、AES を使用した場合よりも高速で少ない計算リソースを必要とする組み込みシステムなど、「制約のある」環境で使用するために設計された軽量のブロック暗号です。 3 つはすべて SPN 構造に基づいており、学術的なデザインとして提案されています。関連する GIFT-128 は GIFT-COFB のコンポーネントであり、最近の NIST 軽量暗号コンテストのファイナリストでしたが、Ascon として知られるアルゴリズムに敗れました。
一方、PRESENT は ISO/IEC 29167-11:2014 および ISO/IEC 29192-2:2019 に記載されていますが、広く使用されていません。そもそも RECTANGLE が使用されているかどうかは不明です。 3 つのアルゴリズムはすべて学術的な設計であるため、広く分析されています。
統合された識別子: 本質的に、整数識別子の発見は大規模な最適化問題の一種であり、これを解決すると、ブロック暗号で使用される暗号化スキームを破るための強力なツールが提供されます。というタイトルの2018年の論文 統合識別子を簡単に見つける 古典的なコンピューティングを使用して、数十のアルゴリズムの積分識別子を見つけたと報告しました。この研究には、9 月の論文で研究されたアルゴリズムである PRESENT、GIFT64、および RECTANGLE の 9 ラウンド識別子が含まれていました。
混合整数線形計画法: 通常 MILP と略される混合整数線形計画法は、複雑な問題を解決するための数学的モデリング手法です。 MILP では一部の変数を非整数にすることができ、これにより他の方法に比べて柔軟性、効率性、最適化が実現します。
専門家が意見をまとめる
9 月の論文の主な貢献は、研究者らが前述の 3 つのアルゴリズムの最大 9 ラウンドで積分識別子を見つけるために使用したプロセスです。論文の大まかに翻訳されたバージョン（5月のものではなく、正しいバージョン）によると、研究者たちは次のように書いています。
従来の暗号解析手法にインスピレーションを得て、私たちは対称暗号解析のための新しい計算アーキテクチャである量子アニーリング-古典混合暗号解析 (QuCMC) を提案しました。これは、量子アニーリング アルゴリズムと従来の数学的手法を組み合わせたものです。このアーキテクチャを利用して、最初に除算プロパティを適用して、SPN 構造対称暗号アルゴリズムの線形層と非線形層の伝播規則を記述しました。
その後、SPN 構造識別子検索問題は混合整数線形計画法 (MILP) 問題に変換されました。これらの MILP モデルはさらに D-Wave 制約付き 2 次モデル (CQM) に変換され、量子ゆらぎによって引き起こされる量子トンネル効果を活用して極小解を回避し、攻撃されている暗号アルゴリズムの積分識別子に対応する最適解を達成しました。 D-Wave Advantage 量子コンピュータを使用して行われた実験では、PRESENT、GIFT-64、RECTANGLE の 3 つの代表的な SPN 構造アルゴリズムに対する攻撃の実行に成功し、最大 9 段の積分識別器の探索に成功しました。実験結果は、量子アニーリング アルゴリズムが、極小値を回避する能力と解決時間の点で、シミュレーテッド アニーリングなどの従来のヒューリスティック ベースの大域最適化アルゴリズムを上回ることを示しています。これは、実際の量子コンピューターを使用した、複数の本格的な SPN 構造の対称暗号アルゴリズムに対する最初の実際的な攻撃となります。
さらに、これは、複数の SPN 構造の対称暗号アルゴリズムに対する量子コンピューティング攻撃が従来の数学的手法のパフォーマンスを達成した最初の例です。
この論文では AES や RSA については言及されておらず、何かを壊すとは決して主張していません。代わりに、D-Wave 対応の量子アニーリングを使用して積分識別子を見つける方法について説明します。従来の攻撃には、長年にわたり、同じ統合識別子を見つけるための最適化された機能が備わっていました。カナダのウォータールー大学で PQC を専門とするデビッド・ジャオ教授は、この研究を新しい鍵開け技術の発見に例えました。最終的な結果は同じですが、方法は新しいものです。彼は次のように説明しました。