弱一方向性関数

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

弱一方向性関数

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

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

関数 f: Σ* → Σ* が以下を満たす時、関数 f は弱一方向性関数であるという： f は多項式時間で計算可能。 ある多項式 P が存在し、任意の多項式時間アルゴリズム A に対し、ある k0 が存在し、全ての k > k0に対し、Pr[z≠f(x) | x ←R Σk, y ← f(x), z ← A(1k, y)] > 1/P(k)。 定理 一方向性関数が存在する必要十分条件は弱一方向性関数が存在する事である。 証明の概略（⇒）自明。 （⇐）f を弱一方向性関数とする。g を g(x1 || … || xN) = f(x1) || … || f(xN) と定義する。ただしここで「||」はビット列の連接、N = 2kP(k)。（P は弱一方向性関数の定義の条件 2 にあるもの）。この時 g-1 を求めるには、f -1 を N 回計算しなければならない。 どのようなアルゴリズムを用いても f -1 を計算するには 1/P(k) ステップかかるので、f -1 を N 回計算するのは多項式時間ではできない。