Quantum-Aware Key Rank for Side-Channel Attacks evaluation

デジタルセキュリティの世界において、秘密鍵の強さは、数学を解くのではなく、マシンに「耳を傾ける」ことによって試されることがよくあります。コンピュータがデータを暗号化するとき、その消費電力や電磁信号を通じて、ごくわずかな情報が漏洩します。セキュリティの専門家は、これらの漏洩物である「トレース」を捉え、それを利用して可能な鍵のリストを絞り込みます。正しい鍵を即座に見つけ出すのではなく、これらの攻撃は通常、長い順序付けられた候補リストを残し、真の鍵はその中の中間付近に隠されています。このリストにおける真の鍵の位置を「ランク」と呼びます。ランクが低ければ鍵は見つけやすく、高ければ鍵は事実上安全です。何十年もの間、セキュリティ研究所は、攻撃者が残りの可能性を探索するために標準的なコンピュータを使用すると仮定して、このランクを測定し、デバイスの安全性を判断してきました。

しかし、量子コンピュータの登場により、ゲームのルールが変わろうとしています。これらのマシンは異なる物理原則に基づいて動作しており、理論的には、古典的なコンピュータよりもはるかに速く可能性のリストを探索できます。イェフゲン・コトゥクによる新しい研究は、私たちの理解における決定的な空白、すなわち、攻撃者が初期の手がかりを集めるために古典的なコンピュータを使用し、その後、作業を完了させるために量子コンピュータに切り替えた場合に何が起こるのか、という問題に取り組んでいます。研究の結果、量子コンピュータが提供するスピードアップは、以前のいくつかの理論が示唆していたほど劇的でも普遍的でもないことが明らかになりました。結局のところ、その優位性は、残された候補の数と、量子コンピュータにどれだけの時間が許容されるかに完全に依存するのです。

研究者たちは、この特定の種類のハイブリッド攻撃者をシミュレートするために、詳細なモデルを構築しました。ハッカーがまずデバイスから電力トレースを収集し、標準的なソフトウェアを使用して潜在的な鍵のランク付きリストを作成するシナリオを想定しました。このリストには数十億の候補が含まれる可能性があります。その後、ハッカーはこのリストを取り出し、量子アルゴリズムを実行して正しい鍵を見つけ出します。研究は、特定の数の候補が残っている単一のデバイスに対して、量子コンピュータが提供するスピードアップは、その数の平方根に正確に比例することを証明しています。つまり、古典的なコンピュータが100万個の鍵をチェックする必要がある場合、量子コンピュータは1,000個だけチェックすればよいかもしれません。これは大幅な改善ですが、以前のより抽象的な理論が予測していたような、魔法のような指数関数的な速度の爆発ではありません。それらの古い理論は、量子コンピュータはさらに高速になり得ると示唆していましたが、今回の新しい研究は、それらの予測が個別の攻撃の現実を見るのではなく、多くの異なるデバイスにわたって結果を平均化したものであることを示しています。

この研究の極めて重要な部分は、量子コンピュータの物理的な限界に関わるものです。これらのマシンはまだ完璧ではなく、繊細な量子状態が崩壊してしまう前に、実行できる操作の数に制限があります。研究者たちは、将来の量子コンピュータが1年または10年間に実行できる最大ステップ数を示す、量子回路の「深さ」に対する厳格な制限を適用しました。彼らは、量子的なスピードアップが機能するのは、残りの鍵の数が特定の閾値を下回る場合のみであることを発見しました。もし候補リストが長すぎる場合、量子コンピュータは時間制限内に収まるために、自身のコピーを多数並列で実行することを余儀なくされます。この並列化がスピードの優位性を食いつぶし、その恩恵を単純な定数倍の係数へと減少させます。AES-128のような現代の暗号規格では、この優位性の「窓」は、鍵のランクが2の59乗付近に達したときに閉じます。この点を超えると、量子コンピュータはもはや指数関数的に速くなることはなく、単なる固定倍数の速さとなり、場合によってはその優位性は極めて小さく、ほとんど意味をなさなくなります。

セキュリティ研究所がこの新しい現実に適応できるよう、著者は「量子認識型鍵ランク（quantum-aware key rank）」と呼ばれる新しい指標を導入しました。このツールを使用すると、評価者はすでに算出している標準的なランクを取り、特定の時間制限を持つ量子攻撃者に対するセキュリティレベルを反映した値に変換することができます。例えば、あるデバイスの古典的なランクが安全であることを示していても、量子認識型ランクを用いれば、量子コンピュータが許容された時間内に鍵を見つけ出せるため、実際には脆弱である可能性があることが示されるかもしれません。研究は、この変換のための明確な公式を提供しており、量子的な敵対者に対して同じレベルのセキュリティを維持するためには、以前考えられていたよりもはかに高い古典的ランクが必要であることを示しています。具体的には、深さが2の40乗に制限された量子コンピュータに対して、あるデバイスが2の48乗の古典的ランクを持つデバイスと同等のセキュリティを保つためには、約2の74乗の古典的ランクを保持する必要があります。

また、研究では、量子コンピュータが漏洩した情報を利用して鍵を見つける2つの異なる方法についても比較を行いました。一つの方法は、各鍵の尤度を反映した特別な量子状態を準備することであり、もう一方は、構造化された方法で鍵のブロックを探索することです。研究によれば、典型的なデータ漏洩で見られるタイプのデータにおいては、これら2つの手法の性能は非常に近いことが分かりました。決定的な要因は、どちらの手法が理論的に速いかではなく、より複雑な手法を実装するために必要なハードウェアのコストです。研究者たちは、小さなトイ・サイファー（模型的な暗号）と現実的なAES暗号モデルを用いてこれらの攻撃をシミュレートし、自らの理論を確認しました。その結果、低S/N比（信号対雑音比）を伴う典型的な攻撃において、大きなゲート予算を持つ量子攻撃者は、古典的な攻撃者に対して約22個の追加の電力トレース分の価値があることを発見しました。言い換えれば、量子の優位性は実在しますが、それは限定的であり、予測可能なものです。

この研究は、セキュリティコミュニティにおける2つの相反する見解の間の緊張を解消するものです。一つは、量子コンピュータが超高速の指数関数的な優位性を提供すると主張する見解であり、もう一つは、ハードウェアの制限により優位性が全く得られない可能性を示唆する見解です。研究は、両方の見解が正しく、ただしそれぞれ異なる状況に適用されることを示しています。超高速の優位性は多くのシナリオにわたる「平均」であり、限定的で二次的な優位性は、個別の、現実世界の攻撃において起こる現象です。具体的な指標と明確な限界を提供することで、この研究は、セキュリティ評価者にリスクを正確に評価するためのツールを与えます。これにより、議論は推測から計算へと移行し、量子技術が成熟するにつれて、私たちの防御策を当て推量ではなく、精密さを持って調整できるようにするのです。