一方向性関数（いちほうこうせいかんすう, one-way function）とは、簡単に計算できるが逆関数の計算は非常に困難である関数を指す。暗号理論などで用いられる概念である。素因数分解問題の困難性を用いたものが代表的。以下特に断りがなければ、単に「多項式時間アルゴリズム」といったら平均多項式時間確率アルゴリズムを指すものとする。formula_1 で自然数の集合を表す。Σ = {0, 1} とし、formula_2とする。関数 formula_3 が以下を満たす時、関数 "f" は一方向性関数であるという：現在のところ、一方向性関数の存在性は証明されていない。（一方向性関数の存在性が示せれば、P≠NP が系として従う）。しかし、一方向性関数の候補となる関数はいくつか知られている。一方向性関数が存在すると証明が与えられたわけではないものの、暗号理論では一方向性関数の存在性を仮定して議論を進める。"I" を Σ の部分集合とし、"D" = {"D"}、"R" ={"R"} を Σ の部分集合の族とする。"G"、"G" を多項式時間アルゴリズムとし、"F" = {"f": "D" → "R"} を関数の族とする。組 ("D

出典:wikipedia