一方向関数(one-way function)とは、決定的な多項式時間で計算できるが、一様に選んだ入力の値からその逆像の 1 つを求めることには、どの確率的な多項式時間の算法も無視できる確率でしか成功しない関数である。素数の積や法 $p$ の冪が候補とされるが、存在は証明されていない。存在すれば、逆像を 1 ビットずつ探す論法により $\mathrm{P}\ne\mathrm{NP}$ が従う。擬似乱数生成器の存在と同値であり、1 回限りの署名などの暗号の道具の安全性の基礎となる仮定として使われる。
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 つが成り立つことをいう。
逆算者は、元の $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)。
使える条件:
次の関数は一方向関数であると予想されているが、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}$ である。
証明の考え方は、「$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完全性が最悪の場合の難しさを扱うのに対し、暗号には大部分の入力での難しさが要ることを挙げている。
同じ論法で、乱数を使う判定でも結論が強められる。
一方向関数が存在すれば $\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 回だけ署名する Lamport の方式を述べる(BS23 §14.1、Theorem 14.1、p. 584)。
$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$ の正しい署名を出せれば成功とする。
確率的な多項式時間の偽造者 $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):
乱択自己帰着(prop-owf-selfred):
使う公式: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}$ 年である。総当たりは常に可能なので、一方向関数は「多項式時間では」逆算できないことを要求する。
使う公式: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アソシエイト)の紹介料で運営されています。 支援について / 寄付する