一方向性関数

一方向性関数（いちほうこうせいかんすう、）とは、関数値は容易に計算できるが逆関数の計算は非常に困難である関数を指す。暗号理論などで用いられる概念である。素因数分解問題の困難性を用いたものが代表的。
下では、単に「多項式時間アルゴリズム」と書いたら「平均多項式時間確率アルゴリズム」を指す。
厳密な定義.
formula_1 で自然数の集合を表す。
Σ = {0, 1} とし、formula_2とする。
関数 formula_3 が以下を満たす時、関数 formula_4 は一方向性関数であるという：
一方向性関数の存在性.
現在のところ、一方向性関数の存在性は証明されていない。
（一方向性関数の存在性が示せれば、P≠NP が系として従う）。
しかし、一方向性関数の候補となる関数はいくつか知られている。
一方向性関数が存在すると証明が与えられたわけではないものの、
暗号理論では一方向性関数の存在性を仮定して議論を進める。
一方向性関数族.
"I" を Σ* の部分集合とし、
"D" = {"D""n"}"n" ∈ "I"、"R" ={"R""n"}"n" ∈ "I" を Σ* の
部分集合の族とする。
"G"1、"G"2 を多項式時間アルゴリズムとし、
"F" = {"f""k": "D""k" → "R""k"} を関数の族とする。
組 ("D", "R", "G"1, "G"2, "F") が以下を満たすとき、("D", "R", "G"1, "G"2, "F") を一方向性関数族という：
一方向性関数が存在する事は一方向性関数族が存在する事の必要十分条件である事が知られている。
弱一方向性関数.
関数 "f": Σ* → Σ* が以下を満たす時、関数 "f" は弱一方向性関数であるという：
定理　一方向性関数が存在する必要十分条件は弱一方向性関数が存在する事である。
証明の概略（⇒）自明。
（⇐）"f" を弱一方向性関数とする。"g" を "g"("x"1 || … || "x""N") = "f"("x"1) || … || "f"("x""N") と定義する。ただしここで「||」はビット列の連接、"N" = 2"kP"("k")。（"P" は弱一方向性関数の定義の条件 2 にあるもの）。
この時 "g"-1 を求めるには、"f" -1 を "N" 回計算しなければならない。
どのようなアルゴリズムを用いても "f" -1 を計算するには 1/"P"("k") ステップかかるので、"f" -1 を "N" 回計算するのは多項式時間ではできない。
非一様一方向性関数.
関数 "f": Σ* → Σ* が以下を満たす時、関数 "f" は 非一様一方向性関数であるという：
多項式時間アルゴリズムは多項式時間サイズの回路族で表す事ができるので、非一様一方向性関数は必ず一方向性関数である。しかし逆はよく分かっていない。
一方向性関数の候補.
集合 {("p", "q") ∈ formula_12 | "p", "q" は素数で、"p" のビット数 = "q" のビット数} から自然数の集合 formula_1への写像 ("p", "q") formula_12 "pq" は一方向性関数であると予想されている。
必要十分条件.
以下は全て同値である。