量子コンピュータに破れない暗号はつくれるか？　【近刊紹介】縫田光司 著『耐量子計算機暗号』

新刊、『耐量子計算機暗号』（2020年8月上旬発行）の発行に先立ち、著者の縫田光司先生による本書の紹介文と、「まえがき」を公開します。

＊＊＊
『耐量子計算機暗号』の紹介　

記：縫田光司（東京大学准教授）

現代の高度情報化社会を支える基盤であるインターネットなどの情報通信技術を、安全性の面でさらに下支えしている技術の一つが「公開鍵暗号」です。一方で、従来の計算機（コンピュータ）とは異なる物理原理により高速な計算を行う「量子計算機」の研究開発が、近年特に勢いを増しています。両者は一見すると関連が薄そうに思えるかもしれませんが、実は、量子計算機の大規模化によって公開鍵暗号の安全性が脅かされる、という悩ましい関係があります。

より詳しくは、現在の主要な公開鍵暗号（RSA暗号と楕円曲線暗号）の安全性評価の際に「この問題は計算機でも解くのが非常に難しいであろう」と前提としていた問題が、量子計算機にとってはさほど難しくないことが判明しています。このことが明らかとなった1990年代半ば以降、量子計算機でも解読が難しい暗号の実現を目指す「耐量子計算機暗号」が暗号分野の一大研究テーマとなりました。量子計算機の研究開発は今後もさらに進むでしょうから、暗号的な対抗策である耐量子計算機暗号の重要性もさらに高まると考えられます。

その一方で、耐量子計算機暗号について新たに学び始める方向けの、技術的な基本事項を幅広く集めたいわゆる「入門書」は（少なくとも、日本語で読める本は）まだありませんでした。この分野が比較的新しいことも要因の一つですが、別の要因として耐量子計算機暗号の種類の多彩さが挙げられます。従来の公開鍵暗号では、まずはRSA暗号、より高度な題材として楕円曲線暗号、という「王道」が確立しています。それとは対照的に、耐量子計算機暗号は発展途上の分野であり、様々な構成原理に基づく方式たちが次世代の標準技術を目指して鎬を削っている状態です。そうした異なる種類の構成原理やその背後にある数理的手法の説明を盛り込み、「耐量子計算機暗号を技術的に学ぶにはまずはこの一冊」、と思っていただけるよう志して本書を執筆しました。

上述した耐量子計算機暗号の構成原理は、いわゆる理系分野の方には比較的お馴染みであろう行列や多項式を用いる「符号ベース暗号」「多変数多項式暗号」のほか、高次元格子を用いる「格子暗号」、さらには楕円曲線の特殊な変換関数を用いる「同種写像暗号」のようなかなり高度な数学を要するものまで多様です。本書ではそうした高度な題材についても、できるだけ少ない数学的予備知識から出発して、必要な数学的知識を随時補いつつ（どうしても難しい箇所は概略に留めつつ）説明を試みています。また、最初の章は「耐量子計算機」に限らない暗号分野自体への導入的内容であり、暗号分野自体に初めて触れる方にも参考になると期待しています。さらに、最後の章では量子計算のアルゴリズムについても理論の概要を説明しています。より本格的な内容は量子情報理論の専門書に譲りますが、公開鍵暗号（特に、耐量子計算機暗号）の安全性評価と量子アルゴリズムの関係についても書かれている本は珍しいと思います。

なお、上述のように本書は「入門書」としての幅広い記載を心掛けたため、例えば格子暗号など個々の題材について本書に収められなかった事項も多いです。そうした発展的な題材は今後出版されるであろう（と著者は期待します）個別の専門書にお任せすることとして、読者の方々が「次」へ挑まれる際の「踏み台」として本書が役立てるのであれば著者として喜ばしい限りです。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝

『耐量子計算機暗号』まえがき

現代の高度情報化社会の根幹を担う基盤技術の一つが暗号技術である。たとえば、インターネットにおける安全な通信には公開鍵暗号が不可欠である。その要は、仮に公開・送信した情報から秘密の情報を「原理的には」特定しうるとしても、その特定にたとえば数百年もの非現実的な計算量が必要であれば「事実上」安全である、という方法論である。一例として、本書の執筆時点で推奨されているRSA暗号の強度設定では、設計に用いられる整数を素因数分解できれば暗号が解読できるものの、その整数は二進法で2048桁（十進法では600桁強）もの巨大さであり、これは素因数分解の世界記録の桁数（二進法で795桁）*1の倍以上である。こうした暗号の安全性は、今後余程の驚異的な技術革新がない限りは破られないように思える。

