非一様一方向性関数

ウィキペディア小見出し辞書

非一様一方向性関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/17 00:27 UTC 版)

「一方向性関数」の記事における「非一様一方向性関数」の解説

関数 f: Σ* → Σ* が以下を満たす時、関数 f は 非一様一方向性関数であるという： f は多項式時間で計算可能。 任意の多項式時間サイズの回路族 A = {Ak} に対し、ある無視可能函数 ν が存在して、Pr[x ← Ak(y) | x ←R Σk, y ← f(x)] < ν(l)。 多項式時間アルゴリズムは多項式時間サイズの回路族で表す事ができるので、非一様一方向性関数は必ず一方向性関数である。しかし逆はよく分かっていない。