過去・現在・未来

【 8/27 マルレク「暗号技術の現在」講演資料と講演ビデオ公開しました 】  MaruLaboでは、実施したセミナーの講演資料と講演ビデオを公開しています。 今回は、8月27日に行ったマルレク「暗号技術の現在」のセミナーの 講演資料と講演ビデオの公開です。ご利用ください。 講演資料： https://drive.google.com/file/d/172wp0DjNR1BehXyBejI4g_yXgxHT55fE/view?usp=sharing 講演ビデオ再生リスト： https://www.youtube.com/playlist?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz この「暗号技術の現在」の再生リストは、次の四つのビデオから構成されています。 　●  「暗号技術の現在」概説 https://youtu.be/LGkK28M1NPE?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz 　●  第1部 「現代暗号技術の成立」 https://youtu.be/Rpl4a7Whd7A?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz 　●  第2部 「ショアのアルゴリズムの発見」 https://youtu.be/itRvFSmIpgc?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz 　●  第3部 「ラティス暗号の時代の始まり」概説 https://youtu.be/K5-YWvcbfVw?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz このセミナー「暗号技術の現在」の参考資料・ショートムービーは、次のMaruLaboのサイト   https://www.marulabo.net/docs/cipher2/  からアクセスできます。 また、このセミナーは 内容的には、9月のマルゼミ「ラティス暗号入門」に続いています。こちらのページも参照ください。マルゼミ「ラティス暗号入門」： https://www.marulabo.net/docs/ciphe

 　「先生、肉牛と乳牛の違いわかりますか？」 昔、稚内に引っ越した頃、知り合いになった酪農家に聞かれたことがある。 　「食肉になる牛と、ミルクをだす牛の違いでしょ。（まんまだ）」 　「あ、乳牛はメスだけで、肉牛は、どっちもあり。（あたりまえだ）」 そんなことではなかった。 　「肉牛には名前がないけど、乳牛には名前があるんです。」 彼が言うには、肉牛は名前を持たず番号で管理されるが、乳牛は「メリー」とか「ベス」と名前をつけられて、酪農家に大事に育てられるのだという。 そうなんだ。知らなかった。 先日、近所のスーパーで「ホルスタイン」（これは乳牛）の肉が売っていた。珍しい。ローストビーフにして食べたが、新鮮で、ほとんどレアでもとても美味しかった。 宗谷では、人間より牛の数が多い。「宗谷黒牛」というブランドで肉牛も育てているが、それは宗谷岬一帯だけで、ほとんどは乳牛・ホルスタインだ。 大事に育てられていても、乳牛だって、僕ら人間と一緒で、いつか斃れる。ペットの葬式は普通にあるが、牛の葬式は見たことない。というかそんなこと、考えたこともなかったが。 美味しくいただいたお肉には、「個体識別番号」が明記されていた。乳牛にも番号あるじゃないか。 もしも、僕が誰かに食べられるなら、マイナンバーや戒名じゃなく、名前を使って欲しいな。

【 量子コンピュータであることを確認する方法 】 今回は、Mahadevの論文の紹介です。 2018年の論文全てではなく、彼女の仕事の一部である「Quantum Certification Protocol」の紹介です。これは、検証者が対話している相手のコンピュータが、本当に量子コンピュータであるのかをチェックするというプロトコルで、いわゆる「量子優越性」の実証に利用できるものです。 今回紹介するプロトコルとそのバリアントは、彼女のもっと大きな対話プロトコルの「1ラウンド」を形成することになります。「1ラウンド」というのは、今回見たプロトコルを一つのブロックとして、何度も何度も、何ラウンドも、対話を繰り返すのです。 今回見たプロトコルで、「標準基底で測定する」「Hadamard基底で測定する」という選択肢が含まれているのですが、それぞれの選択をSとHで表すと、SとHからなる長い並びで、大きな対話を特徴づけることができます。 彼女は、こうした対話を通じて、相手の量子デバイスを自分の忠実な「量子状態測定器」にかえます。こちらが本論なのですが、今回は、残念ながら触れることができませんでした。 また、いろいろ、説明が足りないところがあることに気づきました。 今日のセッションで、いきなりProver（証明者）とVerifier（検証者）という言葉が出てくるので、少し気になったのですが、Mahadevが対話型証明の手法を使ったということは触れていましたが、こうした数学的な「対話型証明」の設定と、彼女の「対話型証明」の設定には、違いがあります。 数学的な対話型証明の「証明者」は、能力に制限のない「全能者」でしたが、Mahadevの「証明者」は、そうではありません。能力に限界があります。Mahadevの「証明者」の能力は、量子複雑性の言葉で「BQP」と特徴づけられています。（ショアのアルゴリズムが属するクラスです）また、検証者の能力は「BPP」と定義されています。 それは、文脈上は明らかかもしれませんが、きちんと説明したほうがよかったと思っています。なぜなら、問題を明確に定義することが問題解決には不可欠ですから。 -------------------------------- 「 Quantum Certification Protocol 」 を公開しました。 https:/

