過去・現在・未来

【  5月に開催した「エントロピー論の現在」全講演ビデオ 公開しました  】  MaruLaboでは、以前に行ったセミナーの収録ビデオを公開しています。 今回は、5月27日に開催した マルゼミ「エントロピー論の現在」の講演ビデオの公開です。 以下が、マルゼミ「エントロピー論の現在」の 講演資料と講演ビデオの再生リストです。ご利用ください。 講演資料： https://drive.google.com/file/d/1XnJY74PfN0wy92pzB89fL4kNnvbkSwdJ/view?usp=sharing 再生リスト： https://www.youtube.com/playlist?list=PLQIrJ0f9gMcMUBleCTf9mTcrcpnMU-HgG この「エントロピー論の現在」の再生リストは、次の四つのビデオから構成されています。 ●  第1部 シャノン・エントロピーの基本的な性質について https://youtu.be/IVsfeTSHfX8?list=PLQIrJ0f9gMcMUBleCTf9mTcrcpnMU-HgG ●  第2部 シャノンが考えたことを振り返る https://youtu.be/WGZ8TYuQlAo?list=PLQIrJ0f9gMcMUBleCTf9mTcrcpnMU-HgG ●  第3部 Faddeev-LeinsterのChainルール https://youtu.be/bjjD3_ENkUQ?list=PLQIrJ0f9gMcMUBleCTf9mTcrcpnMU-HgG 1 ●  第4部 Baez: 新しいエントロピー論の登場 https://youtu.be/FHFfiEwRIMA?list=PLQIrJ0f9gMcMUBleCTf9mTcrcpnMU-HgG このセミナーの参考資料・ショートムービーは、MaruLaboのサイト  https://www.marulabo.net/docs/info-entropy5/  からアクセスできます。

【 縦か横か？ 】 基底 b1, b2, ... , bn から作られるラティスを、次のように表します。 　　L = L(b1, b2, ... , bn) ラティス𝐿は、複数の基底を持ちます。もう一つの基底を b1', b2', ... , bn' とすれば、 　　L = L(b1, b2, ... , bn) = L(b1', b2', ... , bn') この時、基底 (b1, b2, ... , bn )と基底 (b1', b2', ... , bn')は、𝐿について「等価」であると呼んで、次のように表しましょう。 　　(b1, b2, ... , bn ) ⇔ (b1', b2', ... , bn') ラティスの基底が等価であることを、行列を使って表現することもできます。 基底を構成するそれぞれのベクトル b1, b2, ... , bnを列ベクトルで表し、それを並べて行列を作ります。ラティスの基底は、𝑛×𝑛の行列Bで表現されます。 　　L = L(B) この時、行列Bに次のような操作を加えて新しい行列を作ります。 1. 元の行列Bの列v_iをv_jと交換したものをB1とします。 2, 元の行列Bの一列v_iに−1に掛けたものをB2 とします。 3. 元の行列Bの一列v_iをv_i + k・v_jにかえたものをB3とします。 この時、 　　L(B) = L(B1) = L(B2) = L(B3) であることがわかります。 要するに、B1もB2もB3もラティスLの基底になっています。先の行列への操作によって、ラティスの基底としての等価性は保たれています。 この操作、見たことありませんか？ 「掃き出し法」とか「ガウスの消去法」というのと、基本的に同じものです。 僕が気になったのは、別のことです。 前に、「Babaiのアルゴリズム」を紹介した時、ラティスの基底を「行ベクトル」の集まりとして扱ってきました、ただ、今回は、ラティスの基底を「列ベクトル」の集まりとして扱っています。 　 縦と横、ベクトルの向き、どっちがいいんでしょう？ どっちでもいいんです。 −−−−−−−−----- 動画 「同じラティスを生成する複数の基底」を公開しました。 https:...

