一方向性関数のソースを表示

'''一方向性関数'''（いちほうこうせいかんすう, one-way function）とは、簡単に計算できるが[[逆関数]]の計算は非常に困難である[[関数 (数学)|関数]]を指す。暗号理論などで用いられる概念である。[[素因数分解]]問題の困難性を用いたものが代表的。
以下特に断りがなければ、単に「多項式時間アルゴリズム」といったら平均多項式時間確率アルゴリズムを指すものとする。

==厳密な定義==
<math>{\Bbb N}</math> で自然数の集合を表す。
&Sigma; = {0, 1} とし、<math>\Sigma^* = \cup_{k\in{\Bbb N}}\Sigma^k</math>とする。

関数 <math>f : \Sigma^* \to \Sigma^*</math> が以下を満たす時、関数 ''f'' は'''一方向性関数'''であるという：

# ''f'' は[[多項式時間]]で計算可能。すなわちある多項式時間アルゴリズム ''C'' があって ''C''(''x'') = ''f''(''x'')
# 任意の多項式時間アルゴリズム ''A'' に対し、ある [[negligible]] な関数 &nu; とある <math>k_0 \in {\Bbb N}</math> が存在して、全ての ''k'' &gt; ''k''<sub>''0''</sub> に対し、
#:<math>Pr[x \gets_R \Sigma^k, y \gets f(x),x' \gets A(1^k, y) : y=f(x')] \le \nu(l) .</math>

==一方向性関数の存在性==

現在のところ、一方向性関数の存在性は証明されていない。
（一方向性関数の存在性が示せれば、[[P≠NP予想|P≠NP]] が系として従う）。
しかし、一方向性関数の候補となる関数はいくつか知られている。
一方向性関数が存在すると証明が与えられたわけではないものの、
暗号理論では一方向性関数の存在性を仮定して議論を進める。

==一方向性関数族==
''I'' を &Sigma;<sup>*</sup> の部分集合とし、

''D'' = {''D''<sub>''n''</sub>}<sub>''n'' &isin; ''I''</sub>、''R'' ={''R''<sub>''n''</sub>}<sub>''n'' &isin; ''I''</sub> を &Sigma;<sup>*</sup> の

部分集合の族とする。
''G''<sub>1</sub>、''G''<sub>2</sub> を多項式時間アルゴリズムとし、
''F'' = {''f''<sub>''k''</sub>: ''D''<sub>''k''</sub> &rarr; ''R''<sub>''k''</sub>} を関数の族とする。
組 (''D'', ''R'', ''G''<sub>1</sub>, ''G''<sub>2</sub>, ''F'') が以下を満たすとき、(''D'', ''R'', ''G''<sub>1</sub>, ''G''<sub>2</sub>, ''F'') を'''一方向性関数族'''という：
# ''G''<sub>1</sub> は 1<sup>''k''</sup> を入力すると ''n'' &isin; ''I''&cap;&Sigma;<sup>''k''</sup> を出力するアルゴリズム。
# ''G''<sub>2</sub> は ''n'' &isin; ''I'' を入力すると ''x'' &isin; ''D''<sub>''n''</sub> を出力するアルゴリズム。
# ある多項式時間アルゴリズム ''C'' があって ''C''(''x'', ''n'') = ''f''<sub>''n''</sub>(''x'')。
# 任意の多項式時間アルゴリズム ''A'' に対し、ある negligible な関数 &nu; とある ''k''<sub>0</sub> &isin; <math>{\Bbb N}</math> が存在して、全ての ''k'' &gt; ''k''<sub>0</sub> に対し、Pr[''x'' &larr; ''A''(''n'', ''y'') | ''n'' &larr; ''G''<sub>1</sub>(1<sup>''k''</sup>), ''x'' &larr; ''G''<sub>2</sub>(''n''), ''y'' &larr; ''f''(''x'')] &lt; &nu;(''l'')。

一方向性関数が存在する事は一方向性関数族が存在する事の必要十分条件である事が知られている。

==弱一方向性関数==
関数 ''f'': &Sigma;<sup>*</sup> &rarr; &Sigma;<sup>*</sup> が以下を満たす時、関数 ''f'' は'''弱一方向性関数'''であるという：

# ''f'' は[[多項式時間]]で計算可能。
# ある多項式 ''P'' が存在し、任意の多項式時間アルゴリズム ''A'' に対し、ある ''k''<sub>0</sub> が存在し、全ての ''k''<sub>0</sub> &gt; 0 に対し、Pr[''z''≠''f''(''x'') | ''x'' &larr;<sub>''R''</sub> &Sigma;<sup>''k''</sup>, ''y'' &larr; ''f''(''x''), ''z'' &larr; ''A''(1<sup>''k''</sup>, ''y'')] &gt; 1/''P''(''k'')。

'''定理'''　一方向性関数が存在する必要十分条件は弱一方向性関数が存在する事である。

'''証明の概略'''（&rArr;）自明。

（&lArr;）''f'' を弱一方向性関数とする。''g'' を ''g''(''x''<sub>1</sub> || &hellip; || ''x''<sub>''N''</sub>) = ''f''(''x''<sub>1</sub>) || &hellip; || ''f''(''x''<sub>''N''</sub>) と定義する。ただしここで「||」はビット列の連接、''N'' = 2''kP''(''k'')。（''P'' は弱一方向性関数の定義の条件 2 にあるもの）。
この時 ''g''<sup>-1</sup> を求めるには、''f''<sup> -1</sup> を ''N'' 回計算しなければならない。

どのようなアルゴリズムを用いても ''f''<sup> -1</sup> を計算するには 1/''P''(''k'') ステップかかるので、''f''<sup> -1</sup> を ''N'' 回計算するのは多項式時間ではできない。□

==非一様一方向性関数==
関数 ''f'': &Sigma;<sup>*</sup> &rarr; &Sigma;<sup>*</sup> が以下を満たす時、関数 ''f'' は''' non uniform な一方向性関数'''であるという：

# ''f'' は[[多項式時間]]で計算可能。
# 任意の多項式時間サイズの回路族 ''A'' = {''A''<sub>''k''</sub>} に対し、ある[[無視可能函数]] &nu; が存在して、Pr[''x'' &larr; ''A''<sub>''k''</sub>(''y'') |  ''x'' &larr;<sub>''R''</sub> &Sigma;<sup>''k''</sup>, ''y'' &larr; ''f''(''x'')] &lt; &nu;(''l'')。

多項式時間アルゴリズムは多項式時間サイズの回路族で表す事ができるので、non uniform な一方向性関数は必ず一方向性関数である。しかし逆はよく分かっていない。

==一方向性関数の候補==

集合 {(''p'', ''q'') &isin; <math>{\Bbb N}</math><sup>2</sup> | ''p'', ''q'' は素数で、''p'' のビット数 = ''q'' のビット数} から自然数の集合 <math>{\Bbb N}</math>への写像 (''p'', ''q'') <math>\mapsto</math> ''pq'' は一方向性関数であると予想されている。

==必要十分条件==

以下は全て同値である。
# 一方向性関数が存在する
# 弱一方向性関数が存在する
# 一方向性関数族が存在する
# [[暗号論的擬似乱数生成器]]が存在する
# [[擬似ランダム関数]]の族が存在する。
# [[電子署名]]方式が存在する。

==関連項目==
* [[暗号学的ハッシュ関数]]
* [[素因数分解]]
* [[離散対数]]

{{DEFAULTSORT:いちほうこうせいかんすう}}
[[Category:暗号技術]]
[[Category:関数]]
[[Category:数学に関する記事]]