NIST、PQC Round4候補のSIKEに欠陥か

日付:2022-08-05 提供:Quantum Computing Report 翻訳:Hideki Hayashi

先月、NISTがラウンド3で4つのポスト量子暗号(PQC)アルゴリズムを標準化対象として選定し、ラウンド4でさらに4つのアルゴリズムが選定されたことをお伝えした。新たな研究のために選ばれたアルゴリズムの1つが、SIKE(Supersingular Isogeny Key Encapsulation)である。SIKEは、第3ラウンドのKEMアプリケーションに選ばれた格子ベースのKyberアルゴリズムとは根本的に異なるアプローチ(Supersingular Isogeny)に基づく、鍵カプセル化(KEM)アルゴリズム。NISTは、Kyberに問題が見つかった場合に、はるかに異なる代替手段を提供できる可能性があるため、異なるアプローチを肯定的にとらえている。また、NISTはSIKEを、鍵のサイズと暗号文のサイズが小さいという点で魅力があるとしている。


しかし今回、KUルーヴェンの研究者が、Magmaと呼ぶプログラムを用いて、シングルコアプロセッサを用いたSIKEp434、セキュリティレベル1に対する効率的な鍵回復攻撃を約1時間の時間で発見できたとする予備論文を発表した。このような欠陥は、アルゴリズムの小さな修正で直ることもある。しかし、修正できない場合は、SIKEアルゴリズムはPQC標準化のさらなる検討対象から外れることになる。今年の初めには、Rainbowというデジタル署名アルゴリズムに欠陥が見つかり、Round 3で落とされた。今はまだ、SIKEアルゴリズムの最終的な運命がどうなるかを知るには時期尚早だろう。しかし、研究者が「クリプトアジリティ(crypto-agility)」と呼ぶ、問題が発見された場合にアルゴリズムを簡単に変更できるようにするためのケースであることは確かだ。また、単一障害点が存在するような状況を避けるために、他の技術にも目を向けるべきであると説いている。このキーリカバリ攻撃について説明したプレプリントの要旨はこちら、プレプリント全文はこちらのリンクを参照。


この攻撃についてより詳しく説明した長文の記事は現在準備中。