一方向関数

同義語:one-way function一方向置換one-way permutation一方向性関数

概要

一方向関数(one-way function)とは、決定的な多項式時間で計算できるが、一様に選んだ入力の値からその逆像の 1 つを求めることには、どの確率的な多項式時間の算法も無視できる確率でしか成功しない関数である。素数の積や法 $p$ の冪が候補とされるが、存在は証明されていない。存在すれば、逆像を 1 ビットずつ探す論法により $\mathrm{P}\ne\mathrm{NP}$ が従う。擬似乱数生成器の存在と同値であり、1 回限りの署名などの暗号の道具の安全性の基礎となる仮定として使われる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: P対NP問題, 確率的アルゴリズム

2 つの素数を掛けるのは易しいが、積から元の素数を求める 素因数分解 には、AB07(2007 年の版)の時点で知られている最良の方法でも、桁数 $n$ について $2^{O(n^{1/3})}$ 程度の時間がかかる(AB07 Example 10.2、p. 189。この評価自体も数論の未証明の予想に依存する)。$g^x\bmod p$ の計算と、その逆の 離散対数 も同じ関係にある。一方向関数(one-way function)は、この「計算は易しいが、逆はほとんどの入力で難しい」という性質を、多項式時間の算法の言葉で定義したものである。
一方向関数は現代の暗号理論の最も基本的な仮定である。擬似乱数生成器、1 回限りの署名、ゼロ知識証明 に使う約束の方式などは、一方向関数の存在から作れる。一方で、一方向関数が存在するかどうかは分かっていない。存在すれば $\mathrm{P}\ne\mathrm{NP}$ が従うからである。この記事では定義を述べ、一方向関数の存在から $\mathrm{P}\ne\mathrm{NP}$ が従うことを完全に証明する。さらに、弱い一方向関数との違い、離散対数の難しさが最悪の場合から平均の場合へ移ること、一方向関数から作る 1 回限りの署名を証明つきで述べる。

定義

以下、$\{0,1\}^n$ は長さ $n$ の 0 と 1 の列の集合、$U_n$ は $\{0,1\}^n$ 上の一様分布に従う確率変数である。算法は乱数を使ってよく、時間が入力の長さの多項式でおさえられるものを 確率的な多項式時間の算法 という(確率的アルゴリズム)。$1^n$ は $1$ を $n$ 個並べた列で、算法に長さの目安 $n$ を知らせるために入力に添える。

無視できる関数

関数 $\varepsilon\colon\mathbb N\to[0,1]$ が 無視できる とは、どの正の整数 $c$ についても、十分大きなすべての $n$ で $\varepsilon(n)< n^{-c}$ となることをいう。

$2^{-n}$ や $n^{-\log n}$ は無視できるが、$n^{-10}$ や $\frac12$ は無視できない。無視できる関数に多項式を掛けたものも無視できる。

一方向関数

写像 $f\colon\{0,1\}^*\to\{0,1\}^*$ を考え、各 $n$ について $f$ を $\{0,1\}^n$ に制限したものを $f_n$ とする。$f$ が 一方向関数 であるとは、次の 2 つが成り立つことをいう。

  1. 計算が易しい:$f$ は決定的な多項式時間の算法で計算できる。
  2. 逆が難しい:どの確率的な多項式時間の算法 $I$(逆算者)についても、
    $$ \mathrm{Inv}_I(n):=\Pr\bigl[\,I(1^n,f(X))\in f_n^{-1}(f(X))\,\bigr],\qquad X\sim U_n $$
    は $n$ の関数として無視できる。確率は $X$ と $I$ の乱数についてとる。
    $f$ が各 $\{0,1\}^n$ の全単射でもあるとき、一方向置換 という。

逆算者は、元の $X$ を当てる必要はなく、$f(X)$ の逆像のどれか 1 つ(長さ $n$ の列)を出せば成功とする。これは AB07 Definition 10.1(p. 189)で、$\varepsilon(n)$ を無視できる関数、逆算者の時間を多項式としたものにあたる。

弱い一方向関数

def-owf-def の 1 を満たす $f$ が 弱い一方向関数 であるとは、ある多項式 $q$ があって、どの確率的な多項式時間の逆算者 $I$ についても、十分大きなすべての $n$ で $1-\mathrm{Inv}_I(n)\ge\frac1{q(n)}$ となることをいう。def-owf-def の意味の一方向関数を、区別するときは 強い一方向関数 という。

