過去・現在・未来

【  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=PLQIrJ0f