一方向性関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

一方向性関数（いちほうこうせいかんすう, oneway function）とは、簡単に計算できるが逆関数の計算は非常に困難である関数の事。暗号理論の概念。素因数分解問題の困難性を用いたものが代表的。以下特に断りがなければ、単に「多項式時間アルゴリズム」といったら平均多項式時間確率アルゴリズムを指すものとする。

[編集] 厳密な定義

${\Bbb N}$ で自然数の集合を現す。 Σ = {0, 1} とし、 $\Sigma^* = \cup_{k\in{\Bbb N}}\Sigma^k$ とする。

関数 $f : \Sigma^* \to \Sigma^*$ が以下を満たす時、関数 f は一方向性関数であるという：

f は多項式時間で計算可能。すなわちある多項式時間アルゴリズム C があって C(x) = f(x)
任意の多項式時間アルゴリズム A に対し、ある negligible な関数 ν とある $k_0 \in {\Bbb N}$ が存在して、全ての k > k₀ に対し、

$Pr[x \gets_R \Sigma^k, y \gets f(x),x' \gets A(1^k, y) : y=f(x')] \le \nu(l)$ 。

[編集] 一方向性関数の存在性

現在のところ、一方向性関数の存在性は証明されていない。（一方向性関数の存在性が示せれば、P≠NP が系として従う）。しかし、一方向性関数の候補となる関数はいくつか知られている。一方向性関数が本当に存在するのかどうかは誰も分からないものの、暗号理論では一方向性関数の存在性を仮定して議論を進める。

[編集] 一方向性関数族

I を Σ^* の部分集合とし、 D = {D_n}_{n ∈ I}、R = {R_n}_{n ∈ I} を Σ^* の部分集合の族とする。 G₁、G₂ を多項式時間アルゴリズムとし、 F = {f_k: D_k → R_k} を関数の族とする。組 (D, R, G₁, G₂, F) が以下を満たすとき、(D, R, G₁, G₂, F) を一方向性関数族という：

G₁ は 1^k を入力すると n ∈ I∩Σ^k を出力するアルゴリズム。
G₂ は n ∈ I を入力すると x ∈ D_n を出力するアルゴリズム。
ある多項式時間アルゴリズム C があって C(x, n) = f_n(x)。
任意の多項式時間アルゴリズム A に対し、ある negligible な関数 ν とある k₀ ∈ ${\Bbb N}$ が存在して、全ての k > k₀ に対し、Pr[x ← A(n, y) | n ← G₁(1^k), x ← G₂(n), y ← f(x)] < ν(l)。

一方向性関数が存在する事は一方向性関数族が存在する事の必要十分条件である事が知られている。

[編集] 弱一方向性関数

関数 f: Σ^* → Σ^* が以下を満たす時、関数 f は弱一方向性関数であるという：

f は多項式時間で計算可能。
ある多項式 P が存在し、任意の多項式時間アルゴリズム A に対し、ある k₀ が存在し、全ての k₀ > 0 に対し、Pr[z≠f(x) | x ←_R Σ^k, y ← f(x), z ← A(1^k, y)] > 1/P(k)。

定理　一方向性関数が存在する必要十分条件は弱一方向性関数が存在する事である。

証明の概略（⇒）自明。

（⇐）f を弱一方向性関数とする。g を g(x₁ || … || x_N) = f(x₁) || … || f(x_N) と定義する。ただしここで「||」はビット列の連接、N = 2kP(k)。（P は弱一方向性関数の定義の条件 2 にあるもの）。この時 g^-1 を求めるには、f ^-1 を N 回計算しなければならない。