強い一方向関数は弱い一方向関数である($1-\mathrm{Inv}_I(n)\ge\frac12$ が十分大きな $n$ で成り立つ)。弱い一方向関数は、逆算できない入力の割合が多項式分の 1 以上あることだけを要求する(AB07 §10.1.1、p. 190)。
使える条件:

  • (i) 逆算者の時間は入力の長さの多項式で、入力には $1^n$ が添えられる。
  • (ii) 難しさは $X$ が一様に選ばれたときの確率で測る(平均の場合の難しさ)。最悪の入力で難しいだけでは足りない。
  • (iii) 逆像のどれか 1 つを出せば逆算の成功とする。
  • (iv) 成功の確率は無視できる(強い)か、失敗の確率が多項式分の 1 以上(弱い)かを区別する。

一方向関数の候補

次の関数は一方向関数であると予想されているが、AB07(2007 年の版)の時点で、どれも一方向であることは証明されていない。それぞれの逆の問題が平均の場合に難しいという仮定に基づく(AB07 Examples 10.2–10.4、pp. 189–190)。

候補写像逆の問題備考
掛け算$(x,y)\mapsto x\cdot y$($n$ ビットの整数)素因数分解$x,y$ がともに素数である入力は多項式分の 1 程度で、弱い一方向関数の候補
素数の積乱数から $n$ ビットの素数 $p,q$ を作り $pq$ を出す素因数分解ほとんどすべての入力で逆が難しいと予想される
法 $p$ の冪$x\mapsto g^x\bmod p$($g$ は原始根)離散対数置換。prop-owf-selfred
RSA 関数$x\mapsto x^e\bmod N$($N=pq$)$e$ 乗根RSA暗号 で使う
部分和$(a_1,\dots,a_n,S)\mapsto(a_1,\dots,a_n,\sum_{i\in S}a_i)$部分和問題

主定理:一方向関数が存在すれば $\mathrm{P}\ne\mathrm{NP}$

一方向関数と P 対 NP 問題

一方向関数が存在すれば $\mathrm{P}\ne\mathrm{NP}$ である。

証明の考え方は、「$f(wu)=y$ となる続き $u$ があるか」という問いが NP に属することである。$\mathrm{P}=\mathrm{NP}$ ならこの問いが多項式時間で答えられ、逆像を先頭から 1 ビットずつ決めていける。

対偶を示す。$\mathrm{P}=\mathrm{NP}$ と仮定し、$f$ を def-owf-def の 1 を満たす任意の写像とする。$f$ が一方向関数でないこと、すなわち成功の確率が無視できない逆算者があることを示す。
$f$ は多項式 $t$ の時間で計算できるとする。とくに $\lvert f(x)\rvert\le t(\lvert x\rvert)$ である。3 つ組 $(1^n,y,w)$($w$ は長さ $n$ 以下の列)を適当に符号化した列の言語
$$ L_f:=\bigl\{(1^n,y,w)\ :\ f(wu)=y\text{ となる }u\in\{0,1\}^{n-\lvert w\rvert}\text{ がある}\bigr\} $$
を考える。$L_f$ は NP に属する。実際、証明書を $u$ とすれば、その長さは $n$ 以下で入力の長さ以下であり、$f(wu)$ を時間 $t(n)$ で計算して $y$ と比べればよい。仮定から $L_f\in\mathrm P$ であり、$L_f$ を判定する決定的な多項式時間の算法 $D$ がある。
逆算者 $I$ を次のように定める。入力 $(1^n,y)$ に対し、$w$ を空列から始め、$i=1,\dots,n$ の順に、$D(1^n,y,w0)=1$ なら $w:=w0$、そうでなければ $w:=w1$ とする。最後の $w$(長さ $n$)を出力する。
$y\in f(\{0,1\}^n)$ のとき $I(1^n,y)$ が $y$ の逆像であることを示す。「$(1^n,y,w)\in L_f$」が各段の後で成り立つことを $i$ についての帰納法で示す。始めは $w$ が空列で、$y$ が $f_n$ の像に入ることがそのまま $(1^n,y,w)\in L_f$ である。ある段の前で $(1^n,y,w)\in L_f$ とし、$f(wu)=y$ となる $u$ をとる。$D(1^n,y,w0)=1$ なら $(1^n,y,w0)\in L_f$ である。そうでなければ $u$ の先頭は $0$ でありえない($0$ なら $(1^n,y,w0)\in L_f$ となる)ので $1$ であり、$(1^n,y,w1)\in L_f$ である。$n$ 段の後 $w$ の長さは $n$ で、$(1^n,y,w)\in L_f$ は $f(w)=y$ を意味する。
$I$ は $D$ を $n$ 回呼ぶだけなので多項式時間である。$X\sim U_n$ のとき $y=f(X)$ は $f_n$ の像に入るので、$\mathrm{Inv}_I(n)=1$ である。$1$ は無視できないので、$f$ は一方向関数でない。$f$ は任意だったので、一方向関数は存在しない。$\square$

