暗号解読量子コンピュータに向けて | MIT ニュース

あなたが最近送信した電子メールは、おそらく、最も高速なコンピュータでも巨大な数字を効率的に因数分解することはできないという考えに基づいた、実績のある方法を使用して暗号化されたものです。

一方、量子コンピュータは、従来のコンピュータでは絶対に解読できない複雑な暗号システムを迅速に解読できると期待されています。この期待は、1994年に提案された量子因数分解アルゴリズムに基づいています。 ピーター・ショア、現在はMITの教授です。

しかし、研究者たちは過去30年間で大きな進歩を遂げてきたものの、ショアのアルゴリズムを実行できるほど強力な量子コンピューターをまだ構築できていない。

研究者の中には、より大きな量子コンピュータの構築に取り組む者もいる一方で、ショアのアルゴリズムをより小さな量子回路で実行できるように改良しようとしている者もいる。約1年前、ニューヨーク大学のコンピュータ科学者オデッド・レゲフは、 大きな理論的改善彼のアルゴリズムはより高速に実行できるが、回路にはより多くのメモリが必要になる。

MIT の研究者は、これらの結果を基に、Regev のアルゴリズムの速度と Shor のアルゴリズムのメモリ効率を組み合わせた、両方の長所を兼ね備えたアプローチを提案しました。この新しいアルゴリズムは、Regev のアルゴリズムと同等の速度で、必要な量子ビットと呼ばれる量子構成要素が少なく、量子ノイズに対する耐性も高いため、実際に実装するのがより現実的になる可能性があります。

長期的には、この新しいアルゴリズムは、量子コンピューターの暗号解読力に耐えられる新しい暗号化方法の開発に役立つ可能性があります。

「もし大規模な量子コンピュータが構築されれば、因数分解は駄目となり、暗号化に何か別の方法を見つけなければなりません。しかし、この脅威はどれほど現実的なのでしょうか？量子因数分解を実用化することはできるのでしょうか？私たちの研究は、実用化に一歩近づく可能性があります」と、フォード財団工学教授で、コンピュータサイエンスおよび人工知能研究所（CSAIL）のメンバーであり、論文の主任著者であるヴィノド・ヴァイクンタナサンは述べています。 アルゴリズムを説明した論文。

この論文の主著者は、MIT電気工学・コンピュータサイエンス学部の大学院生、セユーン・ラガヴァン氏である。この研究は、2024年の国際暗号学会議で発表される予定である。

暗号解読

インターネット上で安全にメッセージを送信するために、電子メールクライアントやメッセージングアプリなどのサービスプロバイダーは通常、RSAに依存しています。 暗号化方式 1970 年代に MIT の研究者 Ron Rivest、Adi Shamir、Leonard Adleman によって発明されました (「RSA」という名前はここから来ています)。このシステムは、2,048 ビットの整数 (617 桁の数字) を因数分解するのはコンピューターが妥当な時間内に行うには難しすぎるという考えに基づいています。

その考えは1994年に、当時ベル研究所に勤務していたショアが量子コンピューターがRSA暗号を破るのに十分な速さで因数分解できることを証明するアルゴリズムを発表したときに一変した。

「あれは転換点でした。しかし1994年当時、十分な大きさの量子コンピューターを構築する方法を誰も知りませんでした。そして、私たちはまだそこにかなり遠いところにいるのです。量子コンピューターが構築される日が来るのだろうかと疑問に思う人もいるのです」とヴァイクンタナサンは言う。

量子コンピュータには約 2000万量子ビット ショアのアルゴリズムを実行する。現在、最大の量子コンピューターには約 1,100 個の量子ビットがある。

量子コンピュータは、古典コンピュータが古典回路を使用するのと同じように、量子回路を使用して計算を実行します。各量子回路は、量子ゲートと呼ばれる一連の操作で構成されています。これらの量子ゲートは、量子コンピュータの最小の構成要素である量子ビットを使用して計算を実行します。

