一方向性関数 - Summer498 の頭ん中

一方向性関数

関数値は容易に計算できるが逆関数の計算は非常に困難である関数を指す。暗号理論などで用いられる概念

逆関数? 一対一対応なの?

暗号論的ハッシュ関数のことを考えると多対一でも良さげ

多を 1 つのタプルにまとめれば一対一になるからどうでもいいかもしれない

下では、単に「多項式時間アルゴリズム」と書いたら「平均多項式時間確率アルゴリズム」を指す。

厳密な定義

$ \Sigma=\{0,1\}とし、$ \Sigma^*=\bigcup_{k\in\N}\Sigma^kとする

関数$ f:\Sigma^*\rightarrow\Sigma^*が以下を満たす時、関数$ fは一方向性関数であるという:

1. $ fは多項式時間で計算可能。

ある多項式時間アルゴリズム$ Cがあって$ C(x)=f(x)

2. 任意の多項式時間アルゴリズム$ Aに対し、ある無視可能関数$ \nuと、ある$ k_0\in\Nが存在して、任意の$ k>k_0に対して

$ {\rm Pr}\left[x\leftarrow_R\Sigma^k,y\leftarrow f(x), x'\leftarrow A(1^k,y):y=f(x')\right]\le\nu(l)