【 LWE暗号の利用 】 Mahadevの論文を読む準備をしています。 Mahadevの量子計算の古典的検証では、古典コンピュータ上で実装可能で、しかし、量子コンピュータでも解読できない暗号、ポスト量子暗号のLWE暗号を利用します。今回のセッションでは、そのことを見ていきます。 基本的には、前回見た Trapdoor Claw-Free Functions (TCF) をLWEを使って定義します。こうして再定義された TCFを Noisy Trapdoor Claw-Free Functions (NTCF) といいます。それについては、セッションのスライドとビデオを参照ください。 ここでは、参考にした 2021年のMahadev達の論文の「はじめに」の部分が、よくまとまっていたので、それを紹介したいと思います。 「この論文では、純粋に古典的な検証者が、多項式時間に制限された一つの量子マシンと相互作用する新しいモデルを考察する。」 「量子デバイスの計算を多項式時間に制限することで、検証者は、ポスト量子暗号、すなわち、古典コンピュータ上で効率的に実装可能であるが、量子コンピュータでも解読できない暗号の基本技術を活用することができる。」 「このモデルでは、「信頼できない量子デバイスが “本当に ”量子的であることを効率的に検証する方法」と「信頼できない量子デバイスから検証可能な乱数文字列を生成する方法」という2つの基本的問題に対する解決策を提案する。」 「一つ目の課題は「量子優越性の証明問題」とも呼ばれ、既存のプロトコルでは、古典的スーパーコンピュータを用いて指数関数的な時間をかけて検証する必要がある。それに対し、本論文のqubit検証テストは、古典的検証者が多項式時間で検証可能な量子性の証明を提供する。」 「信頼できない量子デバイスを扱う難しさの中核には、デバイスの操作を通じて、量子デバイスの内部にあるqubitの構造を持たせることを強制することにある。すなわち、量子デバイスに実際にこの量子ビットを保持させ、また、検証者の要求に応えて、qubitの計測を実行することの難しさにある。」 この最後の部分をどう実現するかが、ポイントになります。 前回のセッションの最後の式、それは、今回のセッションの最後の式とも同じなのですが、claw (x0, x1) に対して、clawの

【 clawとは何か 】 Mahadev の論文を読む上で必要な準備をしています。 今回は、Mahadevの暗号の利用で重要な役割を果たしている Trapdoor Claw-Free Functions の話をしようと思います。 Trapdoor というのは、現代の暗号の基本的な構成要素である「一方向関数」のことです。xからf(x)を求めるのは易しいのですが、逆に、f(x)からxを求めるのが難しい関数を、「一方向関数」といいます。 例えば、二つの素数p,qから、その積 N=pqを求めるのは簡単ですが、逆の、二つの素因数を持つ大きな数Nが与えられたとき、Nからその素因数p,qを求めるのは難しいです。そのギャップを利用しようと言うのが、RSA暗号の基本的なアイデアです。 「一方向関数」の上に見た説明に出てくる「易しい」とか「難しい」という言葉、感覚的にはわかると思うのですが、その定義を正確に述べるのは難しいことです。 「易しい」の定義は比較的簡単で、計算に要する時間が「多項式時間」であれば「易しい」と考えることができます。 ただ、「難しい」をその計算に要する時間が「多項式時間」ではなく「指数関数的時間」だとすればいいのでしょうか？ ある計算が、本当に「指数関数的時間」かかることを示すのは、難しいです。ある計算法では、「指数関数的時間」がかかるけど、素晴らしいアルゴリズムが発見されて、その計算が、「多項式時間」で終わる可能性があるからです。 （逆に、「多項式時間」で済む計算にも、「指数関数的時間」が必要な「おばかアルゴリズム」は存在します。おひまなら僕の「計算理論入門 -- 「やさしい計算」と「むずかしい計算」」をご覧ください。割り算を掛け算で計算できるのですが、とても手間がかかります。https://drive.google.com/file/d/1MNnGRkCJAsrR1GeKPyhVMk3VLYfnDhZH/view ） 「一方向関数」が存在すると言うことは、数学的にはキチンと証明されていません。 「易しい」とか「難しい」というけど、それは程度問題で、実際には、「一方向関数」といわれているものも、その逆関数も実は「多項式時間」で計算できる。ただ、そのやり方に気づいていないだけだ。と考えることもできるのですから。 実は、「一方向関数が存在する」という命題は、複雑性理