逆は分かっていない。$\mathrm{P}\ne\mathrm{NP}$ は、NP の問題に多項式時間で解けない入力が「どこかにある」ことしか言わず、逆算がほとんどの入力で難しいことは言わない。AB07 の第 10 章の冒頭(p. 187)は、NP完全問題の難しさから暗号の安全性を導く試みはその時点で成功していないと述べ、その理由として、NP完全性が最悪の場合の難しさを扱うのに対し、暗号には大部分の入力での難しさが要ることを挙げている。
同じ論法で、乱数を使う判定でも結論が強められる。

一方向関数と BPP

一方向関数が存在すれば $\mathrm{NP}\not\subset\mathrm{BPP}$ である。ここで BPP は、どの入力でも確率 $\frac23$ 以上で正しく答える確率的な多項式時間の算法で判定できる言語のクラスである(確率的アルゴリズム)。

証明を開く

$\mathrm{NP}\subset\mathrm{BPP}$ とし、prf-thm-owf-pnp の $L_f$ が BPP に属するとする。同じ算法を独立に何回も走らせて多数決をとると、誤りの確率を入力の長さ $N$ について $2^{-N}$ 以下にできる(AB07 Theorem 7.10、p. 122)。この算法 $D'$ を $D$ の代わりに使うと、入力 $(1^n,y,w)$ の長さは $n$ 以上なので、$n$ 回の呼び出しのどれかが誤る確率は $n2^{-n}$ 以下である。すべて正しければ prf-thm-owf-pnp と同じく逆像が得られるので、$\mathrm{Inv}_I(n)\ge1-n2^{-n}$ であり、これは無視できない。$\square$

弱い一方向関数と強い一方向関数

弱いが強くない一方向関数

