Last Updated on 2024-05-28 22:41 by admin
量子コンピュータが将来的に現在の公開鍵暗号アルゴリズムを破る可能性があるため、暗号学者は量子耐性のある公開鍵アルゴリズムの開発に取り組んでいる。2017年から、米国国立標準技術研究所（NIST）はこの目的のためのコンペティションを主催しており、既にいくつかの提案された標準がある。これらのほとんどは格子問題に基づいている。格子暗号の数学は、多次元空間内のベクトルの集合、つまり格子を組み合わせることに関連している。この格子は多次元の周期性を持っている。暗号学で使用される難問は、大きくランダムに見える格子内で最短の周期性を見つけることである。これは、さまざまな方法で公開鍵暗号システムに変換することができる。研究は1996年から続けられており、それ以来、多くの実用的な公開鍵アルゴリズムが開発されている。
2024年4月10日、北京の清華大学のYilei Chenは、その最短経路格子問題に対する新しい量子攻撃を記述した論文を投稿した。この論文は非常に数学的であり、63ページにわたるが、その詳細をすべて理解できる暗号学者は少ないだろう。しかし、その結論は、格子ベースの完全準同型暗号スキームを事実上破り、最近提案された（そしてNISTによって承認された）格子鍵交換および署名スキームに対する攻撃にかなり近づいたというものだった。しかし、論文の37ページの下部に小さなが重要な誤りがあった。この誤りは、ベルケリーのHongxun Wuとイスラエルのワイツマン研究所のThomas Vidickによって8日後に独立して発見された。現在の形では攻撃アルゴリズムは機能しない。この結果は、RSAカンファレンスでの暗号学者パネルで先週議論された。
Adi Shamir（RSAの「S」であり、2002年にACMのA.M. Turing賞を受賞）は、この結果が格子ベースのアルゴリズムに対する量子暗号解析についてまだ多くの発見があることを示す心理的に重要であると述べた。Craig Gentry（格子を使用した最初の完全準同型暗号スキームの発明者）は、機能しない攻撃は何も変えないと基本的に言っていた。量子暗号解析に関する研究はまだ多くの未探索の研究領域があることを示している。しかし、理論上でさえ、任意の量子攻撃を機能させることは多くの困難が伴う。格子ベースの暗号を量子コンピュータで破るには、RSAを破るよりもはるかに多くの量子ビットが必要であるため、Chenのようなアルゴリズムを現在の技術でテストすることは完全に不可能である。しかし、エラーは数学的な性質のものであり、実験を必要としなかった。Chenのアルゴリズムは9つの異なるステップで構成されており、最初の8ステップは特定の量子状態を準備し、9番目のステップはそれを利用することを意図していた。誤りは9ステップ目にあり、Chenは彼の波動関数が周期的であると信じていたが、実際にはそうではなかった。
NISTが量子暗号化標準化プロセスで何か異なることをすべきかという問いに対する答えは否である。新しいアルゴリズムの選択において素晴らしい仕事をしており、この新しい研究のために何も遅らせるべきではない。また、暗号のユーザーは新しいNISTアルゴリズムの実装を遅らせるべきではない。しかし、この誤りがまだ発見されていなかったら、このエッセイはどれほど異なっていただろうか？この作業は、研究が続くにつれてアルゴリズムを容易に入れ替えることができるように、システムが暗号アジャイルである必要があることを強調している。また、TLSのように、セキュリティが最も強いものに依存する複数のアルゴリズムを使用するハイブリッド暗号を可能な限り使用することが望ましい。そして、最後に、査読に対する賛辞がある。研究者が新しい結果を提案し、レビュアーが作業の致命的な欠陥を迅速に見つけた。欠陥を修正する努力が進行中である。査読については多くの不満があるが、ここではそれが意図された通りに機能した。
【ニュース解説】
量子コンピュータの登場が予測される中、現行の公開鍵暗号アルゴリズムが破られる可能性に備え、暗号学者たちは量子耐性のある新しい公開鍵アルゴリズムの開発に取り組んでいます。この分野での主要な研究の一つが、格子ベースの暗号システムです。格子暗号は、多次元空間内のベクトルの集合（格子）を利用し、その中の最短周期性を見つけ出すことが難問とされています。この問題を解決することが、公開鍵暗号システムの構築につながります。
2024年4月、清華大学のYilei Chen氏が提出した論文では、格子ベースの暗号システムに対する新たな量子攻撃が提案されました。この攻撃は、完全準同型暗号スキームを含む多くの格子ベースの暗号システムを破る可能性があるとされました。しかし、論文には重要な数学的誤りが含まれており、攻撃アルゴリズムは実際には機能しないことが後に明らかにされました。
この出来事は、量子暗号解析の分野においてまだ多くの未解決の問題が存在することを示しています。特に、格子ベースの暗号システムに対する効率的な量子攻撃の構築には、さらなる研究が必要であることが示唆されています。量子コンピュータを用いた攻撃は、理論上でも実際にも多くの困難を伴いますが、この分野の研究は重要な意味を持ちます。
NISTによる量子耐性暗号の標準化プロセスは、この新しい研究によって変更されるべきではありません。新しいアルゴリズムの選定において、NISTは適切な仕事をしており、暗号のユーザーも新しいアルゴリズムの実装を遅らせるべきではありません。この事件は、暗号システムが柔軟にアルゴリズムを入れ替えられるようにすること（暗号アジャイル）、そして可能な限りハイブリッド暗号を使用することの重要性を強調しています。
また、この出来事は、査読の重要性を再確認させるものでもあります。新しい研究結果が提案された際に、査読によって迅速に致命的な欠陥が見つかり、修正の努力が進行中であることは、科学的研究の健全性を保つ上で不可欠です。このようなプロセスを通じて、より安全で信頼性の高い暗号技術の発展が期待されます。
from Lattice-Based Cryptosystems and Quantum Cryptanalysis.
