日本百科事典

home | メインページ

一方向性関数

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

厳密な定義

で自然数の集合を現す。 とし、とする。

関数 が以下を満たす時、関数 は一方向性関数であるという：

• は多項式時間で計算可能。すなわちある多項式時間アルゴリズム があって 。 • 任意の多項式時間アルゴリズム に対し、ある • negligible な関数 とある が存在して、全ての • に対し、。

一方向性関数の存在性

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

一方向性関数族

I を Σ^* の部分集合とし、 D = D_{nn ∈ I}、R = R_{nn ∈ 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₀ ∈ が存在して、全ての 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 回計算しなければならない。

どのようなアルゴリズムを用いても f ^-1 を計算するには 1/P(k) ステップかかるので、f ^-1 を N 回計算するのは多項式時間ではできない。□

non uniform な一方向性関数

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

• f は多項式時間で計算可能。 • 任意の多項式時間サイズの回路族 A = A_k に対し、ある negligible な関数 ν が存在して、Pr[x ← A_k(y) | x ←_R Σ^k, y ← f(x)] < ν(l)。

多項式時間アルゴリズムは多項式時間サイズの回路族で表す事ができるので、non uniform な一方向性関数は必ず一方向性関数である。しかし逆はよく分かっていない。

一方向性関数の候補

集合 (p, q) ∈ ² | p, q は素数で、p のビット数 = q のビット数 から自然数の集合 への写像 (p, q) pq は一方向性関数であると予想されている。

必要十分条件

以下は全て同値である。 • 一方向性関数が存在する • 弱一方向性関数が存在する • 一方向性関数族が存在する • (暗号論的)擬似乱数生成機が存在する • 擬似ランダム関数の族が存在する。 • 電子署名方式が存在する。

関連項目

暗号理論

この記事はスタブ（書きかけ）です。この記事を加筆して下さる協力者を求めています。