【 Babaiのアルゴリズムは失敗することがある 】 ラティスには、「ラティス問題」と言われるものがあります。 このセッションでは、Shortest vector problem (SVP)とClosest vector problem (CVP)と呼ばれる、二つの「ラティス問題」を紹介します。 Shortest vector problem (SVP)は、ラティスの基底が与えられた時、その基底で張られるラティスで、最も距離が近い格子点を求めよという問題です。 Closest vector problem (CVP)は、ラティスの張る平面上に、ある点を放り込んだ時、その点に一番近い格子点を求めよという問題です。 正規直交基底のように、格子点が縦横に一コマずつ動いてラティスを作るのなら、この問題を解くのは、直観的には簡単です。ただ、基底ベクトルの整数倍の和がジグザグに動いて、ラティスが作られるのなら、見通しは悪くなります。その上、ラティスの次元n が大きなものになると、この問題を解くのは、急に難しくなります。 ここでは、二次元のラティスで、Closest vector problem (CVP)を考えてみましょう。 ラティスの基底を a, b 、格子点に近い点をx とし、それぞれの成分を(a1,a2),  (b1,b2), (x1,x2)としましょう。 ここで、 　　m(a1, a2) + n(b1, b2) = (x1, x2) という関係が成り立っているとします。 　　m・a1 + n・b1 = x1 　　m・a2 + n・b2 = x2 ですので、これを m, n について解くことができます。 ただ、これを解いても、m, n が整数になる保証はありません。そこで、この解 m, n に一番近い整数を M, N とします。 この時、M, N は整数で、a, b は基底ですので、 　　M(a1, a2) + N(b1, b2)  は格子点になります。これが点(x1, x2)に一番近い格子点です。 こうしたアプローチを「Babaiのアルゴリズム」と言います。 残念ながら、このアルゴリズム、失敗するんです。うまくいくときもあるんですが。 整数とは限らない m, n から、整数 M, N を作ったあたりが、怪しいですね。 −−−−−−−−----- 動画 ...

 【 8/27 マルレクのタイトルを「暗号技術の現在」に変えました 】　 開催まで一週間を切っているのですが、8/27 マルレクのタイトルを「ポスト量子暗号技術の現在」から「暗号技術の現在」に変更しました。急な変更申し訳ありません。 構成は次のようになります。 　● 第一部「現代暗号技術の成立」 　● 第二部「ショアのアルゴリズムの発見」 　● 第三部「ラティス暗号の時代の始まり」 「ポスト量子暗号技術」にフォーカスするのではなく、できるだけ多くの人に、現代の暗号技術の大きな流れを捉えてもらうことをセミナーの目標にしたいと思っています。 セミナーでは、ざっくりとした話をわかりやすくできればと思っています。 細かな議論や論点は、ぜひ、セミナーのまとめページ  https://www.marulabo.net/docs/cipher2/ をご覧ください。 まだ、告知ページ等の修正ができていません。これからぼちぼち進めます。 今日はタイトルページの写真を修正しました。Nashの写真とNSA/NISTのロゴを削除しました。代わりに、僕の好みで、Regev の写真を追加しました。Regevは、暗号の世界以外ではあまり知られていないかもしれませんが、いつかNashのように有名になると、僕は思っています。 セミナーへのお申し込みは、https://cipher2.peatix.com/view からお願いします。皆様のお申し込みをお待ちしています。

 【 良い基底と悪い基底 】 前回、サンプルにしたのは、とてもシンプルなラティスでした。このラティスのシンプルさは、主要に、その基底が直交する単位ベクトルであることに起因しています。 ただ、ラティスの基底は、正規直交基底には限りません。二次元のラティスなら、任意の独立した二つのベクトルは、ラティスの基底になることができます。n次元のラティスなら、任意の独立なn個のベクトルは、ラティスの基底になることができます。 この時、n次元のラティスを構成する格子点は、それぞれn個ある基底の製数倍の和で表されます。基底の整係数の線型結合です。必ず整数を係数に持つというのが、一つのポイントです。 問題は、同じ図形で表されるラティスでも、基底は複数あるということです。 ただ、その複数ある基底の中でも、ある基底は良い性質を持ち、ある基底はあまり良い性質を持たないということがあります。 何を理由に、基底の良し悪しを区別しているかは、次回に説明したいと思います。 −−−−−−−−----- 動画 「基底でラティスを定義する」を公開しました。 https://youtu.be/KrvwqcQNryo?list=PLQIrJ0f9gMcMOiLc6py4lKrk3xAG_g0FH この動画のスライドのpdf https://drive.google.com/file/d/16AOiRGIgpFQnZ2wWo1rzvGnaAPF9SI65/view?usp=sharing 関連blog 「良い基底と悪い規定」 https://maruyama097.blogspot.com/2022/08/blog-post_20.html このセミナー「ポスト量子暗号技術の現在」のまとめページ https://www.marulabo.net/docs/cipher2/ セミナーの申し込み https://cipher2.peatix.com/view

 【 暗号の世界での女性達の活躍 】 ポスト量子暗号の技術の中核はラティス暗号です。現代は、ラティス暗号の時代の始まりと考えることができます。　 このセッションでは、ラティス暗号の現在までの発展のステージを、次の四つにまとめましたた。 　● One way functionへのLattice problemの利用 　● 先行したLattice 暗号の実装 　● LWE(Learning with errors) 　● Homomorphic encryption あわせて、代表的なプレーヤーを紹介しようと思います。 この分野での女性の活躍が目立ちます。 Ajitaiとともにラティス暗号の最初の時代を牽引したのは、Cynthia Dwork でした。彼女はまた、個人データのビッグデータとしての処理を可能としつつ、個人のプライバシーを守るdifferential privacy の提唱者としても有名です。彼女は、2017年にゲーデル賞を受賞しています。 ラティス暗号の実装で先行したNTRUのJill Pipherは、ネーター生誕100年を記念してプリンストンの高等研究所で開催された女性数学者による連続セミナーに招かれて、暗号の世界で「声が大きい人」の横暴を批判していました。彼女は、2019年からアメリカ数学会の会長を務めていました。 GGH暗号のGoldwasserは、ゲーデル賞を二度受賞し、2012年にはチューリング賞を受賞しました。彼女は、暗号理論だけでなく、ゼロ知識証明でもInteractive Proofでも大きな仕事をしています。偉大な数学者です。 動画 「ラティス暗号の時代の始まり」を公開しました。   https://youtu.be/oveQgUObirA?list=PLQIrJ0f9gMcMOiLc6py4lKrk3xAG_g0FH この動画のスライドのpdf https://drive.google.com/file/d/1QQ7r4g7JmPWhYPyqf3sP3wLVwkP8xZ5h/view?usp=sharing 関連blog 「 暗号の世界での女性達の活躍」　 https://maruyama097.blogspot.com/2022/08/blog-post_18.html    −−−−−...