$f$ を一方向関数とし、長さ $n+1$ の列 $bx'$($b\in\{0,1\}$、$x'\in\{0,1\}^n$)について
$$ g(0x'):=0x',\qquad g(1x'):=1f(x') $$
とおく。$g$ は弱い一方向関数であるが、強い一方向関数ではない。

証明を開く

$g$ は多項式時間で計算できる。$I(1^{n+1},z):=z$ とする逆算者は、先頭が $0$ の入力(確率 $\frac12$)では $g(z)=z$ なので成功する。よって $\mathrm{Inv}_I(n+1)\ge\frac12$ で、$g$ は強い一方向関数でない。

任意の確率的な多項式時間の逆算者 $I$ をとる。$g$ の値で先頭が $1$ のものの逆像は、先頭が $1$ で $1u$($f(u)=$ 残りの部分)の形をしている。$f$ の逆算者 $I'$ を、入力 $(1^n,y)$ に対し $I(1^{n+1},1y)$ を計算し、その先頭を除いた長さ $n$ の列を出すものとする。$I(1^{n+1},1y)$ が $1y$ の逆像なら、$I'$ は $y$ の逆像を出す。よって、先頭が $1$ の入力での $I$ の成功の確率は $\mathrm{Inv}_{I'}(n)$ 以下で、$\mathrm{Inv}_I(n+1)\le\frac12+\frac12\mathrm{Inv}_{I'}(n)$ である。$\mathrm{Inv}_{I'}$ は無視できるので、十分大きな $n$ で $1-\mathrm{Inv}_I(n+1)\ge\frac12-\frac12\mathrm{Inv}_{I'}(n)\ge\frac13$ である。多項式 $q:=3$ で def-owf-weak を満たす。$\square$

逆向きに、弱い一方向関数 $f$ があれば、多数の独立な入力に $f$ を並べて適用した $(x_1,\dots,x_m)\mapsto(f(x_1),\dots,f(x_m))$ が($m$ を $n$ の適当な多項式にとると)強い一方向関数になることが Yao によって示されている(AB07 §10.1.1、p. 190 にこの主張がある。同書は第 17 章でこれに近い主張を示すとしている。この記事では証明しない)。したがって、一方向関数の存在を問うときは強弱を区別しなくてよい。

最悪の場合から平均の場合へ

def-owf-def は平均の場合の難しさを要求する。離散対数では、ある程度の割合の入力で解ければすべての入力で解けるので、最悪の場合の難しさから平均の場合の難しさが出る。このような性質を 乱択自己帰着性 という。

離散対数の乱択自己帰着

$p$ を素数、$g$ を法 $p$ の原始根とする。決定的な算法 $A$ が、$x\in\{0,1,\dots,p-2\}$ のうち割合 $\varepsilon>0$ のものについて、$g^x\bmod p$ から $x$ を正しく求めるとする。このとき、どの $y\in\{1,\dots,p-1\}$ についても、$A$ を $k$ 回呼んで確率 $1-(1-\varepsilon)^k$ 以上で $y$ の離散対数を求める確率的な算法がある。とくに $k=\lceil\varepsilon^{-1}\ln\delta^{-1}\rceil$ 回で失敗の確率は $\delta$ 以下である(AB07 Theorem 10.5、p. 191)。

各回、$r\in\{0,\dots,p-2\}$ を一様に選び、$y':=y\,g^r\bmod p$ を $A$ に渡す。答え $z$ について $g^{z}\equiv y'$ を確かめ、成り立てば $x:=z-r\bmod(p-1)$ を出力して止める。
$y\equiv g^{x_0}$ とすると $y'\equiv g^{x_0+r}$ である。$r\mapsto x_0+r\bmod(p-1)$ は $\{0,\dots,p-2\}$ の全単射なので、$y'$ の離散対数は一様に分布し、$A$ が正しく答える確率はちょうど $\varepsilon$ である。正しく答えれば $g^{z-r}\equiv y'g^{-r}\equiv y$ なので出力は $y$ の離散対数である。確かめの段で誤った答えは捨てられるので、誤った値を出力することはない。各回は独立なので、$k$ 回すべて失敗する確率は $(1-\varepsilon)^k\le e^{-\varepsilon k}$ であり、$k\ge\varepsilon^{-1}\ln\delta^{-1}$ なら $\delta$ 以下である。$\square$

応用:1 回限りの署名

一方向関数だけから作れる暗号の道具の最も簡単な例として、1 ビットの文書に 1 回だけ署名する Lamport の方式を述べる(BS23 §14.1、Theorem 14.1、p. 584)。

Lamport の 1 ビット署名

$f$ を一方向関数とする。署名者は $x_0,x_1\in\{0,1\}^n$ を独立に一様に選び、秘密の鍵を $(x_0,x_1)$、公開の鍵を $(y_0,y_1):=(f(x_0),f(x_1))$ とする。文書 $m\in\{0,1\}$ の署名は $x_m$ で、$\sigma$ が $m$ の署名として正しいとは $f(\sigma)=y_m$ となることである。偽造者 は、公開の鍵を受け取り、好きな $m$ を 1 つ選んでその署名 $x_m$ を受け取ったあと、もう一方の文書 $1-m$ の正しい署名を出せれば成功とする。

Lamport の署名の安全性

確率的な多項式時間の偽造者 $A$ の成功の確率を $\mathrm{Sig}_A(n)$ とすると、確率的な多項式時間の逆算者 $B$ で $\mathrm{Inv}_B(n)=\frac12\mathrm{Sig}_A(n)$ となるものがある。とくに $f$ が一方向関数なら $\mathrm{Sig}_A$ は無視できる。

証明を開く

$B$ は入力 $(1^n,y)$($y=f(X)$、$X\sim U_n$)に対し、ビット $b$ と $x'\in\{0,1\}^n$ を一様に選び、$y_b:=y$、$y_{1-b}:=f(x')$ として公開の鍵 $(y_0,y_1)$ を $A$ に渡す。$A$ が文書 $m$ を選んだとき、$m=1-b$ なら署名 $x'$ を渡し、$A$ が出した $\sigma$ を出力する。$m=b$ なら失敗とする。

