ポスト量子暗号の概要

ポスト量子暗号とは

多くの既存暗号アルゴリズムを破ることができる、新しいタイプのコンピュータが開発されています。そのため、そのようなコンピュータに対して安全であり、さらに 既存のコンピュータでも実行できる、新たなアルゴリズムを開発する必要があります。これを「ポスト量子暗号」と呼びます。

量子コンピュータとは

1981 年、リチャード・ファインマンは、複雑な系における量子相互作用をモデル化する新しい方法を提案しました。ここで問題となったのが、相互作用をモデル化する場合は各結合粒子を確率集合として表現する必要があるという点です。粒子を追加すると、配列は指数関数的に増加します。大規模システムの場合、既存のコンピュータではストレージや時間に関する要件を満たすことができません。

これに対するファインマンの提案はとてもシンプルなものでした。それが、対象となる物理オブジェクトのモデル化に量子もつれオブジェクトを使用するコンピュータの構築です。このコンピュータを使用することで、多数のタスクを効率的に処理でき、量子もつれの状態変化を利用する方法が明確になりました。

量子ビットとは

量子コンピュータの背景には、古典的なビットを「量子ビット」に置き換えるという考え方があります。古典的なビットは 0 または 1 ですが、量子ビットは 1 または 0 になる確率があり、通常は 3 次元領域の単位ベクトルで表現されます。量子ビットのパワーは 1 ビットではなく、もつれ合う複数のビットのパワーになります。問題の解において量子ビットが相互に干渉し合うアルゴリズムを考案できれば、即時に解の状態に到達するように量子ビットを強制できます。

暗号化における量子コンピュータの役割

ファインマンが量子コンピュータを提案した当時、そのコンピュータは誰にも実現できませんでした。しかし、研究者は量子コンピュータの 構築方法 だけでなく、利用方法 にも注目しました。

1994 年、ピーター・ショアは、量子コンピュータを用いて RSA およびディフィー・ヘルマン暗号化システムを破ることができるアルゴリズムを特定しました。その後、ショアのアルゴリズムは ECC (楕円曲線暗号) の解読も可能になりました。これらのアルゴリズムは、すべての公開鍵交換および電子署名アルゴリズムのビルディングブロックです。この時点で、プライマリー公開鍵システムの安全性が確保されるのは、大規模かつ実用的な量子コンピュータが実現されるまでだということが明らかでした。(現時点でジョブの実行に使用できる量子コンピュータは存在しますが、既存アルゴリズムのリスクになるには規模が足りません。)

古典的なアルゴリズムは破られる可能性があるため、量子コンピュータが容易に解決できない問題に基づく新たなアルゴリズムが必要となるはずです。それがポスト量子暗号です。新しいアルゴリズムは、既存コンピュータ上で実行されます。また、古典的なコンピュータと量子コンピュータの両方が容易に解決できない問題に基づいています。

ポスト量子暗号に注意すべき理由

暗号は現代社会に浸透しています。たとえば Web でクレジットカード番号を入力すると、その通信は暗号化されたチャネルで保護されます。これは、電子署名 (正しいベンダーにクレジットカードを渡していることを確認するため) と公開鍵交換 (クライアントとサーバー間の通信暗号化で使用する鍵に合意するため) の両方に依存します。しかし、十分な規模の量子コンピュータを構築する場合、通常の TLS (Transport Layer Security) で得ることができるセキュリティ保証は、どれも当てにできません。一部のディスク暗号化でも、ユーザーがパスワードを忘れた場合は公開鍵を使用して復旧システムを提供します。

一般的なユーザーにとって、使用しているシステムの中で脆弱である可能性のあるものを特定できることは、最重要事項のひとつです。企業の IT 部門にとっては特に重要です。

注意すべきタイミング

ポスト量子暗号に関する講演や記事では、モスカの定理を使用してこの質問に答えています。

新アルゴリズムへの移行時間 (y) と機密を保持する時間 (x) の合計が、公開鍵アルゴリズム (z) を破ることができる量子コンピュータが出現するまでの残存時間より大きい場合、データの有用性が失われる前にデータは危険にさらされます。問題なのは、このような数字の多くが確定されていない点です。

通常、機密保持が必要な時間 (x) はアプリケーションに基づき判断できます。たとえばインターネット上のクレジットカードの場合、カードの有効期限にもよりますが、2 年または 3 年です。一方、医療データについては数十年になることもあります。

さらに、一部の団体 (政府や民間) が TLS セッションを記録するようになったため、TLS セッションが短命でも、将来的にそのデータが保存および暗号化される可能性があるという事実が、この問題を複雑にしています。たとえば、あなたは権威主義国家で支援活動をしており、あなたと共に活動することで逮捕される可能性があるとします。その場合、VPN や TLS 接続を信頼して協力者の名前やその他の個人情報を送信することはしないはずです。この時間値は自分で制御できますが、どれぐらいの期間、どのような相手に対して特定のデータの機密性を保持するか評価する必要があります。

