暗号技術の現在 -- ポスト量子暗号への移行と量子暗号
MaruyamaFujio
目次
2019/06/03 暗号技術の現在 -- ポスト量子暗号への移行と量子暗号 概要
現在では、企業の秘密情報も個人のプライベートな情報も、ネットワークをまたいで共有されることが普通に行われています。そうした情報が、無関係の（ある場合には悪意のある）第三者に漏れないように、暗号化技術が利用されています。現代のネットワーク社会の安全性を支える基本技術の一つが、暗号化技術です。
今回のセミナーでは、最近関心が高まりつつある量子情報技術と暗号化技術の関係にフオーカスしたいと思います。セキュリティ技術やブロックチェイン技術に関心のある方の参加を歓迎します。
量子情報技術と暗号化技術の関係は、二つの面から考えることができます。一つは、従来の暗号化技術を「破る」技術としての量子情報技術です。もう一つは、従来の技術（量子コンピュータを含めて）では達成できない「破られない」暗号化技術への量子情報理論の利用です。
前者については、量子コンピュータを使って素因数分解を高速に行うショアのアルゴリズムが有名です。ただ、1994年のショアの発見から25年たった現在も、現在利用されている暗号を破るような量子コンピュータは作られていません。それにもかかわらず、暗号化技術の最前線では、NISTもNSAも「量子耐性」を持つ暗号化技術の開発に余念がないように見えます。
- NIST "Post-Quantum Cryptography" https://csrc.nist.gov/projects/post-quantum-cryptography
- NSA "Commercial National Security Algorithm Suite" https://apps.nsa.gov/iaarchive/programs/iad-initiatives/cnsa-suite.cfm
セミナーでは、アメリカのNIST, NSAの動きを中心に、暗号技術の現在を「量子耐性暗号への移行」としてまとめてみようと思います。
後者の「量子暗号」については、BB84と呼ばれる、秘密キーの共有プロトコルを紹介しようと思います。意外なことに、この量子暗号の原理は、いたってシンプルなものです。量子コンピュータのことを知らなくても、理解できると思っています。もちろん、先のマルレクでも取り上げた「量子テレポーテーション」等の量子通信技術がベースになるのですが、RSA暗号を解く量子コンピュータより一足先に実用化されるのではと、僕は思っています。
はじめに
暗号には「秘密」がつきものであった。1955年、数学者のJohn Nashは、 NSAに対して「鍵の計算に指数関数的時間のかかる」方法を使えば、「誰にも破れない暗号を簡単に作れるようになる」という手紙を送っている。1970年代の初めには、イギリスの情報機関GCHQの科学者たちが、今日の公開キー暗号と同じものを作り上げていた。それはNSAも知っていた。ただ、それらは全て「機密」とされ、世に知られることはなかった。
なぜ、「機密」にされたかといえば、securityの問題は、第一義的に”National Security”の問題だからということなのだが、なぜそうした技術が、広く実用化されなかったという点に関して言えば、別の問題があったことに気づく。それは、当時のコンピュータには、少なくとも経済的には、こうした複雑な計算を実行する計算能力が十分ではなかったのである。
暗号の歴史
Shorのアルゴリズムの発見
1994年、Peter Shorは、量子コンピュータを利用すれば、RSA暗号の基礎である素因数分解が、多項式時間で実行できることを、理論的に証明した。
このアルゴリズムを用いれば、RSAでの素因数分解問題だけでなく、楕円曲線暗号の基礎である離散対数問題も多項式時間で解くことが示され、暗号技術の世界に大きな衝撃を与えた。
ただ、Shorのアルゴリズムを実行する量子コンピュータの実現が、極めて困難であることがわかり、それが現在の暗号技術への「当面の脅威」ではないことが、むしろ広く認識として共有された。
確かに、現在に至るも、Shorのアルゴリズムを用いて、現在利用されている暗号化を破るような量子コンピュータは、いまだ存在しない。
ただ、こうした認識に大きな変化が現れるのは、2015年になってからのことである。
「ポスト量子暗号」 標準化の動向
2015年、NSAは次のような重要な決定を公表した。 Shorの発見から、約20年後のことであった。「我々は、来るべき量子耐性アルゴリズムへの移行について、早いうちから計画づくりとコミュニケーションを開始することを決定した。我々の最終的な目標は、量子コンピュータの潜在的な能力に対して、コスト効率の良いセキュリティを提供することである。」
NSAの決定を受けて、NISTは2016年から “Post-Quantum Cryptography”の標準化の策定の作業を開始した。その計画によれば、早ければ2022年、遅くとも2024年までには、新しい「ポスト量子暗号技術」の標準を決定するという。
量子耐性アルゴリズムへの移行を
現在のグローバルな環境では、我々の国家とその市民とその利益を守る上で、高速で安全な情報の共有が重要である。強力な暗号化アルゴリズムと安全な標準プロトコルは、我々の国家の安全に貢献し、安全への普遍的な要請と相互運用可能なコミュニケーションに向けた取り組みを助ける死活的に重要なツールである。 ......
我々の最終的な目標は、量子コンピュータの潜在的な能力に対して、コスト効率の良いセキュリティを提供することである。我々は、合衆国政府、ベンダー、標準化団体をまたいだパートナーと共に、アルゴリズムの新しいSuitを獲得する明確な計画が存在することを保証するための作業を行なっている。そのアルゴリズムは、オープンで透明性をもって開発され、我々の次の暗号化アルゴリズムSuitの基礎を形作るであろう。 ......
Suit Bの楕円曲線アルゴリズムへの移行を、まだ行なっていないパートナーならびにベンダーは、現時点で、そのための大きな支出せずに、その代わりに、来るべき量子耐性アルゴリズムへの移行を準備することを、我々は勧めてきた。 .....
不幸なことに、楕円曲線の利用の拡大は、量子コンピューティング研究の絶え間ない進歩の事実と衝突するものである。すなわち、量子コンピューティングの研究は、楕円曲線暗号化は、多くの人がかってそうなるだろうと期待したような長期間にわたって有効なソリューションではないことを明らかにした。こうして、我々は、戦略の見直しを余儀なくされてきた。
