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>を同時に含んでいますね。何か不思議な感じがします。
--------------------------------
https://arxiv.org/pdf/1804.01082.pdf
コメント
コメントを投稿