量子コンピューター、新しいアルゴリズムで予想より早く暗号を解読できる可能性

プラトン再発行

フォロワー： 0

将来の量子コンピューターの最も確立され、破壊的な用途の XNUMX つは、暗号化を解読する機能です。新しいアルゴリズムは、これを達成するための障壁を大幅に下げる可能性があります。

量子コンピューティングに関する誇大宣伝にもかかわらず、依然として大きな疑問符が付いています。量子コンピューターは実際に何に役立つのか。最適化プロセスから機械学習まであらゆるものを高速化できると期待されていますが、どれだけ簡単で高速になるかは多くの場合不明のままです。

ただし、かなり確かなことが XNUMX つあります。それは、十分に強力な量子コンピューターが、私たちの主要な暗号化スキームを無価値にしてしまう可能性があるということです。それらの基礎となる数学的パズルは古典的なコンピューターでは事実上解くことができませんが、十分な大きさの量子コンピューターであれば完全に解決可能です。これらのスキームではほとんどの情報がオンラインで保護されているため、これは問題です。

救いは、今日の量子プロセッサが必要とされる規模には程遠いということです。しかし、ある人によると、中で報告する科学, ニューヨーク大学のコンピューター科学者オデッド・レゲブ氏は、必要な量子ビットの数を大幅に削減できる新しいアルゴリズムを発見しました。

このアプローチは基本的に、これまでで最も成功した量子アルゴリズムの 1994 つを作り直したものです。 XNUMX 年、MIT のピーターショールは、特定の数を得るためにどの素数を掛け合わせる必要があるかを計算する方法、つまり素因数分解として知られる問題を考案しました。

多数の場合、これは非常に難しい問題であり、従来のコンピューターではすぐに対処できなくなります。そのため、一般的な RSA 暗号化スキームの基礎として使用されました。しかし、重ね合わせやもつれなどの量子現象を利用することで、ショールのアルゴリズムは、信じられないほど大きな数であってもこれらの問題を解決できます。

この事実は、セキュリティ専門家の間で少なからぬパニックを引き起こしている。とりわけ、今日ハッカーやスパイが暗号化されたデータを探し出し、それを解読するのに十分強力な量子コンピューターの開発をただ待つだけであるためである。また、ポスト量子暗号化標準は開発されていますが、Web 全体に実装するには何年もかかる可能性があります。

ただしかなり待ち時間が長くなる可能性があります。 RSA のほとんどの実装は、少なくとも 2048 ビットのキーに依存します。これは、617 桁の長さに相当します。富士通研究者最近計算した 10,000 量子ビットを備えた完全にフォールトトレラントな量子コンピューターで、これほど大きな数値を解読するには 104 日かかるということです。

ただし、Regev の新しいアルゴリズムは、に公開されたプレプリント arXivの、これらの要件を大幅に削減できる可能性があります。 Regev は基本的に Shor のアルゴリズムを作り直し、はるかに少ない論理ステップで数値の素因数を見つけることができるようにしました。量子コンピューターで演算を実行するには、単純な論理演算を実行するゲートと呼ばれる、数個の量子ビットから小さな回路を作成する必要があります。

Shor のオリジナルのアルゴリズムでは、数値を因数分解するために必要なゲート数は、その数値を表すために使用されるビット数の XNUMX 乗であり、次のように表されます。 n². Regev のアプローチで必要なのは、 n^1.5 これは、単一の数値の非常に大きな乗算ではなく、多くの数値の小規模な乗算を実行することによって素因数を検索するためです。また、古典的なアルゴリズムを使用して出力をさらに処理することにより、必要なゲートの数も削減されます。

Regev 氏は論文の中で、2048 ビットの数値の場合、これにより必要なゲート数が XNUMX ～ XNUMX 桁減少する可能性があると推定しています。これが本当であれば、はるかに小型の量子コンピューターでも RSA 暗号を解読できる可能性がある。

ただし、実際には制限があります。まず第一に、Regev 氏は、Shor のアルゴリズムは、実行に必要な量子ビットの数を削減するために長年にわたって開発された多数の最適化の恩恵を受けていると述べています。これらの最適化が新しいアプローチで機能するかどうかはまだ不明です。

スウェーデン政府の量子コンピューティング研究者であるマーティン・エケロー氏もこう語った。科学 Regev のアルゴリズムは中間値を保存するために量子メモリを必要とするようです。そのメモリを提供するには追加の量子ビットが必要となり、メモリが持つ計算上の利点が損なわれてしまいます。

それにもかかわらず、この新しい研究は、暗号化に対する量子コンピューティングの脅威に関して、次のことをタイムリーに思い出させてくれます。ゴールポストは常に動いている、ポスト量子スキームへの移行は十分に早く起こることはできません。

画像のクレジット：でログイン