SQAT^® Security Report 2019年9月号

量子コンピュータの実用化と耐量子暗号の標準化動向
～ 未来は遠く、それでいて近い ～

通信の安全性に特化した技術として普及している暗号化や認証技術。コンピュータの進化によって、そう遠くない未来には現在普及している暗号技術は破られてしまう可能性がある。このシナリオに抗うため、日夜研かれし頭脳を駆使して挑戦を続ける研究者たちがいる。その中のひとりである、東京大学の縫田 光司氏をお招きし、当社セキュリティサービス本部でアナリストを務める芦原聡介とさまざまな角度から暗号技術の可能性を語り合っていただいた。

※インタビュー内容、役職、所属は取材当時のものです。

量子暗号と耐量子暗号の違いについて

芦原：まずは対談の企画段階で、量子コンピュータの実用化の話題が候補に挙がり、そこから派生して米国政府の耐量子暗号の標準化動向などにも触れたい、となったのですが、社内で検討していくうちに「そもそも量子暗号と耐量子暗号を混同している方もいるのでは？」という疑問が生まれました。

縫田：たしかに、混同されることも多いです。単純に字面だけでいうと、日本語には“耐”が付いているだけ、英語でもQuantum cryptographyとPost – Quantum cryptographyでして、「“耐”“Post”が付いているほうが改良版」と捉えてしまう方も結構見受けられます。実際は全くの別物で、量子暗号というと量子コンピュータを使った暗号化技術を指すこともありますが、実際には量子鍵配送、つまり量子力学の原理を利用して暗号化に使用する秘密鍵を安全に相手に送り共有するための技術を指す場合が多いです。

芦原：そうですね。量子鍵配送に関しては、ITU-TでY.3800勧告として承認され、国際標準の骨格に日本の技術が強く反映されていることが先日ニュースになりましたね。それに対して、耐量子暗号のほうは、量子力学の原理が実装された新しい型のコンピュータ、すなわち量子コンピュータに対抗するための技術のことですよね。つまり、暗号を使用する自分は量子コンピュータを使っていなくても、攻撃者のほうは量子コンピュータを使えるという攻撃モデルを想定しています。そんな条件でも、解読することができない暗号技術のことを耐量子暗号といいます。ですので、耐量子暗号は、現在普及しているコンピュータを使って実装するものです。

　

高機能暗号、耐量子高機能暗号について

芦原：次にセキュリティの観点からすると、暗号はあくまでセキュリティを実現するためのひとつの手段であり、コストがかかるものというイメージがあります。こういったネガティブなイメージを払拭できる話をしたくて。そうですね…、まずは高機能暗号について話をしていきたいと思うのですが。

縫田：普通の暗号技術は、暗号化や認証技術など通信の安全性を守るのに特化したものです。高機能暗号と呼ばれる技術は、比較的新しい技術でして、安全性はもちろんあるのですが付加的な機能も充実させようという技術です。高機能暗号の例を挙げますと、準同型暗号（図参照）というものがありまして、暗号文がふたつ与えられた際に平文や秘密鍵なしで計算できる技術です。これは平文が仮に数値だったとすると、暗号化を解いて足して暗号化しなおすのではなく、暗号文のままで中身を加算できます。単なる安全性だけではなく、機能としてもより便利なものになっているということになりますね。これは一例であって、他にも検索可能暗号* 2 データを暗号化したままで検索を可能にする技術のこと、関数型暗号* 2 公開鍵と秘密鍵にパラメータを与え、パラメータの対応関係が成立したときに限り復号できる技術のこと などといった技術もあります。

芦原：高機能暗号を企業で利用するという話ですと、自社でだけ使うようなシステムなら暗号化の必要はないと思いますが、例えばクラウド上のシステムなど、データ処理を外部委託するような環境の場合ですよね。不正だったり、事故だったりがあったとしても、安全性が保たれるようにしたい。暗号化技術はこういった状況で必要になってくる。

縫田：おっしゃるとおりで、クラウドの利用者側としては安全だと思いたいけれども、必ずしも言い切れないと思う人もいる。ですが、暗号化した状態でクラウドにデータを預けておいて、統計的な処理をするとして、暗号化したままで実現できるようになるなら完全には信用できないと思われるクラウド環境だったとしても、見られることはないだろう、と思える。