【 任意のf(x)を計算する量子回路を考える 】 Mahadev の論文を読む上で必要な準備をしています。 前回は、ポスト量子暗号のLWE (Learning with Errors)が、古典コンピュータで実装できるアルゴリズムだということを紹介しました。Mahadevの方法は、この古典的に実装可能なLWE暗号を量子コンピュータは破ることはできないということを前提にしています。 Mahadevは、古典コンピュータと量子コンピュータを「対話」させます。正確にいうと、古典コンピュータと人間が一緒にチームを作って、その混合チームを量子コンピュータと対話させます。この対話は「対戦」でもあります。対戦しているのは古典コンピュータと人間の混合チームと単独の量子コンピュータです。 なぜ、人間と古典コンピュータが、同じ仲間になるのかと言えば、量子コンピュータとの関係では、両者は共に同じような能力しか持っていないからなのですが、そこは、「いや、コンピュータ（古典）より、人間がエライ」「そんなことはない。AIをみろ。人間はコンピュータ（でも古典）にかなわない」という議論はあるでしょうが、それは等しく古典的なものの内輪揉めとして、先に進みます。納得いかない人も多いと思いますので、それについては、次回に説明します。 対話あるいは対戦は、古典チームが量子コンピュータにある計算の実行を指示することで始まります。量子コンピュータはそれを計算しその結果を古典チームに返します。古典チームは、その結果を見て新しい指示を量子コンピュータに出します。こうしたことを繰り返します。 量子コンピュータは、古典族と同様に計算を行う能力を持つのですが、その計算のスタイルは、ちょっと変わっています。今回のビデオのセッションは、そのことにフォーカスしています。 関数を計算する量子回路を考えます。量子回路は、量子ゲートから構成されているのですが、量子ゲートは、すべて「ユニタリ性」という性質を持ちます。その結果、量子回路自体も「ユニタリ性」を持つことになります。 量子回路のユニタリ性というのは、簡単に言えば、入力から出力を返す量子回路は、入力と出力を鏡に移したように回路ごと反転させれば、出力から入力を得ることができるという性質です。計算結果の出力から、時間を遡ったように入力を復元できると考えることもできます。これを、可逆性

【 Post量子暗号 】 「Post量子暗号」という名前は一般的に利用されているのですが、「量子の後の暗号」とか、「量子暗号の次のもの」と受け止められかねない、少しミスリーディングな名前のように、僕は感じています。かといって代わりの名前がすぐに思い浮かぶわけではないのですが。 この名前の中の「量子」という言葉でイメージしているのは、量子コンピュータが現在の暗号技術に対する脅威になりうるという認識なのではないかと思います。 「ショアのアルゴリズムの発見は、暗号技術にとって危機だったが、それを乗り越える暗号技術を我々は必要としている。」ということなら、気持ちはよくわかります。 ですから、「Post量子暗号」のコンセプトが含意していることは、まず、「量子コンピュータによる暗号破りの攻撃を跳ね返すことができること」です。これを「量子耐性をもつ暗号」といったりします。「Post量子暗号」を「量子耐性暗号」と言い換えてもいいのです。 ただ、現在の「Post量子暗号」のコンセプトには、もうひとつ大事な含意があります。残念ながら、そのことは、この名前にはあまり反映されていないように思えます。当たり前すぎるからでしょうか？それは、それが量子コンピュータの上ではなく、現在のコンピュータの技術の上に構築される技術だということです。 これも、ミスリーディングな言い方に聞こえるかもしれませんが、「現在のコンピュータ」を量子コンピュータとの対比で「古典コンピュータ」といいます。「古典コンピュータ」というのは、「そろばん」のことではありません。 「Post量子暗号」技術は、量子コンピュータによる暗号攻撃を跳ね返すことの出来る、古典コンピュータ上の技術です、これは、量子コンピュータとの対比で「古典コンピュータ」の能力を考えたとき、一般的には、ほとんどすべての点で、量子コンピュータが優っていることを考えれば、とても興味深い性質だと思います。決して、当たり前のことではありません。 Mahadevは、まさにこのことを、量子コンピュータのコントロールに利用しようとしたことは、前回述べました。 今回のビデオのセッションでは、「Post量子暗号」の中心的技術である、Learning with Error のアルゴリズムの実装を、ざっとみていきます。これなら、古典コンピュータで実装できることはわかると思います。