*1　2019年12月に樹立された。それ以前の記録は二進法で768桁（2009年12月）であった。

しかし、その「余程の驚異的な技術革新」の可能性を秘めているのが量子計算である。現在の普通の計算機（コンピュータ）では、機器の小型化・高密度化を支える工学的工夫はさておき、計算の原理自体はいわゆる古典物理学の領域にある。そこに古典物理学では実現できない量子物理学的な原理を導入して、現在の計算機よりも「根本的に速い」計算機の実現を目指すのが量子計算の分野である。量子物理学的な現象は繊細かつ安定した制御が困難なことから、量子計算ではこれまでハードウェア的な研究よりもソフトウェア（アルゴリズム）的な研究が先行してきた。その代表例が、ショア（Peter W. Shor）が1994年に発表した、素因数分解を効率的に行う量子計算アルゴリズムである。暗号分野の視点ではこの研究結果は、将来的にショアのアルゴリズムを実装できる大規模な（暗号で用いられる数千ビット規模の数値を扱える）量子計算機が実現すると、前述したRSA暗号をはじめとする素因数分解の計算困難性を前提とした暗号の安全性が失われることを意味する。

そこで、現在主流のRSA暗号などとは異なり、大規模量子計算機の実現後も安全性が損なわれない新しい公開鍵暗号技術の必要性が暗号分野で提唱され、本書の主題でもある「耐量子計算機暗号」（Post-Quantum Cryptography）という研究分野が誕生した*2。耐量子計算機暗号は、それを専門に取り扱う国際会議PQCrypto（International Conference on Post-Quantum Cryptography）が10年以上にわたり定期開催されているなど、すでに暗号分野で主要な研究分野の一つとなった。2016年には米国国立標準技術研究所NISTが耐量子計算機暗号の標準化に向けた公募を行っている。さらに近年は量子計算のハードウェア的な研究が大幅に進展し、2017年には小型ではあるが量子計算機の商用サービスが開始され、また2019年9月には量子計算機の性能が（詳細は割愛するが）「量子超越性」と呼ばれる一つの大きな壁を超えたのではないかとの観測がなされた。こうした量子計算に対する認知度や期待の高まりも相まって、耐量子計算機暗号はこれまで以上に大きく注目されている。

*2　この分野名は、英語ではPost-Quantumの代わりにQuantum-ResistantやQuantum-Safeといった語も用いられ、日本語でも「耐量子暗号」「ポスト量子暗号」など呼称のぶれが大きい。本書では原則として、CRYPTREC（1.5節を参照）が使用している「耐量子計算機暗号」という名称を用いる。

本書はこの耐量子計算機暗号に関する、筆者の調べた限り（包括的かつ技術的内容に重きを置いた）和書として初の専門書である。耐量子計算機暗号の特徴の一つに、その基盤となる知識の多彩さや関連分野の幅広さが挙げられる。暗号分野の知見を要するのに加えて、RSA暗号という公開鍵暗号の「王道」と異なる構成原理*3を探る必要上、投入される数学理論の種類や難度も多様である。さらには「耐量子計算機」暗号であるから、「敵を知る」意味で量子計算の知識も重要となる。逆にいえば、従来の暗号分野に限らず、数学や量子計算の分野の人々が「うちの分野と関係するらしいので」とこの分野を訪れることも考えられる（し、そう筆者は願っている）。そこで本書では、暗号分野や近接分野で比較的共有されているであろう数学知識（いわゆる理系の大学1、2年次程度の解析学や線型代数と、集合・写像・確率など基礎数学的な事項）のみを前提とし、耐量子計算機暗号の設計や安全性評価の具体例の紹介だけでなく、この分野をさらに深く学ぶために必要と筆者が考える数学や暗号技術などの基礎知識の整備をも主眼とした。なお、高度な数学を仮定しないとはいえ、実際には（筆者自身がもともと数学畑の人間ということもあり）証明や式変形など数学一般の営みに親しみがあるほうが本書を読み進めやすい。たとえば卒業研究や大学院進学で暗号分野を研究し始める情報科学分野の学生が研究の土台固めのため最初にじっくり読む本、といった立ち位置を志して本書を執筆した。

*3　暗号分野に馴染みのある読者向けの注釈として、現代の公開鍵暗号にはRSA暗号以外にもいわゆる楕円曲線暗号という別の主流技術も存在するが、それらもショアのアルゴリズムで破られてしまう。

