一方向性関数
一方向性関数(いちほうこうせいかんすう、英: one-way function)とは、関数値は容易に計算できるが逆関数の計算は非常に困難である関数を指す。「トラップドア関数」という別称がある。
暗号理論などで用いられる概念である。素因数分解問題の困難性を用いたものが代表的。
以下では、単に「多項式時間アルゴリズム」と書いた場合は「平均多項式時間確率アルゴリズム」を指す。
I を Σ の部分集合とし、
D = {Dn}n ∈ I、R ={Rn}n ∈ I を Σ の
部分集合の族とする。 G1、G2 を多項式時間アルゴリズムとし、 F = {fk: Dk → Rk} を関数の族とする。 組 (D, R, G1, G2, F) が以下を満たすとき、(D, R, G1, G2, F) を一方向性関数族という:
G1 は 1 を入力すると n ∈ I∩Σ を出力するアルゴリズム。
G2 は n ∈ I を入力すると x ∈ Dn を出力するアルゴリズム。
ある多項式時間アルゴリズム C があって C(x, n) = fn(x)。
任意の多項式時間アルゴリズム A に対し、ある negligible な関数 ν とある k0 ∈ N {\displaystyle {\mathbb {N} }} が存在して、全ての k > k0 に対し、Pr[x ← A(n, y) | n ← G1(1), x ← G2(n), y ← f(x)] < ν(l)。
一方向性関数が存在する事は一方向性関数族が存在する事の必要十分条件である事が知られている。