芦原：もし具体例を挙げるとしたら、どのような高機能暗号の利用の仕方がありますか？法的な理由などで、データ処理を外部委託したくても平文では外に出せない場合も考えられますよね？

縫田：そうですね…。例えばビッグデータ解析をするとき、個人の活動の履歴や、病歴、企業秘密、特許のアイデアなど、あまり外部に見せたくないようなデータを分析します。こういうときに先ほど言ったような準同型暗号を使えば、暗号化したままで分析を行うことができる。情報の利活用とプライバシーを守ることの両立になりますね。

芦原：準同型暗号ですと、既に実装されているものもありましたよね。準同型暗号を使ったソフトウェアが出ていて、使い始めている企業もあったと記憶しています。

縫田：この“高機能暗号”に先ほどまでお話をしていた“耐量子技術”が合わさると、安全性がより強固なものになります。それが“耐量子高機能暗号”というものですね。耐量子暗号と高機能暗号には、数学的な仕組みに共通点が多いという相性の良さもあります。

　

量子コンピュータの起源と研究について

芦原：耐量子暗号は、“量子コンピュータが実装されたときに対抗するための技術”といったことを話しましたが、ともすると量子暗号やこれを搭載した量子コンピュータが悪者であるかのように捉える方もいるかもしれません。そうではなくて、高性能なものを駆使して世の中を便利なものにしたいといった前向きな動機で研究が始まったわけですよね。

縫田：はい。高度な技術は大抵の場合、前向きな構想があって、理論的なところから出発します。量子コンピュータの起源は“量子計算”。1980年代に「例えば普通のコンピュータではなく、量子計算ができるコンピュータがあれば、量子力学的なシミュレーションが上手くできるのではないか」という希望的観測から始まりました。そして現在量子コンピュータをどう実現するのか、という段階ではありますが、いろいろな研究が進められている。

芦原：ただし、ポジティブな側面を机上の空論でふりかざしてばかりではいけない。何かを実現させるためにはリスクも考えなければなりませんよね。新しい技術を研究するうえでは避けられないことです。

縫田：そうですね。暗号の観点でインパクトがあった最初の研究結果は、1994年にPeter W. Shor氏が証明した素因数分解の量子計算アルゴリズムです。現行のコンピュータでの大きな整数の素因数分解には膨大な計算量を要しますが、インターネット等で使われる暗号の安全性は、この計算量の大きさに依存しています。もし量子コンピュータが実現されるとこういった暗号の安全性が崩壊する、としたのがShor氏の論文です。

芦原：現在公開されているRSA暗号や楕円曲線暗号の設計思想が破られてしまうということが明らかになったわけですから、それに対応できる暗号技術の研究を進めなければなりませんよね。

縫田：基本的に公開鍵暗号の安全性は、理論的に証明しきることはできません。よって実験で検証する。実験結果から導き出される予測で安全性が成り立っている、ということです。予測とはあくまで“確からしさ”ですので、明日その“確からしさ”が破られる可能性は否定できるものではありません。この信頼度をいかに高めるかは、暗号分野の課題のひとつです。

芦原：コンテストでその“確からしさ”の信頼性を高めようとする動きがありましたね。RSA Factoring Challenge*3 1991年3月18日にRSA Security社の研究機関であるRSA Laboratoriesが提唱した、計算数論の研究と大きな整数の 因数分解と暗号化に使用されるRSA鍵が破られることの困難性検証を促進するためのプロジェクトなんかもそうでしたよね。

縫田：素因数分解をする対象がレベルごとに用意されていて、世界中の暗号の研究者が問題を解く。たくさんの人が解けない問題を自分が解ければ、優秀さを認められることになりますし、賞金が発生するものもあります。そうすると、漠然と研究をしているよりもモチベーションが上がりますよね。

芦原：そういう世界的に注目されているような場があれば、世界最強の暗号解読者でも解くことができない問題のレベルがわかりますよね。そうなれば、暗号の“確からしさ”をどこまでのレベルに設定しておけば破られないか、という目安がわかるとなるわけですね。

縫田：耐量子暗号でもこういったコンテストを開催しています。これは企業ではなく、大学が主導のコンテストです。大学が主導なのにはいろいろな理由があるとされていますが、耐量子暗号についてはこれから普及していくであろう、という段階だからというのがひとつ挙げられると思います。

　

米国における耐量子暗号の標準化動向について