$A$ が受け取る公開の鍵は、本物と同じく独立な 2 つの $f(U_n)$ であり、$b$ と独立である。よって $A$ が選ぶ $m$ と $b$ は独立で、$m=1-b$ となる確率は $\frac12$ である。$m=1-b$ のとき $A$ が見るものは本物の場合とまったく同じなので、$A$ が成功する条件付き確率は $\mathrm{Sig}_A(n)$ に等しい。$A$ が成功すれば $f(\sigma)=y_{1-m}=y_b=y$ なので $B$ は逆像を出す。以上から $\mathrm{Inv}_B(n)=\frac12\mathrm{Sig}_A(n)$ である。$\square$

$v$ ビットの文書には、この方式を $v$ 組並べればよい(BS23 §14.1、p. 584)。同じ鍵で 2 回署名すると $x_0,x_1$ の両方が知られてしまうので、1 回限りという条件は外せない(反例の表)。

公式の表

主張条件根拠
一方向関数がある $\Rightarrow\mathrm{P}\ne\mathrm{NP}$—thm-owf-pnp
一方向関数がある $\Rightarrow\mathrm{NP}\not\subset\mathrm{BPP}$—prop-owf-bpp
強い一方向 $\Rightarrow$ 弱い一方向—def-owf-weak の後
弱い一方向 $\not\Rightarrow$ 強い一方向(同じ関数で)一方向関数 $f$ があるprop-owf-weak
弱い一方向関数がある $\Rightarrow$ 強い一方向関数がある—証明しない(AB07 p. 190)
擬似乱数生成器 $\Rightarrow$ 一方向関数伸長 $\ge2n$擬似乱数生成器
一方向関数がある $\iff$ 擬似乱数生成器がある—証明しない(AB07 Theorem 10.13、p. 196)
離散対数:割合 $\varepsilon$ で解ける $\Rightarrow$ 全入力で解ける$k=\lceil\varepsilon^{-1}\ln\delta^{-1}\rceil$ 回prop-owf-selfred
一方向関数 $\Rightarrow$ 1 回限りの署名偽造の確率 $=2\times$ 逆算の確率prop-owf-lamport

計算の手順

判定の算法から逆算する(thm-owf-pnp):

  1. 問い「$f(wu)=y$ となる続き $u$ があるか」を判定する算法 $D$ を用意する。
  2. $w$ を空列とし、$i=1,\dots,n$ の順に $D(1^n,y,w0)$ を問い、答えが「ある」なら $w0$、「ない」なら $w1$ に延ばす。
  3. 長さ $n$ になった $w$ を出力する。$D$ を呼ぶのは $n$ 回である。

乱択自己帰着(prop-owf-selfred):

  1. 許す失敗の確率 $\delta$ と、$A$ の成功の割合 $\varepsilon$ から $k=\lceil\varepsilon^{-1}\ln\delta^{-1}\rceil$ を決める。
  2. 一様な $r$ を選び $y\,g^r\bmod p$ を $A$ に問う。答え $z$ が $g^z\equiv yg^r$ を満たせば $z-r\bmod(p-1)$ を出して止める。
  3. 満たさなければ 2 を繰り返し、$k$ 回で止める。

例題

探索による逆算

使う公式:thm-owf-pnp の手順。
問:$f(uv):=u\cdot v$($u,v$ は 3 ビットの 2 進で $0$ から $7$ の整数)、$y=35$ とする。判定の問いに答える算法があるとして、逆像を求めよ。
答え:$w0$ を問う 6 回の答えは順に「ない($u$ が $0$ から $3$ では $35/u$ は 7 以下の整数でない)」「ある($u=4,5$ のうち $5\cdot7$)」「ない($u=4$)」「ない」「ない」「ない」で、$w=101111$、すなわち $u=5$、$v=7$ を得る。$5\cdot7=35$ である。

離散対数と乱択自己帰着

使う公式:prop-owf-selfred。
問:$p=23$、$g=5$(原始根)とする。$A$ は $1\le y'\le11$ の $y'$ に対してだけ正しい対数を答えるとする($\varepsilon=\frac12$)。$y=19$ の対数を求めよ。
答え:$r=1$ とすると $y'=19\cdot5\bmod23=3$ で、$A$ は $z=16$($5^{16}\equiv3$)を答える。$x=16-1=15$ で、$5^{15}\equiv19\pmod{23}$ である。失敗の確率を $\delta=0.01$ 以下にするには $k=\lceil2\ln100\rceil=10$ 回で足り、実際の失敗の確率は $(\frac12)^{10}\approx0.000977$ である。

