一方向性関数
N {\displaystyle {\mathbb {N} }} で自然数の集合を表す。 Σ = {0, 1} とし、 Σ ∗ = ∪ k ∈ N Σ k {\displaystyle \Sigma ^{*}=\cup _{k\in {\mathbb {N} }}\Sigma ^{k}} とする。
関数 f : Σ ∗ → Σ ∗ {\displaystyle f:\Sigma ^{*}\to \Sigma ^{*}} が以下を満たす時、関数 f {\displaystyle f} は一方向性関数であるという:
f {\displaystyle f} は多項式時間で計算可能。すなわちある多項式時間アルゴリズム C があって C(x) = f(x)
任意の多項式時間アルゴリズム A に対し、ある 無視可能函数 ν {\displaystyle \nu } と、ある k 0 ∈ N {\displaystyle k_{0}\in {\mathbb {N} }} が存在して、全ての k > k0 に対し、 P r [ x ← R Σ k , y ← f ( x ) , x ′ ← A ( 1 k , y ) : y = f ( x ′ ) ] ≤ ν ( l ) . {\displaystyle Pr\left[x\gets _{R}\Sigma ^{k},y\gets f\left(x\right),x'\gets A\left(1^{k},y\right):y=f\left(x'\right)\right]\leq \nu \left(l\right).}