過去・現在・未来

【 お盆休みにどうぞ 】 最近、「いちばんやさしい〇〇」というタイトルを持つ本が炎上したのですが、その理由は「いちばんやさしい」からではなく、内容がひどかったからだと思います。 「いちばんやさしい」というタイトルが人の眼をひくのでしょうね。ただ、僕は、そこが少し気になっています。 「やさしい」ことは、いいことなのでしょうか？ だって、世の中には難しい問題が沢山あります。なんでも、やさしく理解できるとは限りません。 「Shorのアルゴリズム」も、そうした理解が難しいものの一つだと思います。 意外に思われる人もいると思いますが、数学や科学の世界の「複雑で難しい概念」は、必ず、「単純でやさしい概念」に分解されるものです。ただ、単純なものから複雑なものを、やさしいものから難しいものを構成してゆくステップは、きちんと順序だって組織されています。 その推論の連鎖は、長く長く伸びることがあるのですが、一歩一歩のステップは、本当は「やさしい」ものです。 ですので、難しいものを理解するには時間がかかるのです。わからなくなったら、そこで立ち止まって、また考えればいいのです。ここでも、時間が必要です。理解のスピードに個人差はあっても、理解に必要なステップの数は、皆、同じです。必要なステップを省略して飛び越えることは、誰にもできないのです。 ですから、教育者が、ある数学的概念をその概念を学ぼうとする初学者に説明しようとするとき、大事なことは、理解に必要なステップを「ていねいに」説明することです。 今回のセッションでは、 「Shorのアルゴリズム」を実現するのに必要な量子回路の話をしています。 量子コンピューターの世界では、「アルゴリズム」は「量子回路」によって表現されます。もっと強く言えば、「量子アルゴリズム」は「量子回路」を構成して見せることによってしか表現されません。 これは、私たちが普通に見るコンピュータでの「アルゴリズム」とハードウェア「回路」の関係とは大きく異なるものです。以前のセミナーで、僕は、「アルゴリズムとプログラムは違う」という話をしました。普通のコンピューターの世界でのことですが。 このことは、量子コンピューターが、システムとしては、まだまだプリミティブな段階にあることを意味しています。 Shorのアルゴリズムは、概念的には、次のような量子回路から段階的に構成されていま

【 8月27日 マルレク「ポスト量子暗号技術の現在」を開催します 】 セミナーの告知、遅くなりました。 8月27日、オンラインでマルレク「ポスト量子暗号技術の現在」を開催します。 少し構成が変わっています。NISTのレポートの詳細な報告は、大幅にカットしました。 「今回のセミナーでは、暗号技術にまつわるエピソードの紹介を交えながら、「ポスト量子暗号」と呼ばれる現代の暗号技術のオーバービューを、分かりやすくを提供したいと思います。」 セミナーのお申し込みは、次のページからお願いします。 皆さんの参加をお待ちしています。 https://cipher2.peatix.com/view −−−−−−−−−-------−−−−−−-----−−− 今回のセミナーのテーマは「暗号」です。 暗号技術は、今、「ポスト量子暗号」への移行という大きな転換点を迎えようとしています。 今回のセミナーでは、暗号技術にまつわるエピソードの紹介を交えながら、「ポスト量子暗号」と呼ばれる現代の暗号技術のオーバービューを、分かりやすくを提供したいと思います。 主要に三つのトピックスを取り上げます。 第一に、20世紀に成立した現代の暗号の歴史を振り返ります。 現代の暗号技術の第一世代は、コンピュータの能力向上とネットワーク技術の発展の両者が交差するところで、1970年代に成立します。「公開暗号キー」と「RSA暗号」を中心とする、その技術は、その後に続くグローバルなインターネットを準備し、その拡大を支えるものでした。 第二に、今日に至るも、陰に陽に、現代の暗号技術に、強い影響を与え続けている「Shorのアルゴリズム」とは何かを紹介しようと思います。 筆者は、Shorのアルゴリズムの発見は、暗号技術の一つのステップとしてだけでなく、21世紀が、量子コンピューターや量子通信技術が花開く「量子の世紀」になることの、歴史的に重要な「先駆け」だったと考えています。 第三に、Shorのアルゴリズムに強烈な刺激を受けて、暗号の世界は、量子コンピューターによっても破られない（これを「量子耐性をもつ」ということがあります）、「ポスト量子暗号」への移行を、時間をかけて準備して進めています。現代の暗号技術の第二世代が、始まろうとしています。 セミナーでは、NISTの勧告をベースに、こうした動向を紹介します。また、「ポスト

