本格的な量子コンピューターは、数十年とは言わないまでも、まだ数年先です。しかし、開発者たちは長い間、そのキラー アプリがインターネットやその他の場所で暗号化されたメッセージを解読するだろうと考えてきました。その見通しは、暗号学者に刺激を与えました。今週、カリフォルニア州サンタバーバラで開催される会議で、彼らは、量子コンピューターでさえクラックできない方法でメッセージを暗号化するための約 20 のスキームについて話し合う予定です。
このワークショップは、米国立標準技術研究所 (NIST) が推進する、いわゆるポスト量子暗号の標準化の一環です。このような量子コンピューターは決して存在しない可能性があるため、数年にわたる取り組みは時期尚早で少し妄想的に聞こえるかもしれません。しかし、暗号学者は、今こそ準備を整える時だと言います。特に、機密性の高い通信を今すぐ記録し、後で解読することができるからです。オランダのアイントホーフェン工科大学の暗号学者、Tanja Lange は、「量子コンピューターができるまで待っていたら、手遅れです」と言う。 「ポスト量子暗号がない日は、データが漏えいする日です。」
何千億ドルもの電子商取引が、公開鍵暗号と呼ばれる潜在的に脆弱なスキームに依存しています。それらは「トラップドア」計算に基づいています。これは、逆方向よりも前方向に作業する方がはるかに簡単であるためです。受信者のアリスは、数値の公開鍵と、送信者のボブがメッセージをスクランブルするために使用するレシピを提供します。盗聴者の Eve は、Bob の計算を簡単に逆にしてメッセージを発見することはできません。ただし、アリスは公開鍵に数学的に関連付けられた秘密の秘密鍵も生成しており、ボブのような計算によってメッセージの暗号化を解除するのに役立ちます。
たとえば、RSA と呼ばれる一般的な公開鍵方式では、ボブは数値メッセージを、アリスが指定した回数だけ乗算することでスクランブルします。彼は結果を公開鍵 (2 つの素数を乗算して生成される巨大な数) で割り、アリスに剰余を送信します。メッセージを再構築するために、アリスは剰余を自分自身で別の回数 (その数が彼女の秘密鍵です) 掛け、公開鍵で割ります。出来上がり！ボブの元のメッセージが残りに飛び出します。アリスがボブに、ダイヤルを何回も前に回して南京錠の設定を隠す方法を教えているかのように、ダイヤルをさらに前に回して元の設定に戻す方法を知っています。 Eve は、ダイヤルをどこまで戻せばよいかを理解するのに苦労することしかできません。
RSA は、量子コンピューターがもたらす脅威も示しています。 Eve が公開鍵を要素素数に因数分解できれば、秘密鍵を盗んでコードをクラックできます。マサチューセッツ工科大学 (ケンブリッジ) の数学者 Peter Shor が 1994 年に示したように、大きな数の素因数分解は古典的なコンピューターにとっては困難ですが、量子コンピューターにとってはより簡単です。Shor のアルゴリズムを実行する量子コンピューターは、新しい公開鍵を無効にすることもできます。これは、除算と剰余の繰り返し操作でパターンを見つけるのに優れているためです。
リスクに対抗するために、暗号学者は脆弱性の少ないトラップ ドア アルゴリズムを開発しています。多くは、格子と呼ばれる幾何学的な構造に依存しています。これは、数百または数千の次元があることを除いて、結晶内の原子の繰り返し 3D パターンに似た点の配列です。ラティスは、パターンを作成するためにさまざまな組み合わせで追加できる一連の矢印またはベクトルによって定義されます。同じ格子の基底は、扱いやすい短いほぼ垂直なベクトル、または扱いにくい長いほぼ平行なベクトルで構成されます。
これらのスキームでは、アリスの秘密鍵は単純な格子ベースであり、彼女の公開鍵は同じパターンを定義する乱雑なものです。情報の各ビットを Alice に転送するために、Bob は多次元空間内の点の座標をアリスに送信できます。これは、格子内の点に近い場合はゼロを示し、格子点から離れている場合は 1 を示します。乱雑な公開鍵では、量子コンピューターでさえ、点が格子にどれだけ近いかを Eve に知らせることができませんでした。ただし、アリスは単純な秘密鍵を保持しているため、簡単にそれを行うことができます。ドイツのダルムシュタット工科大学のコンピューター科学者である Nina Bindel は、次のように述べています。
一部の研究者は、はるかに古いアルゴリズムを払いのけています。インターネット経由で一連のビットを送信したいが、いくつかの 0 と 1 が誤って反転するのではないかと心配しているとします。エラーを修正するために使用できる冗長性を備えた長い文字列を作成することで、これを防ぐことができます。このようなエラー訂正コードは、0 と 1 のグリッドまたはマトリックスで表すことができ、1970 年代に暗号学者はメッセージを暗号化できることを示しました。
このタイプのスキームでは、アリスの秘密鍵は誤り訂正行列であり、彼女の公開鍵はそれをスクランブルしたバージョンです。ボブのメッセージはビットの文字列であり、これにパブリック マトリックスを適用して別の文字列を取得します。彼は適切な測定のためにいくつかのランダムなビットを反転し、結果を Alice に送信します。ボブの乱雑なマトリックスを知っていても、イブは彼の動きを元に戻すことができません。しかし、これらの反転したビットを修正するために設計されたよりクリーンなものを使用すると、Alice はそれを実行できます。 Lange によると、誤り訂正スキームは格子よりも多くテストされており、たとえ量子コンピューターを持っていたとしても、Eve を裏切ることができます。
ほとんどのポスト量子アルゴリズムは、現在の標準よりも大きなキーまたはより多くの計算時間を必要とします。しかし、オランダのナイメーヘンにあるラドバウド大学の暗号学者であるシモーナ・サマルジスカとその同僚たちは、一連の二次方程式に基づいた機敏な小さな鍵スキームを開発しています。秘密のメッセージを送信するため。
他の公開鍵システムと同様に、ポスト量子スキームが解読不可能であるという証拠はなく、おそらく従来のコンピューターでも解読できません。そのため、現在のアルゴリズムを置き換える代わりに、新しいアルゴリズムがそれらと組み合わせて実行される可能性が高いと、ワシントン州レドモンドにある Microsoft の暗号学者 Brian LaMacchia は言います。
NIST は、早ければ 2022 年には、暗号化とデジタル署名用にそれぞれ 2 つまたは 3 つのアルゴリズムを標準化できると、メリーランド州ゲイザーズバーグにある NIST の数学者、ダスティン・ムーディは述べています。代理店はオプションを望んでいる、と彼は言います。 「すべての格子を破壊する新しい攻撃が見つかった場合でも、頼りになるものはまだあります。」 NIST は連邦政府の標準を設定していますが、「世界の多くは NIST が標準化した暗号化を使用しています」と Moody 氏は言います。 2,000 万の企業やその他の顧客にサービスを提供している、カリフォルニア州サンフランシスコのインターネット セキュリティおよびパフォーマンス企業である Cloudflare は、Web ブラウザのアルゴリズムの一部を使った実験をすでに開始しています。しかし、完全な移行には数年かかると、Cloudflare の応用暗号学者である Nick Sullivan 氏は警告しています。
LaMacchia 氏によると、過去 30 年間で暗号化に 4 つまたは 5 つの大きな変化が見られました。その中には、10 年前に RSA から数学的に関連しているがより安全な後継者に移行する動きも含まれていました。 「これは質的に異なります。はるかに複雑です。」暗号化のユーザー、つまりほぼ全員が、気付かなくても変更がうまくいったことを知るでしょう。