芦原：今、まさに標準化が行われているのは公開鍵暗号ですよね。暗号化、鍵交換、デジタル署名といった公開鍵暗号の方式の選定が進行していて、第1回の安全性・効率性の評価が終わって、第2回の評価に進む方式の仕様や実装結果の更新版も出揃った状況ですね。

縫田：アメリカ国立標準技術研究所［以降NISTとする］ * 4 科学技術分野における計測と標準に関する研究を行う米国商務省に属する政府機関 が標準化に向けた公募、という位置付けで2017年11月まで技術提案を募集していました。芦原さんがおっしゃったように、今は公開鍵暗号方式の選定時期ですね。理論的なことだけではなく実装も含めたものでして、仕組みがわかりやすい実装と、速度的な最適化も施した本格的な実装との2種類を提供すること、という募集のもと選定されています。

芦原：選定の仕方は、例えば、RSA Factoring Challengeのような？

縫田：NISTのWebサイトで公開する暗号方式に対して、世界中の耐量子暗号の研究者たちが安全性のチェックをしていく、というものです。早いものでは提案して数日で破られてしまうものもありますよ。

芦原：もちろん提案する側が簡単なものを提案しているのではありませんよね？

縫田：はい。私自身も携わったことがあるのですが、理論も実装もしっかりしていなければいけませんし、ドキュメントの整備もされていなければなりません。かなりの労力をかけて提案をするのですが、それでも1週間も経たずに破られてしまうということもある、ということです。

芦原： ナップザック暗号*5 1978年にラルフ・マークルとマーティン・ヘルマンが発表した部分和問題を利用した公開鍵暗号のひとつ みたいに、新しい方式が提案されてはすぐに破られて、というのを何度も繰り返している方式もありますし、なかなか上手くいかないものですね。

縫田：量子コンピュータは将来的に実現するかどうかもわからない技術です。それに対して今、暗号方式の標準化をしているというのは、つまり安全性評価を事前にしておかないと間に合わない、ということです。

芦原：例えばあと2～3年で量子コンピュータができそうですよ、というときに対応した暗号を用意する、となると、まだ安全が保障されていないものを実装せざるを得なくなる危険性がありますしね。

縫田：それから、暗号技術を移行する期間も考えるとかなり余裕を持って標準化を進めておかなければならないということもあります。素因数分解の問題は紀元前から研究されているとされていますが、RSA暗号はその素因数分解の難しさが基本です。研究にかけられた時間の長さが、安全性の確からしさの証左のひとつということですね。

芦原：そうですよね。そうなると、耐量子暗号の研究もかなり長い時間をかけないといけない。耐量子暗号の有力候補の中で比較的新しい格子暗号*6 秘密鍵から公開鍵を計算する際、誤差項を混入させることで秘密鍵を割り出す計算を困難にさせる技術のこと 8の問題についても、既に20年以上も研究され続けていますし、NISTの標準化計画が、年単位の時間をかけたものであることは必然といえそうですね。

縫田：2016年2月に福岡で開催されたPQCrypto（Post-Quantum Cryptography）*7 2006年からスタートした、耐量子暗号を専門とする国際会議のこと に私も参加したのですが、そこでNISTから耐量子暗号の標準化の具体的な計画が示されました。標準化の方針について、採用する技術をひとつに絞るのではなく、信頼できる技術の選択肢を利用者に提供できるようにすることが目的であると言っていました。

芦原：技術をひとつに絞ってしまうと、様々な状況に対応することが難しくなりそうですものね。つまり、利用する用途によってふさわしいものを選べるようにする、と。

縫田：はい。そうですね。ある種類の耐量子暗号は安全性が高いとされる一方で、公開しておく情報として、たくさんの数値をためておかないといけないので、例えば軽量デバイスみたいなところに組み込む場合などは、必ずしも適切とはいえないかもしれませんね。そういう場合には、小さな鍵で使える別種の耐量子暗号の需要も出てきます。ですので、メリットとデメリットを検討しつつ、用途によってどの性能を重視するのかを見極めることが重要になってくると思います。

　

セキュリティの観点からの準備について

芦原：弊社では脆弱性診断サービスを提供していまして、いまだに古い暗号の実装を検出することもあります（28ページ参照）。実際標準化を進めて移行できるまでに、どのくらいかかるものなのかな、という疑問があります。耐量子暗号でなくても通信できる期間があって最終的には完全移行がなされるまで、しばらくは移行期間が設けられると思いますが…。