【 量子コンピューターが、直接、素因数分解をするわけではないこと 】　 量子コンピューターの入力に巨大な数を放り込むと、Shorのアルゴリズムで、素因数分解された数字が量子コンピューターの出力に返ってくるというイメージありませんか？ ただ、実際は、少し違います。 Shorの素因数分解アルゴリズムを実行するためには、量子コンピューターの他に、風通のコンピューターが必要なのです。 今回は、Shorのアルゴリズムの元となった「確率的素数判定」というアルゴリズムを紹介しようと思います。これは、量子コンピューターで実行されるアルゴリズムではなく、普通のコンピューターで普通に実行されるアルゴリズムです。 ただし、ランダムに試行して正しい答えを見つけようとする点で、普通の計算アルゴリズムとは異なっているのですが。 一番単純には、a < N なる a をランダムに生成して、aとNが互いに素であるかをチェックします。aとNの最大公約数が1以外の値を持てば、Nは gcd(a, N)という約数を持ち、素数でないことが分かります。 まあ、これだけだと、あまりに行き当たりばったりですね。 確率的素数判定法では、先の「aとNが互いに素でないなら、Nは素数でない」というチェックに加えて、もう一つ、「 a^(N−1) が 1でないなら (mod Nで)、 Nは素数でない」というチェックを付け加えます。この二つ目のチェック項目は、「フェルマー・テスト」と呼ばれています。 これだけです。 あとは、沢山の a < N について、二つのチェックを行います。このチェックを通り抜けたNは、素数である可能性があります。aの数が増えるにつれて、Nは素数である確率は高まります。単に、約数aのチェックを忘れただけかもしれないのですが。 原理的には、チェックすべきaの数には、上限があります。a < Nである aを全てチェックすれば、このアルゴリズムでNが素数かの判定が可能なのは明らかです。 ただ、そこまでやらなくても、確率的には必要な情報を得ることが出来ます。こうしたアルゴリズムを、「確率的アルゴリズム」と言います。それは、行き当たりばったりなように見えますが、そうした見かけ以上に強力なアルゴリズムです。 以前に、現代の暗号の技術は、それがどのような「一方向関数」を選択したかで特徴付けられるという話を

【 Shorのアルゴリズムのインパクト 】 1994年、Peter Shorは、量子コンピュータを利用すれば、RSA暗号の基礎である素因数分解が、多項式時間で実行できることを、理論的に証明しました。 このアルゴリズムを用いれば、RSAでの素因数分解問題だけでなく、楕円曲線暗号の基礎である離散対数問題も多項式時間で解くことが示され、暗号技術の世界に大きな衝撃を与えました。 ただ、Shorのアルゴリズムを実行する量子コンピュータの実現は、当時の技術では、極めて困難でした。 こうして、時間と共に、Shorのアルゴリズムが現在の暗号技術への「当面の脅威」ではないという楽観論が、むしろ広く共有されることになります。 確かに、現在に至るも、Shorのアルゴリズムを用いて、現在利用されている暗号化を破るような量子コンピュータは、いまだ存在しません。 こうした認識に大きな変化が現れるのは、 Shorの発見から、約20年後の2015年になってからのことです。 2015年、NSAは次のような重要な決定を公表しました。  「我々は、来るべき量子耐性アルゴリズムへの移行について、早いうちから計画づくりとコミュニケーションを開始することを決定した。我々の最終的な目標は、量子コンピュータの潜在的な能力に対して、コスト効率の良いセキュリティを提供することである。」 NSAの決定を受けて、NISTは2016年から “Post-Quantum Cryptography”の標準化の策定の作業を開始します。その計画によれば、早ければ2022年、遅くとも2024年までには、新しい「ポスト量子暗号技術」の標準を決定するというものです。 NSAの危機感は極めて大きいものでした。Michele Mosca は次のように語ります。 「2026年までに、RSA−2048 が破られる確率は 1/7 , 2031年までに破られる確率は 1/2 になると私は評価している、」 彼らの危機感の背景には、暗号通貨やブロック・チェイン技術の中で、楕円曲線暗号の利用が急速に拡大していることがありました。 次のNSAの 2015年の警告は、そのことを強く意識したものでした。 「 不幸なことに、楕円曲線の利用の拡大は、量子コンピューティング研究の絶え間ない進歩の事実と衝突するものである。すなわち、量子コンピューティングの研

【 オリビア 】 qubit が、Q = a|0> + b|1> の形で表されるとする。ただし、a, b は、|a|^2 + |b|^2 = 1を満たす複素数で「確率振幅」と呼ばれる。何故、|0>, |1> の係数に「確率」の名前がついているのか？ それは、このQを観測した時、 ビット 0 あるいは ビット 1 を得る「確率」が、それぞれ、|a|^2  あるいは  |b|^2 で与えられるからである。 量子論を学ぶときに、誰もが最初に受ける洗礼が、この量子の観測の確率ルールである。この規則を「Born のルール」と呼ぶ。 亡くなった オリビア・ニュートン＝ジョンは、この Born の孫娘である。 −−−−−−−----- 僕は、いつも同じような格好をしているのですが、僕の服のデザイナーも亡くなりました。 −−−−−−−−----- 夜中に連続して二度揺れて、びっくりしました。これまで、あまり地震のないところだったので。僕のところは、大丈夫です。