本書の構成
第1章では、暗号分野の歴史や本書で用いる計算量理論の基礎知識、暗号方式の具体例やその理論的・実用的観点からの安全性評価の実例などを概説している。本書は暗号分野以外の読者も想定しているため、この章は「耐量子計算機」に限らず暗号分野一般への導入にも役立つよう志した。また最後の第5章では、量子計算の数学的モデル化に必要な量子情報理論の基礎の解説*4から始めて、前述したショアの量子計算アルゴリズムなど従来型の暗号の安全性と関連する内容を説明し、最後の節では（技術的詳細を述べる余裕はなかったが）耐量子計算機暗号の安全性評価にも関連する比較的新しい量子計算アルゴリズムの概要も述べている。

*4　量子情報理論を真面目に説明するにはどうしても比較的高度な線型代数の理論（（半）正定値線型変換や線型空間のテンソル積など）を要するため、それらの予備知識を付録のA章にまとめている。

本題である耐量子計算機暗号自体を扱った残り三つの章については、何を書いたかよりも「何を書か（け）なかったか」を述べるほうが有益であろう。第2章で耐量子計算機暗号分野を概観した後、現時点での耐量子計算機暗号の主な種類のうち「符号ベース暗号」と「多変数多項式暗号」を紹介し、次に「格子暗号」と「同種写像暗号」をそれぞれ第3章と第4章で紹介しているが、たとえば他の重要な種類である「暗号学的ハッシュ関数」に基づく方式は本書では説明できていない。また、本書で扱っている上記の耐量子計算機暗号の種類についても、（多数存在する方式のなかでごく限られた）いくつかの方式の具体的設計や（一部を除き）その出力の正しさは説明しているものの、その数学的な安全性証明の詳細や、実用上の安全性解析に用いられる各種アルゴリズム（グレブナー基底計算、格子の最短ベクトル計算など）の詳細な計算量評価については説明する紙面の余裕がなかった。実のところ、上で挙げた耐量子計算機暗号の主な種類の各々が、本来はそれ単独で専門書になりうる深みと広がりをもつ題材なのである。こうした本書に欠けている事項については、本書を踏み台として、後で紹介するようなより進んだ書籍や学術論文などを参照してさらに学習や研究を進めていただけると幸いである。

なお、上で「初の専門書」の前に括弧書きで言い訳がされているのは、本書の執筆開始時点では当該分野の専門的な和書が見当たらなかったところ、以下のように執筆開始後の2019年2月以降に関連書籍が相次いで発刊されたことによる。時系列順に、岡本龍明（著）『現代暗号の誕生と発展』（近代科学社）は、全体としては暗号分野全般を概説する一般向け書籍の体裁であるが、そのなかで一つの章を耐量子計算機暗号の紹介に割いている。高木剛（著）『暗号と量子コンピュータ』オーム社）も比較的一般向けの見た目をした概説書であるが、副題に「耐量子計算機暗号入門」とあるように耐量子計算機暗号、とくに本書では記載の乏しい標準化動向など実用寄りの事項の紹介に力を入れている。さらに、青野良範、安田雅哉（著）『格子暗号解読のための数学的基礎』（近代科学社）は、格子暗号の数学的安全性解析手法に特化した和書では異色の専門書であり、当該分野の第一線の研究者である著者らによって、本書の第3章で述べた入門的内容を超えた専門的内容が豊富に解説されている。一方、洋書ではベルンシュタイン（Daniel J. Bernstein）らが編者の”Post-Quantum Cryptography"（Springer社）が代表的であり、2010年出版のため同種写像暗号のような最近の話題は含まないものの専門性の高い内容となっている。本書に欠けている事項についてはこういった関連書籍も参照されたい。

出典：『耐量子計算機暗号』

縫田光司（ぬいだ・こうじ）
東京大学大学院情報理工学研究科 准教授

＊＊＊

『耐量子計算機暗号』

量子計算機（量子コンピュータ）の研究開発が急速に進む昨今、従来の計算機の能力を前提に設計されている「暗号技術」に見直しが求められている。大規模量子計算機の実現後も安全な公開鍵暗号は、どうすればつくれるのか。この課題に挑むべく誕生した「耐量子計算機暗号」（Post-Quantum Cryptography）は、近年成長が著しい一大研究分野となっている。

本書は、耐量子計算機暗号を包括的かつ技術的に解説した、初の専門書である。暗号理論全般および量子計算への入門的解説から紐解き、安全性評価の具体例も紹介しながら、多彩な耐量子計算機暗号の試みを取り上げる。

【目次】
第1章　暗号分野への導入
第2章　耐量子計算機暗号
第3章　格子暗号
第4章　同種写像暗号
第5章　量子計算と暗号の安全性