総当たりの手間

使う公式:def-owf-def。
問:入力が $n$ ビットの関数を、すべての入力を試して逆算する。1 秒に $10^{12}$ 回 $f$ を計算できるとき、$n=64$ と $n=128$ で最悪どれだけかかるか。
答え:$2^{64}\approx1.844674\times10^{19}$ 回で約 $213.5$ 日、$2^{128}\approx3.402824\times10^{38}$ 回で約 $1.078290\times10^{19}$ 年である。総当たりは常に可能なので、一方向関数は「多項式時間では」逆算できないことを要求する。

小さな Lamport の署名

使う公式:def-owf-lamport。
問:$f(x)=5^x\bmod23$ を使い、秘密の鍵 $(x_0,x_1)=(3,10)$ で文書 $m=1$ に署名し、検証せよ。
答え:公開の鍵は $(5^3,5^{10})\bmod23=(10,9)$ である。署名は $\sigma=x_1=10$ で、$5^{10}\equiv9=y_1$ なので正しい。この大きさの $f$ はすぐ逆算できるので、安全性は $p$ が十分大きいときの話である。

使える条件と反例

外す条件反例成り立たなくなること
(iii) 逆像のどれでもよい(元の $X$ を当てることを要求する)定数関数 $f(x)=0$元の $X$ を当てる確率は $2^{-n}$ で定義を満たしてしまうが、どの列も逆像で、逆は易しい。定義が「逆が難しい」を表さなくなり、thm-owf-pnp の証明(逆像を 1 つ探す)も元の $X$ を当てない
(i) 入力に $1^n$ を添える$f(x):=\lvert x\rvert$ の 2 進表記$1^n$ がないと逆算者は長さ約 $\log_2n$ の入力から長さ $n$ の列を書く必要があり、多項式時間では書けないので定義を満たしてしまう。どの長さ $n$ の列も逆像で、逆は易しい
(ii) 平均の場合の難しさ(最悪の場合だけにする)prop-owf-weak の $g$(一方向関数 $f$ があるとき)先頭が $1$ の入力は逆算が難しいが、半分の入力で $I(z)=z$ が成功する。最悪の場合には難しいのに、def-owf-def の 2 が満たされない
1 回限り(def-owf-lamport)同じ鍵で $m=0$ と $m=1$ の両方に署名する$x_0,x_1$ がともに知られ、どちらの文書の署名も偽造できる。prop-owf-lamport の結論が成り立たない

よくある誤り

誤り正しくはなぜ
$\mathrm{P}\ne\mathrm{NP}$ なら一方向関数がある逆向きの含意は分かっていないthm-owf-pnp の後。$\mathrm{P}\ne\mathrm{NP}$ は最悪の場合の難しさ
NP完全問題の逆なら一方向関数になる最悪の場合に難しくても、ほとんどの入力で易しいことがある使える条件 (ii)、AB07 p. 187
一方向関数は単射である単射でなくてよい。$f$ が一方向なら $(x,b)\mapsto f(x)$ も一方向(BS23 p. 337)def-owf-def は逆像のどれでも成功とする
逆算は元の $x$ を求めること逆像のどれか 1 つでよい反例の表の 1 行目
素因数分解が難しいことは証明されている予想であるAB07 p. 189
一方向関数があれば公開鍵暗号が作れるAB07 の時点で、一方向関数だけからの構成は知られていない(落とし戸などの構造を仮定する)AB07 p. 188

補足

一方向関数の存在は、擬似乱数生成器 の存在と同値である(AB07 Theorem 10.13、p. 196。一方向置換の場合の構成は 擬似乱数生成器 で述べる)。そこから共通鍵暗号や、ゼロ知識証明 に使う約束の方式が作れる。一方、公開鍵暗号 には、秘密の情報(落とし戸)を知っていれば逆算が易しくなる 落とし戸つき一方向関数 が使われる(AB07 Example 10.4、p. 190)。RSA暗号 の $x\mapsto x^e\bmod N$ は $N$ の素因数を知っていれば逆算できる。
thm-owf-pnp から、一方向関数の存在を証明することは $\mathrm{P}\ne\mathrm{NP}$ の証明を含む。そのため暗号理論では、一方向関数の存在や、素因数分解・離散対数の難しさを仮定として置き、そこから各方式の安全性を prop-owf-lamport のような帰着で示す。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する