縫田：そうですね。NISTの標準化の観点ですと多少意見はわかれますが、2030年ごろにはRSA暗号を破ることができる量子コンピュータが現れるだろうとされています。

芦原：耐量子暗号による通信でないといけないのは2030年辺りだろう、ということですね。

縫田：移行期間を予測するひとつの目安としては、現在RSA暗号に使われている鍵の大きさの今の標準、2048ビットへの移行に要した期間でしょうか。少し前までは1024ビットでしたね。コンピュータの性能の進化などによって1024ビットでは足りないとなったのが、2010年ごろでした。実際に世の中のほとんどのシステムが2048ビットに移行できたのにはおよそ5、6年かかったというデータがあります。今回はもともとのシステム自体を入れ替えるという作業になりますので、もっと時間がかかってもおかしくない。

芦原：計画では標準化ドラフト発行が2024年ごろ、そこから耐量子暗号への移行完了が2030年ごろの予定ですから、結構ぎりぎりのスケジュールですね。移行する方法、例えば、現状は既存のネットワーク上で TLSを使って暗号化通信をする場合は、公開鍵暗号で鍵交換や認証をしているわけですけれども、それの公開鍵暗号の部分を単純に耐量子暗号に置き換えるだけで機能するものなのでしょうか。

縫田：プロトコル全体の安全性をしっかりと調べるというのは難しいかもしれませんが、基本的には鍵の共有が終わった後の部分というのは、公開鍵型ではなく共通鍵型になりますので、そこまで大きな問題はないかなと思います。

芦原：共通鍵暗号の場合は、量子コンピュータを使うことによって、暗号の強度が鍵長の半分のものと同程度にまで落ちるため、ひとまず共通鍵の鍵長を2倍にすれば、それまでと同等の安全性を確保できると考えられていますよね？

縫田：実は少し問題がありまして、2010年に共通鍵も安全ではないという説が出まして、本格的に研究が始まりました。最初は割と限られた種類の方式だけに影響すると考えられていたのですが、もっと新しい研究だと、もう少し広い範囲の共通鍵暗号方式について量子コンピュータの影響がある、となりました。単純に鍵を長くすればよいというわけではないということが明らかになってきているので、耐量子といったときには共通鍵のほうも本当は注目しなければならない要素です。ただ2010年に研究が始まったばかりですので、まだ研究途上ではありますが。

芦原： 標準化が進められている公開鍵型の耐量子暗号だけでなく、共通鍵暗号についても、将来使い続けられるものであるかどうかを考えて利用しないといけないという問題がありそうですね。

縫田：もしかすると、2030年に間に合わせようとするなら準備を急がねばならない段階かもしれません。ただ、今は標準化の準備段階ですので、既存のシステムの中で使われている暗号を新しく置き換えるのは大変でしょうね。ですが、新しいシステムの導入からなら置き換えではないので、想定して作っておくことはできるのではないでしょうか。

芦原：そうなると、2030年以降も稼動させる予定のシステムについては、今の段階で新しい暗号方式に対応できるように設計するのがよさそうですね。

縫田：信頼できる選択肢をどれだけ提供できるかが研究者の使命であると考えています。

---

縫田 光司 氏（右）
東京大学 大学院情報理工学系研究科
数理情報学専攻　准教授
東京大学 理学部 数学科を卒業後、東京大学 大学院数理科学研究科 数理科学専攻 修士課程と博士課程修了。
情報通信や情報利活用の安全性を支える暗号・情報セキュリティ技術の研究を行っている。
論文・著書：Koji Nuida, Goichiro Hanaoka, “On the security of pseudorandomized information-theoretically secure schemes”, IEEE Transactions on Information Theory, vol.59, no.1, pp.635-652, 2013.ほか

芦原 聡介（左）
株式会社ブロードバンドセキュリティ（BBSec）
セキュリティサービス本部 セキュリティ情報サービス部
広島大学大学院理学研究科数学専攻修了　博士（理学）取得。その後、暗号技術の研究に従事し、 共通鍵暗号型検索可能暗号の動向についての論文を執筆。
産業技術総合研究所、日本銀行金融研究所を経て、株式会社ブロードバンドセキュリティ入社。
現在はセキュリティ情報のリサーチ・分析・配信などを行うアナリストを務めるほか、 ITセキュリティセミナーの講師としても活躍している。

---

---