【 Shorのアルゴリズムを発見した時、Shorが考えたこと 】　 Shorが、Shorのアルゴリズムを発見した時、Shorは、量子コンピュータの可能性について、どんなことを考えていたのでしょうか？ 「コンピュータサイエンスの歴史において、最も重要な問題は、多項式時間またはNP完全問題のいずれかであることがわかっています。 したがって、量子コンピュータは、NP完全問題を解くことができない限り、おそらくそれほど広くは役に立たないでしょう。」 「 NP完全問題を効率的に解くことは、理論的コンピュータ科学の「聖杯」です。それが、古典的なコンピュータ上で可能であると期待するのは、非常に少数の人々だけです。量子コンピュータ上で、これらの問題を解決するための多項式時間アルゴリズムを見つけることは、画期的な発見となるでしょう。」 「 量子コンピュータはNP完全問題を解くのに十分に強力ではないといういくつかの弱い徴候があります[Bennett et al。1994]。しかし、私はこの可能性がまだ排除されるべきであるとは思いません。」 Shorは、現代のコンピューターが多項式時間では解けない「NP完全問題」を、量子コンピュータが解く能力を持つだろうと期待していました。 残念ながら、彼は彼の期待が実現可能だと示すことはできませんでした。 同じ頃、Vazirani たちは、量子チューリング・マシンを定義して、その上で多項式時間で計算可能な量子複雑性のクラス BQPを定義します。そして、このBQPクラスが、古典的なチューリング・マシンが多項式時間で計算可能なクラスPを包摂することを証明します。P ⊆ BQP 。 BQPクラスの発見は、現在のコンピューターを上回る能力を量子コンピューターが持ちうることを、複雑性理論の言葉で述べたものです。 量子コンピューターで多項式時間で計算可能なShorのアルゴリズムは、まさに、BQPクラスに属するものでした。 しかしながら、BQPクラスが「NP完全クラス」を包摂する可能性があるという展望は、現在では、ほとんどの複雑性の理論家は、「正しくない」と放棄しているように思えます。 動画 「Shorのアルゴリズムの発見 −− 計算複雑性の新しいクラス BQP」を公開しました。   https://youtu.be/wcsbtH7Ig1k?list=PLQI...

【 お盆休みにどうぞ 】 最近、「いちばんやさしい〇〇」というタイトルを持つ本が炎上したのですが、その理由は「いちばんやさしい」からではなく、内容がひどかったからだと思います。 「いちばんやさしい」というタイトルが人の眼をひくのでしょうね。ただ、僕は、そこが少し気になっています。 「やさしい」ことは、いいことなのでしょうか？ だって、世の中には難しい問題が沢山あります。なんでも、やさしく理解できるとは限りません。 「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年になってからのことです。三人の研究者は、さぞ無念だったと思います。 動画 「暗号の歴史 -- 現代暗号技術の成立」を公開しました。 htt...