しかし、量子ゲートはノイズを発生させるため、ゲートの数を少なくすればマシンの性能は向上する。研究者たちはショアのアルゴリズムを強化して、より少ない量子ゲートでより小さな回路で実行できるように努めてきた。

レゲフ氏が1年前に提案した回路はまさにそれだった。

「これは1994年のショアのサーキットに対する最初の本格的な改良だったので、大きなニュースでした」とヴァイクンタナサンは言う。

ショア氏が提案した量子回路のサイズは、因数分解される数の二乗に比例する。つまり、2,048 ビットの整数を因数分解する場合、回路には数百万のゲートが必要になる。

Regev の回路では必要な量子ゲートの数は大幅に少なくなりますが、十分なメモリを提供するにはさらに多くの量子ビットが必要になります。これにより、新たな問題が発生します。

「ある意味で、ある種の量子ビットはリンゴやオレンジのようなものです。そのままにしておくと、時間の経過とともに劣化します。保存しておく必要のある量子ビットの数を最小限に抑えたいのです」とヴァイクンタナサン氏は説明します。

彼は、昨年 8 月に行われたワークショップで、レゲフ氏がその成果について話すのを聞いた。講演の最後に、レゲフ氏は質問を投げかけた。「誰かが彼の回路を改良して、必要な量子ビットの数を減らすことはできるだろうか?」ヴァイクンタナサン氏とラガバン氏はその質問に取り組んだ。

量子ピンポン

非常に大きな数を因数分解するには、量子回路を何度も実行し、2 の 100 乗のような計算能力を必要とする操作を実行する必要があります。

しかし、量子コンピューターは可逆な演算しか実行できないため、このような大きな累乗を計算するのはコストがかかり、量子コンピューターで実行するのは難しい。数を二乗することは可逆な演算ではないため、数を二乗するたびに、次の二乗を計算するために量子メモリを追加する必要がある。

MITの研究者たちは、一連の フィボナッチ数列 これには、二乗ではなく、可逆な単純な乗算が必要です。彼らの方法では、任意の指数を計算するのに 2 つの量子メモリ ユニットだけが必要です。

「これはピンポンゲームのようなもので、数字から始めて、2つの量子メモリレジスタ間で乗算しながら前後に跳ね返ります」とヴァイクンタナサン氏は付け加えた。

彼らはまた、誤り訂正の課題にも取り組んだ。ショアとレゲフが提案した回路では、アルゴリズムが機能するためにはすべての量子演算が正確であることが必要だとヴァイクンタナサンは言う。しかし、実際のマシンでは誤りのない量子ゲートは実現不可能だろう。

彼らは、不正な結果を除外し、正しい結果のみを処理する技術を使用してこの問題を克服しました。

最終結果は、メモリ効率が大幅に向上した回路です。さらに、エラー訂正技術により、アルゴリズムの導入がより実用的になります。

「著者らは、以前の量子因数分解アルゴリズムにおける 2 つの最も重要なボトルネックを解決しました。まだすぐに実用化できるわけではありませんが、彼らの研究により量子因数分解アルゴリズムは現実に近づきました」と Regev 氏は付け加えています。

将来的には、研究者たちはアルゴリズムをさらに効率化し、いつかそれを使って実際の量子回路で因数分解をテストしたいと考えています。

「この研究の後に残る疑問は、これが実際に RSA 暗号の解読に近づくことになるのか、ということです。それはまだ明らかではありません。これらの改善は現在、整数が 2,048 ビットよりはるかに大きい場合にのみ有効になります。このアルゴリズムを推し進めて、2,048 ビットの整数に対しても Shor のアルゴリズムよりも実現可能にすることはできるでしょうか?」と Ragavan 氏は言います。

この研究は、Akamai Presidential Fellowship、米国防高等研究計画局、国立科学財団、MIT-IBM Watson AI Lab、Thornton Family Faculty Research Innovation Fellowship、および Simons Investigator Award の資金提供を受けて実施されています。