一方向性関数
関数 f: Σ → Σ が以下を満たす時、関数 f は 非一様一方向性関数であるという:
f は多項式時間で計算可能。
任意の多項式時間サイズの回路族 A = {Ak} に対し、ある無視可能函数 ν が存在して、Pr[x ← Ak(y) | x ←R Σ, y ← f(x)] < ν(l)。
多項式時間アルゴリズムは多項式時間サイズの回路族で表す事ができるので、非一様一方向性関数は必ず一方向性関数である。しかし逆はよく分かっていない。
集合 {(p, q) ∈ N {\displaystyle {\mathbb {N} }} | p, q は素数で、p のビット数 = q のビット数} から自然数の集合 N {\displaystyle {\mathbb {N} }} への写像 (p, q) ↦ {\displaystyle \mapsto } pq は一方向性関数であると予想されている。