標準化から実際のデプロイメントまでを含むデプロイ期間 (y) は長くなる可能性があります。場合によっては数十年になることもあるでしょう。暗号化コミュニティは、長年にわたり新しい規格の提案に取り組んでいますが、ようやく標準化の実現を期待できそうです。唯一ここでユーザーが制御できるのは、アルゴリズムとプロトコルが使用可能になった後、いかに迅速にシステムを導入するかという判断だけです。

しかし現時点で、既存アルゴリズムを破ることができる量子コンピュータが出現するまでの時間 (z) は最大の不確定要素です。2015 年に、ウォータールー大学の量子コンピューティング研究者であるミシェル・モスカは、2048 ビット RSA が 2026 年までに脆弱になる確率は 7 分の 1、2031 年までに脆弱になる確率は 50% と試算しています。2017 年にモスカは、2048 ビット RSA が 2027 年までに脆弱になる確率を 6 分の 1 に更新しました。量子コンピューターの研究は加速し、IBM や Google などの企業は、自社や顧客が抱える難問を解決するための実験的な小規模量子コンピュータの構築に取り組んでいます。

その結果、現時点で注意すべき点がいくつかありますが、ポスト量子アルゴリズムが実際にデプロイされるまでは心配する必要ありません。

ポスト量子アルゴリズムがデプロイに至っていない理由

暗号化コミュニティは、以前からこの問題を認識しています。良い知らせとしては、既存の鍵交換や署名アルゴリズムに置き換わる新しいアルゴリズムがいくつかあります。悪い知らせとしては、研究し尽くされたアルゴリズムには、そのデプロイを妨げる大きな障壁が必ず存在します。つまり、鍵のサイズか暗号化されたデータ/署名のサイズ、もしくはその両方が大きすぎる (場合によってはメガバイト規模) という問題です。コミュニティは 10 年ほど前から、巨大な鍵やデータブロブを持たない有望な新しいアルゴリズムの研究を続けてきました。今後の記事では、その一連のアルゴリズムについて詳しく述べますが、いくつかの事実をここで簡単に紹介します。

2016 年、米国国立標準技術研究所 (NIST) は、見込みのあるアルゴリズムを集めて評価するためのポスト量子暗号標準化プロセスを開始しました。82 個の提出があり、そのうち 69 個は 2017 年末に完了とみなされました。評価は 2018 年に実施され、今年の初めには 2019 年を通して改良および評価を行うために 30 個のアルゴリズムが選択されました。

当初に集まった 69 個のアルゴリズムについては、その多くが期間内に破られ、69 個のアルゴリズムの内 26 個が ２ 回目の評価に進むために選出されました。NIST は 2020 年に 最終評価に進む 7 個のアルゴリズムと、補欠の 8 個を選出しました。選出された 15 個のアルゴリズムのうち 3 個がすでに破られています。破られたアルゴリズムの数は、このプロセスを慎重に進める必要があることを裏付けています。

NIST は 2022 年に最終選考を行い、選考が終了したら標準化プロセスを開始するだろうと予想されています。プロセスが完了すると、TLS などのプロトコルによる選択と、ベンダーによるデプロイが可能になります。

何をするべきか

まず、使用しているアルゴリズムのうち破られた可能性があるものを特定し、そのアルゴリズムが長期データを保護していないか確認する必要があります。つまり、以下の使用を調査する必要があります。

• RSA、DSA、ECC、DH：実際の脆弱なアルゴリズム

• TLS、SSH、S/MIME、PGP、IPSEC：脆弱なアルゴリズムに依存するプロトコル

• VPN、Kerberos：脆弱なアルゴリズムに依存している可能性のあるプロトコル

• ブラウザ、暗号化されたメッセージング、ディスク暗号化、認証スキーム：上記のプロトコルや脆弱なアルゴリズムを使用している (可能性のある) アプリケーション

以下を行う必要があります。

1. ユーザーが長期データを保護しようとしていないか確認します。

2. ポスト量子アルゴリズムの使用が可能になり次第、脆弱なアルゴリズムと置き換えるための計画を作成します。最も機密性の高いデータを保存または転送するシステムを優先します。その場合、古いオペレーティングシステムだけでなく、古いハードウェアも更新することになる可能性があります。

3. 自分で制御できないシステム (サードパーティの Web サイトなど) を特定し、そのシステムへのアクセスを抑制する方法を計画します。

残念ながら、このような新しいアルゴリズムはまだ使用できず、規格が更新されるまで使用できるようにもなりません。しかし、どこにあるかを認識することで、少なくとも潜在的な露出を抑制できます。詳細については、Matt Schroll 氏 (NIST) との Q&A を参照してください。

次のステップ

今後のブログでは、新しいポスト量子アルゴリズムがどのように機能するのか、また実装およびデプロイで注意すべき点について説明する予定です。