【 P問題とNP問題 】 ゲーデル、チューリングらが明らかにしたように、「証明可能＝計算可能」なものには原理的限界があることは、1950年代には、 一般に認められるようになっていました。 現代の暗号技術の大きな特徴は、その基礎を、コンピュータはある種の数学的問題を、「効率的」には解くことができないという事実においていることです。 ここで注目してほしいのは、「効率的には解けない問題がある」という考え方です。それは、ゲーデルの不完全性定理が示したような、「原理的に解けない問題がある」とは違った考え方です。それは、実際の計算がコンピューターを使っても、時間がかかり過ぎて手に負えなくなる問題があるという事です。 70年代に入ると、「計算の難しさ」に対する新しいアプローチが活発になります。それは、「計算の難しさ」を、計算に必要な「時間」と「メモリー」で評価しようというものです。それを「計算複雑性理論」といいます。 ここでは、計算に要する時間だけを考えましょう。既に Nashが気づいていたように、計算に「指数関数的時間」を要する問題は、効率的には解けない、難しい問題です。 逆に、入力の文字列の長さをnとするある問題が、nの「多項式時間」で解ける時、この問題を「P問題」といいます。「P問題」は、易しい問題と考えることが出来ます。 計算複雑性の理論で、「P問題」と並んで重要なクラスに「NP問題」があります。「NP問題」は、解くのに「指数関数的時間」がかかる「Not-P問題」ではないのです。 その問題を解くのが「多項式時間」で終わるかどうかはわからなくても、具体的な値で与えられたその問題の「答え」と言われるものが、本当に「正しい答え」であるかどうかを「多項式時間」でチェックできる問題のクラスを、NPといいます。 素因数分解問題は、Nの素因数だという p, q が与えられれば、N = pq かどうかを簡単に、多項式時間でチェックすることが出来ますので NP問題です。　 y = f(x) という関数があって、xが与えられた時 y = f(x)を求めることは簡単に出来ても、yが与えられた時 y = f(x) を満たすxを求めることが難しいとき、関数 f を「一方向関数」と言います。xからyをもとめるのが多項式時間で可能だとすれば、yからxを求めるのは NP問題です。 現代の暗号技術では、ど

 【 NashからNSAへの手紙 】　 1950年代に入ると、時代の先鋭な知性たちは、今日の暗号理論/複雑性理論の原型とも言える認識に到達し始めます。 1955年、NashはNSAに次のような手紙を送ります。  「ほとんどすべての十分に複雑なタイプの暗号化にとって、特に、鍵の異なる部分によって与えられた命令が、相互に複雑に相互作用して、それが暗号化の最終的な決定において影響を与えている場合、鍵の計算の平均的な長さは、鍵の長さ、すなわち、鍵の持つ情報の内容に関して、指数関数的に増加します。」 「それは、実際的には誰も破れない暗号を設計することを、極めて簡単に実行できることを意味します。暗号が洗練されたものになるにつれて、熟練したチームなどによる暗号破りのゲームは、「過去」のものになっていくはずです。」 鍵を破るのに、「指数関数的」時間がかかる暗号は、事実上、誰にも破れないとというのは、現代の暗号技術の基本的な立脚点です。このことに、50年代にNashは気づいていたのです。しかしこの重要な指摘は「秘密」にされました。 現代の暗号技術が立ち上がるのは、それから20年近くたった、1970年代です、 Whitfield Diffie,  Martin Hellman による、「公開キー暗号」が公開されたのは1976年で、Ron Rivest, Adi Shamir, Leonard Adlemanによる、「RSA暗号」が公開されたのは、1977年 です。この 1976−1977年に、現代の暗号技術が確立したと考えていいと思います。 ただ、それは表向きの公式の「暗号史」では、そうなっているということです。 イギリスのNSAにあたるGCHQの情報開示で、1970年から1974年にかけて、GCHQの三人の研究者、James Ellis, Clifford Cocks,  Malcolm J. Williamson が「公開キー暗号」「RSA暗号」とほとんど同じものを開発していたことが明らかになります。それはNSAも知っていました。ただ、そのことは「秘密」にされました。 この情報開示が行われたのは、1997年になってからのことです。三人の研究者は、さぞ無念だったと思います。 動画 「暗号の歴史 -- 現代暗号技術の成立」を公開しました。 https://youtu.be/QDSBa