【 女性たちが日本の暗号を破った 】　 このセッションでは、現代暗号技術成立以前の、特に、第二次世界大戦時の暗号の話をしています。　 先に、ドイツのEnigma暗号を解読するのに、Turingが大きな役割を果たしたことをふれました。実は、日本の暗号を解読したのは、Genevieve Grotjan を中心とする女性のチームでした。"Code Girls" という本に詳しく述べられています。https://amzn.to/2K1N23g セッションの後半では、古代文字の解読の話をしています。 いずれも、画像が中心のスライドです。お楽しみください。    こうした個人のスキルに依拠した、暗号解読のスタイルは、現代的な暗号技術の登場によって、大きく変化します。それについては次回のセッションでお話しします。 動画 「暗号の歴史 -- 現代暗号技術成立以前」を公開しました。 https://youtu.be/9QnssGGghd0?list=PLQIrJ0f9gMcMOiLc6py4lKrk3xAG_g0FH この動画のスライドのpdf https://drive.google.com/file/d/10LblwNSP0uYUWrFq7E6Efqw7hUIZy3cS/view?usp=sharing 関連blog 「 女性たちが日本の暗号を破った」 https://maruyama097.blogspot.com/2022/08/blog-post_08.html   −−−−−−−−----- このセミナーのまとめページ https://www.marulabo.net/docs/cipher2/ 参考資料 Status Report on the Third Round of the NISTPost-Quantum Cryptography Standardization Process        https://doi.org/10.6028/NIST.IR.8413 MaruLabo 関連ページ 「暗号技術の現在 -- ポスト量子暗号への移行と量子暗号」 https://www.marulabo.net/docs/cipher/

【 かつて、暗号技術は「国家機密」だった  -- Turing の場合】　 かつて（といっても、そう遠くない過去には）、暗号技術は「国家機密」だったことは、多くの人は知っていると思います。第二次大戦中のドイツの暗号機 Enigma をめぐる攻防は、有名です。 ただ、かつて暗号技術が「国家機密」だったという事実は、暗号の歴史を振り返る時、非常に重い意味を持っています。 Enigma暗号の解読に大きな役割を果たしたのはTuring でした。ただ、戦争に行方も左右したと言っていいTuringのこの分野での功績は、生前、公式には認められることは一度もありませんでした。誰が暗号解読にたずさわり、どんな仕事をしたかは「国家機密」だったのです。 1952年、Turingは「同性愛法」で訴えられます。当時のイギリスでは、同性愛は犯罪でした。彼は、投獄か薬物的去勢かの選択をせまられます。 英国のブラウン首相は2009年、エリザベス女王は2013年、戦時中のTuringの貢献を高く評価し、公式に謝罪し、Turingの「名誉回復」がなされます。ただ、それは Turingが自殺してから、50年以上たってからでした。 −−−−−−−−−-------−−−−−−---- この動画のURL https://youtu.be/cJN9QK39iT0?list=PLQIrJ0f9gMcMOiLc6py4lKrk3xAG_g0FH この動画のスライドのpdf https://drive.google.com/file/d/1-lj9VGk1GoyLr7CHVz9xsMNPXAE6WHWq/view?usp=sharing blog post https://maruyama097.blogspot.com/2022/07/blog-post.html このセミナーのまとめページ https://www.marulabo.net/docs/cipher2/ 参考資料 Status Report on the Third Round of the NISTPost-Quantum Cryptography Standardization 　　　Process        https://doi.org/10.6028/NIST.IR.8413 ...

【 マルレク「ポスト量子暗号技術の現在」へのお誘いです 】 次回マルレクへのお誘いのビデオです。ご覧下さい。 この動画のURL https://youtu.be/G6HnXTwnIsY?list=PLQIrJ0f9gMcMOiLc6py4lKrk3xAG_g0FH この動画のスライドのpdf https://drive.google.com/file/d/10CPUMhLuTyj06-OQpRV14kenvDXMiEPO/view?usp=sharing blog post https://maruyama097.blogspot.com/2022/08/blog-post.html このセミナーのまとめページ https://www.marulabo.net/docs/cipher2/ 参考資料 Status Report on the Third Round of the NISTPost-Quantum Cryptography Standardization 　　　Process        https://doi.org/10.6028/NIST.IR.8413 MaruLabo 関連ページ 「暗号技術の現在 -- ポスト量子暗号への移行と量子暗号」 https://www.marulabo.net/docs/cipher/

