| |
|
一方向性関数（いちほうこうせいかんすう,oneway function）とは、簡単に計算できるが逆関数の計算は非常に困難である関数の事。暗号理論の概念。素因数分解問題の困難性を用いたものが代表的。 以下特に断りがなければ、単に「多項式時間アルゴリズム」といったら平均多項式時間確率アルゴリズムを指すものとする。
| Table of contents |
|
2 一方向性関数の存在性 3 一方向性関数族 4 弱一方向性関数 5 non uniform な一方向性関数 6 一方向性関数の候補 7 必要十分条件 |
関数f:∑*→∑*が以下を満たす時、関数fは一方向性関数であるという：
現在のところ、一方向性関数の存在性は証明されていない。
（一方向性関数の存在性が示せれば、P≠NPが系として従う）。
しかし、一方向性関数の候補となる関数はいくつか知られている。
一方向性関数が本当に存在するのかどうかは誰も分からないものの、
暗号理論では一方向性関数の存在性を仮定して議論を進める。
定理 一方向性関数が存在する必要十分条件は弱一方向性関数が存在する事である。
集合{(p,q)∈N2|p,qは素数で、pのビット数＝qのビット数}から自然数の集合Nへの写像 (p,q)→pqは一方向性関数であると予想されている。厳密な定義
Nで自然数の集合を現す。
∑={0,1}とし、∑*=∪k∈N∑kとする。一方向性関数の存在性
一方向性関数族
Ｉを∑*の部分集合とし、
Ｄ＝{Ｄn}n∈Ｉ、Ｒ＝{Ｒn}n∈Ｉを∑*の部分集合の族とする。
Ｇ1、Ｇ2を多項式時間アルゴリズムとし、
F={fk:Ｄk→Ｒk}を関数の族とする。
組（Ｄ,Ｒ,Ｇ1、Ｇ2,F）が以下を満たすとき、（Ｄ,Ｒ,Ｇ1、Ｇ2,F）を一方向性関数族という：
一方向性関数が存在する事は一方向性関数族が存在する事の必要十分条件である事が知られている。
弱一方向性関数
関数f:∑*→∑*が以下を満たす時、関数fは弱一方向性関数であるという：
全てののk0>0に対し、Pr[z≠f(x)| x←R∑k, y←f(x),z←A(1k,y)]>1/P(k)。
証明の概略（⇒）自明。
（←）fを弱一方向性関数とする。gをg(x1||・・・||xN)=f(x1)||・・・||f(xN)と定義する。ただしここで「||」はビット列の連接、N=2kP(k)。（Pは弱一方向性関数の定義の条件2にあるもの）。
この時g-1を求めるには、f-1をN回計算しなければならない。
どのようなアルゴリズムを用いてもf-1を計算するには1/P(k)ステップかかるので、f-1をN回計算するのは多項式時間ではできない。□non uniform な一方向性関数
関数f:∑*→∑*が以下を満たす時、関数fはnon uniformな一方向性関数であるという：
多項式時間アルゴリズムは多項式時間サイズの回路族で表す事ができるので、non uniform な一方向性関数は必ず一方向性関数である。しかし逆はよく分かっていない。一方向性関数の候補