近年、量子論と計算機科学の関係は、以前にも増して近くなっている。特に、従来のノイマン型の計算機に比べて、膨大な処理を可能にすると喧伝されている量子計算機は、D-WAVEなどの開発を始めとして注目を増しており、大きな発展が期待されている。
セキュリティの主要な道具である暗号技術でも、量子論との関係が注目を集めている。実は、量子論が暗号技術と関係するのは、2つの別のコンテクストがあり、これらが混同される場面が技術を紹介する際によくみられる。本稿では、量子論と暗号技術の2つのコンテクストのそれぞれを解説しながら、その現状を紹介する。
量子論が暗号技術に関係する2つのコンテクストとは、
- 量子力学の性質を利用して、より安全な暗号技術を作り出す「量子暗号」
- 量子計算機が登場したとしても安全性が損なわれない暗号通信を実現する「耐量子計算機暗号」
である。共に「量子」と「暗号」の文字が入っていて、時に注意深くない文章ではQuantum Cryptographyという英語の単語で混同して扱われることがあるが、この2つは別のものであるため、明確に区別する必要がある。
量子暗号がもたらす便益と実用上の制約
まずは量子力学の性質を利用して暗号技術を作り出す量子暗号について説明する。
もともと、現代暗号のほとんどは、計算量的安全性と呼ばれる安全性の評価方法を用いて安全性の評価をしている。これは、暗号技術の攻撃者が攻撃に使う計算能力は有限であり、その有限の計算能力に対して、暗号が破られる確率は0ではないが、その確率は極めて小さく実用上無視できる範囲に留められるかどうかを評価するというものである。一方で、ムーアの法則にしたがって、攻撃者の計算能力も上がるため、攻撃が成功する確率は徐々に上がってくる。そのような場合、鍵のサイズを増やすなどの方法で対処をしていく。このように、鍵のサイズなどのセキュリティパラメータを増やすことで、現実に存在する計算機では事実上攻撃は成功しないと考える。RSA暗号や、ビットコインに使われているECDSA署名、ビットコインで最近注目されているShnorr署名など、現実に使われている暗号技術は、ほとんど全て計算量的安全性の考え方に基づいて設計されている。
一方、情報理論的安全性という考え方がある。これは、情報理論に基づいて、無限の計算機能力があったとしても攻撃に成功しないことを保障しようというものだ。例えば、バーナム暗号は、暗号化する対象のメッセージと同じ長さだけの乱数列（これが鍵になる）を用意することができれば、情報理論的安全性を保つことができる。バーナム暗号の場合、対象となるメッセージと同じ長さの鍵を、暗号通信を行う者同士であらかじめ共有することが大きな問題となる。例えば、100MBのファイルを暗号化してやり取りしたいときに、情報理論的安全性を保ったまま、毎回異なる100MBのサイズの暗号鍵を通信を行う度に交換するのは現実的には難しい。これを解決するのが、量子暗号だ。現実には、暗号化の計算はバーナム暗号と同じ方式（ビット毎に、メッセージと鍵の排他的論理和を計算する方式）であるので、量子論が使われているのはその前の鍵交換の部分であり、量子暗号は量子鍵交換（QKD: Quantum Key Distribution）と呼ぶこともある。QKDにおいて計算量的安全性が確認されている方式として、BB84という方式があり、これは専用の通信路で光子を1つずつ送り、「盗聴されたら状態が変わってしまう」という光子の性質を用いて、盗聴されたビットを捨てて、盗聴されなかったビットだけで鍵を構成する方法だ。ただし、このような鍵交換を行うためには、特殊な通信路と特殊な装置が必要であり、1秒あたりに交換できる鍵のサイズ（これは、暗号化・復号のスループットに影響する）には上限があり、また鍵交換の装置同士の距離の上限もあり、それを超える場合には中継をしないといけないなど、実際に利用する場合の制約が大きく、インターネットだけで使えるようなものでもないため、軍事用途など、セキュリティに相応の費用を掛けることができる応用に限定されるのが現実だ。
量子計算機が暗号技術にもたらす影響
そして、もう1つの話題が、量子計算機の登場による計算量的安全性を有する暗号技術への影響である。これは、1994年にピーター・ショア（Peter Shor）が発表したアルゴリズム（とそのアルゴリズムを改変したアルゴリズム）を利用することで、現代の公開鍵暗号の安全性を支える数学的な問題である、離散対数問題や素因数分解問題がより効率的に解けることに由来している。また、1996年に発表されたGroverのアルゴリズム、1997年に発表されたSimonのアルゴリズムは共通鍵暗号における探索を効率化することで知られている。
一方で、一般に「量子計算機」と呼ばれる計算機にも大きくタイプがあり、量子ゲート型、量子アニーリング型、量子ニューラルネットワーク型などがある。最近話題になっているD-WAVEは量子アニーリング型であり、近年、大企業からスタートアップまで、さまざまな企業による量子計算機の開発のニュースで目にするものの多くは、このタイプである。一方で、上記のアルゴリズムが実行できるのは量子ゲート型である。この区別は非常に重要である。暗号技術への攻撃の文脈では、新しい量子計算機が、上記のアルゴリズムの実行に有効なタイプであるかどうかを確認する必要がある。
通常の暗号技術の計算量的安全性を議論するときに、鍵のサイズ（ビット長）がその議論の基準となるパラメータとなる。現在のコンセンサスでは、公開鍵暗号においては2,048ビットの鍵長を取ることが推奨されている。量子ゲート型の量子計算機では、量子ビット（qubit）という単位を用いるが、現在の2,048ビットの離散対数問題を解くのに必要とされるqubitは、4096 qubitという理論的見積もりが存在する[1]。現在、公に発表されている情報では、Googleが72 qubitの量子プロセッサBristleconeを発表している。しかし、実際に量子ゲート型の量子計算機を動作させる場合、物理的環境により計算途中での誤りが発生しやすく、そのような誤りに対する耐性を高める必要がある。ここが大きな実用上の技術的課題になっている。1 qubitの誤り訂正ですら、あと数年かかる状況だ。上記の点を考えると、量子ゲート型の量子計算機が現在使われている暗号技術の攻撃の成功に現実的に成功するにはまだ時間がかかると言える。
[1] John Proos and Christof Zalka. “Shor’s discrete logarithm quantum algorithm for el- liptic curves”. In: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario (Feb. 2008).
耐量子計算機暗号の現在の動向
量子計算機に関する研究開発の進展により、ゲート型の量子計算機でも解けない暗号の必要性が議論されている。ここでの焦点は、先にあげたアルゴリズムが存在しても効率的な解読法がない暗号技術を作ることだ。2015年にはアメリカ国家安全保障局NSAが耐量子計算機暗号への移行プランを発表し、関連の学術会議も開かれている。さらに米国連邦標準を定めるNISTが、標準化のための技術公募と評価を行なっている。
2018年8月に、暗号技術の世界最高峰の学術カンファレンスCRYPTO（Bitcoinより古い37年の歴史があり、暗号研究者にとっては”CRYPTO”はこの会議の名前であり暗号通貨のことではない）の併設ワークショップにおいて、NISTの担当者が評価の現状の説明を行なった。現在、82あった応募の中から、69の提案を第1ラウンドの候補として評価を行なっている。そのうち5つは、すでに取り下げられている。提案は、電子署名技術と、暗号化／鍵交換の2つのカテゴリに別れていて、それぞれ、耐量子計算機暗号を実現する基本的な方式として、格子理論に基づく方法、符号理論に基づく方法、多変数理論に基づく方法、ハッシュ関数／共通鍵暗号の基づく方法、その他からなっている。
2017年12月21日にNISTから69の候補が発表されたあと、世界中の研究者が安全性の解析を行い、その結果を発表している。最も早い発表は、NISTの発表の3日前の12月19日にHILA5が主張している安全性がないことを示す結果であり、最初の8日間で8つの提案について、攻撃が見つかった。そして、その次の1ヶ月では9件、そして2018年2月から執筆時点で新たに9件の攻撃が見つかっている。本稿の執筆時点で、13のアルゴリズムが完全に破られており、8のアルゴリズムが部分的に破られている。つまり、すでに69のうち21の提案は破られているのである。
NISTがこのような公募と公開評価プロセスを経て暗号の標準化を行うのは、AES、SHA-3の例がある。ただ、今回の耐量子計算機暗号のケースが以前の2つと異なるのは、AESやSHA-3の時は、どのような基準を満たせば安全な暗号であるか、その要求条件についてのコンセンサスがある程度公募開始時に存在したが、耐量子計算機暗号については、暗号が達成する機能や、何を満たせば安全な耐量子計算機暗号なのかについての知見がないままスタートしている。NISTは、そのような要求条件についても募集をして、並行で検討を進める。つまり、今回のプロジェクトは確固とした耐量子計算機暗号の標準を決める、というより、まずは耐量子計算機暗号に関する知見を、評価プロセスを通じて世界中で共有することに、主眼の半分が置かれていると言ってよい。場合によっては、安全性に対する要求基準の議論が進んだ結果、どの暗号提案も受け入れられない、という可能性すらある。NISTの担当者も、この評価の結果がFIPS（連邦情報処理標準）になるのか、NIST-SP（Special Publication：ガイドライン的文書）になるのかはわからないとしている。上記の位置付け、および RSA 等の成熟したアルゴリズムと比較して解析手法が劇的なスピードで進化している状況を踏まえると、現状欠点が指摘されていないアルゴリズムも安全性が保証された訳ではなく、現状は評価や標準化の初期段階であり、これから様々な評価を経て、その安全性について議論がなされていくことになるだろう。NISTのプロジェクト皮切りに、これから様々な評価を経て、適切な評価基準と技術に向けた活動が進むと考えた方が良いだろう。
まとめ（長期的な方向性）
前述した通り、量子ゲート型の量子計算機が、実際の暗号技術を破るまでには、まだまだ技術的課題があることを考えると、耐量子計算機暗号の安全性の議論には十分な時間があるし、慎重に地に足をつけた議論がなされることが望ましい。現在、理論的に言えることと言えないことを峻別し、冷静な議論がなされるべきである。
もう一点、気にしないといけないのは実用性だ。上記の議論は、主に耐量子計算機暗号の安全性に寄っているが、世の中に銀の弾丸がないように、安全性を高めた暗号技術は、性能を犠牲にするというトレードオフがある。特に多くの耐量子計算機暗号は、データ量が多くなったり、鍵のサイズが大きくなるなど、実用上の欠点も多く持っている。時折、ブロックチェーン技術の長期の安全性のために耐量子計算機暗号を使うという話が出てくるが、必要なデータ量を考えるととてもではないが、ブロックチェーン技術には使えない。このような制約条件についても、今後の研究の中で明確化される必要があるだろう。
関連記事