【 「量子インターネットという未来」講演ビデオ公開します 】  MaruLaboでは、以前に行われたセミナーの講演ビデオを無償で公開しています。 今回は、4月30日に行われたマルゼミ「量子情報と通信技術 -- 量子インターネットという未来」の講演ビデオの公開です。ご利用ください。 インターネットの未来については、現在、さまざまな議論があります。ただ、インターネットの「世代」は、たかだか 20年か30年で変わっていくものです。さらにその先を見据えることは可能なのではないかと考えています。 このセミナーは、21世紀は量子の時代になるという基本的な時代認識から、「量子インターネット」という未来から、現在の技術的到達点を振り返ったものです。 このセミナーのコンテンツ自体とは独立なのですが、このセミナーでは量子の時代の新しい技術を展望する上で、実践的に重要と思われる留意点を二つ述べています。 一つは、量子理論のIT技術への応用は、いわゆる「量子コンピュータ」に限られるものではないということです。このセミナーで取り上げた「量子ネットワーク」は、量子理論のIT技術への応用のもう一つの重要な領域です。 そのことは、現代のIT技術の到達点は、もっぱらコンピュータ技術の進化で説明できるわけではないことを考えればわかります。重要な変化は、クラウドにしろスマートフォンにしろ、サイズの異なる無数のコンピュータが、グローバルに高速のネットワークで結合されたことです。そこで技術の様相が大きく変わりました。ネットワーク技術は本質的に重要です。 もう一つ留意すべきことがあります。 少なくない熱心なIT技術者が、量子理論のIT技術への応用ということで、「量子力学」の勉強を始めています。それ自体は悪いことではないかもしれません。 ただ、「量子力学」は量子論の「力学」への応用です。コンピュータもネットワークも直接には「力学」の対象ではありません。学ぶべき主要なターゲットは、量子論を「情報理論」に適用した「量子情報理論」です。 量子力学と量子情報理論が異なるものであることは、かつて量子力学の領域で「エンタングルメント」が発見されてから、そのもっとも重要な量子情報論的応用である「量子テレポーテーション」が発見されるまで、60年かかったことを考えればわかります。普通に量子力学を 50年勉強していても、量...

【 次回のマルレクは「ポスト量子暗号技術の現在」がテーマです 】 先月7月、米NIST ( National Institute of Standards and Technology )は、「ポスト量子暗号技術の標準化」についての重要な文書 NIST IR 8413 を公開しました。 　　Status Report on the Third Round of the NIST 　　Post-Quantum Cryptography Standardization Process        https://doi.org/10.6028/NIST.IR.8413 暗号化技術は、今、歴史的な転回点を迎えています。 3年前の2019年の6月、マルレクで「暗号技術の現在 -- ポスト量子暗号への移行と量子暗号」というセミナーを開催しました。 https://www.marulabo.net/docs/cipher/ この3年前のマルレクは、NISTの「ポスト量子暗号標準化プロセス」のラウンド 3 の取り組みを紹介したものです。今年のNISTのレポートは 、ラウンド 3 での議論を総括して、ラウンド 4  --ポスト量子暗号技術の標準化の道筋を具体的に示しました。 次回のマルレクのPart I では、まず、このNISTのレポートを紹介しようと思います。 次回のマルレクのPart II では、どのような暗号技術が、量子コンピュータの「Shorのアルゴリズム」の脅威に晒されているのかを説明しようと思います。 「Shorのアルゴリズム」で、巨大な自然数の素因数分解が多項式時間で高速に可能となることはよく知られていて、それゆえ、素因数分解の難しさに依拠するRSA暗号も安全ではないこともよく知られていると思います。 ただ、「Shorのアルゴリズム」の脅威の射程は、それだけではないことは、あまり知られていないように思います。 すこし難しい話になるかもしれないのですが、「Shorのアルゴリズム」で解ける問題は、特定の数学的性質を共通に持っています。 実践的に重要なことは、このクラスの中に、RSA暗号だけでなく、離散対数暗号や楕円曲線暗号も含まれていることです。3年前の NISTやNSAのレポートは、特に、暗号通貨やブロックチェ...