一方向性関数 - Wikipedia

現在のところ、一方向性関数の存在性は証明されていない。 （一方向性関数の存在性が示せれば、P≠NP が系として従う）。 しかし、一方向性関数の候補となる関数はいくつか知られている。 一方向性関数が存在すると証明が与えられたわけではないものの、 暗号理論では一方向性関数の存在性を仮定して議論を進める。 I を Σ* の部分集合とし、 D = {Dn}n ∈ I、R ={Rn}n ∈ I を Σ* の 部分集合の族とする。 G1、G2 を多項式時間アルゴリズムとし、 F = {fk: Dk → Rk} を関数の族とする。 組 (D, R, G1, G2, F) が以下を満たすとき、(D, R, G1, G2, F) を一方向性関数族という： G1 は 1k を入力すると n ∈ I∩Σk を出力するアルゴリズム。 G2 は n ∈ I を入力すると x ∈ Dn を出力するアルゴリズム。 ある

[htnhtn15]

一方向性関数