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 )

「一方向関数」が存在すると言うことは、数学的にはキチンと証明されていません。

「易しい」とか「難しい」というけど、それは程度問題で、実際には、「一方向関数」といわれているものも、その逆関数も実は「多項式時間」で計算できる。ただ、そのやり方に気づいていないだけだ。と考えることもできるのですから。

実は、「一方向関数が存在する」という命題は、複雑性理論の大問題である P≠NPを含意します。さきに、「一方向関数が存在する」ことは、数学的には、キチンと証明されていないといったのは、P≠NPであることが、まだ数学的には証明されていないからです。

ただ、ほとんどの数学者は、 P≠NPだと信じているので、一方向関数が存在すると信じています。数学でも「信じる」ことは大事です。(ほんとかな)

その点、Claw-Free Functions は、その逆関数を計算することが難しいことが、とてもわかりやすい関数です。

x≠yなるx,y について、f(x)=z , f(y)=z と定義します。zが与えられたとき、この関数f の逆関数を考えましょう。難しいですね。難しいと言うより、答えが二つあります。どう頑張っても答えが一つに決まりません。fの逆関数をf^{-1で表すことにすると、f^{-1}(z)=xもf^{-1}(z)=y も正解です。

こうしたとき、この二つの答えの組 (x, y) を"claw"と呼びます。("claw"って、「鉤」とか「爪」ですよね。ちがうのかしら。これらを claw と呼ぶ意味、僕はあまり理解できていません。)

Claw-Free Functionsというのは、なにもMahadevのアイデアではありません。すでに、1980年代に、電子署名の技術として、Goldwasser たちによって提案されています。(ちなみに、Goldwasserも女性です)

Mahadevの素晴らしいアイデアは、このclaw (x, y)から、次のような重ね合わせの状態を、量子コンピュータ内に作ることです。

       ( |0>|x> + |1>|y> )/√2

量子コンピュータでも、暗号としてclaw (x,y)は、計算できません。( claw-free というのは「clawは存在しない」と言う意味です。その心は、計算してもclawは見つからないということです。)

ん。先の状態は、|x>と|y>を同時に含んでいますね。何か不思議な感じがします。

--------------------------------

「Trapdoor Claw-Free Functions  」 を公開しました。

スライドのpdf
https://drive.google.com/file/d/1P7Thc9KnkR_r2lZNhfiWN6jBIQuVi_IO/view?usp=sharing

blog:「Clawとは何か 」
https://maruyama097.blogspot.com/2022/11/claw.html

まとめページ「量子計算の古典的検証 」 

セミナーへの申し込み

参考資料
Mahadev Classical Verification of Quantum Computations
https://arxiv.org/pdf/1804.01082.pdf



コメント

このブログの人気の投稿

マルレク・ネット「エントロピーと情報理論」公開しました。

初めにことばありき

人間は、善と悪との重ね合わせというモデルの失敗について