関数の平均時困難性と分布の識別不可能性

1. 関数の平均時困難性

平均時計算量の理論ではランダムな入力に対する問題の計算複雑性を議論します. 具体的には, 関数$f\colon\{0,1\}^k\to\{0,1\}$が任意のサイズ$s$の回路$C$に対して

\begin{align*}
\Pr_{x\sim\{0,1\}^k}[C(x)=f(x)]\leq 1-\delta
\end{align*}

を満たすとき, $f$はサイズ$s$に対して$\delta$-困難であるといいます. つまり効率的に$f(x)$を計算できる入力$x$の量によってその問題$f$の複雑性を評価します (回路の代わりに効率的なアルゴリズムを考えても似たような定義を与えることができます). 回路$C$が正解する入力の割合を成功確率と呼ぶことにします. すなわち$C$の$f$に対する成功確率は$$\Pr_{x\sim\{0,1\}^k}[C(x)=f(x)]$$

で与えられます.

$f$がBoolean関数ならば, 「常に$0$を出力する回路」もしくは「常に$1$を出力する回路」の少なくとも一方は成功確率$1/2$以上になります. 従って関数$f$は$\delta$-困難であるといった場合は基本的には$\delta\leq 1/2$を仮定し, $\delta$が$1/2$に近いほど$f$の困難性は強いということになります. 

コメント.

非常に細かいことですが, 入力長ごとに「常に0を出力すべきか」「常に1を出力すべきか」が変わりうるので, 決定的アルゴリズムを用いて困難性を定義した場合は$\delta\leq 1/2$は一般には言えません. このように入力長ごとに違うアルゴリズムを採用する場合は非一様モデル(=回路)で議論した方が良いと思います (一概には言えませんが).

2. 分布の識別不可能性

2.1. 統計的な識別不可能性

一方で, 平均時計算量の理論では分布のランダムっぽさ(擬似ランダム性)が計算量の概念を使って定義されています.

 確率論や機械学習などの文脈では分布の近さを統計距離(total variation distance)で評価し, 一様分布に近い分布を「ランダムっぽい」分布とみなすことができます. この文脈でいうと, 「分布$D$はランダムっぽい」という主張は(統計距離の定義に基づいて考えると)「分布$D$と一様分布を識別できる事象は存在しない」ことを意味します. もう少しフォーマルに述べます. 分布$D$を有限集合$\Omega$上の分布だと仮定します. ある関数$E\colon\Omega\to\{0,1\}$が存在して

\begin{align*}
|\mathbf{E}_{x\sim D}[E(x)] - \mathbf{E}_{x\sim \Omega}[E(x)]| > \epsilon
\end{align*}

を満たすとき, 分布$D$は一様分布から(統計距離の意味で)$\epsilon$だけ離れているといいます (ここで$x\sim\Omega$は$x$が$\Omega$上の一様分布に従って選ばれることを意味する). 従って, 関数$E$を使って$D$を一様分布から$\epsilon$のアドバンテージで識別することができます. このことを統計的に識別できるといいます. 逆に, そのような$E$が存在しないとき, 分布$D$はいかなる事象でも一様分布と区別がつきません.

2.2. 識別不可能性の恩恵: 暗号

あるメッセージを暗号化して送信するとしましょう. 暗号化された文は敵対者に対してその内容がわからないようになっている必要があります. 文の構造に何かしらの特徴があるとそこから何かしらの情報が引き出されてしまうため, 暗号文は何も特徴を持たないものであることが望ましいです. もしも暗号文は敵対者にとって「ランダム文字列」と識別できないという性質を持つならばこの課題はクリアされます (完全にランダムな文字列からは長さ意外の情報を何も抜き出せないいため). 例えば長さ$n$の文字列$x\in\{0,1\}^n$に対して, 長さ$n$の一様ランダムな文字列$r\in\{0,1\}^n$を生成して$x\oplus r$を暗号文としてみましょう ($x\oplus r$は各ビットごとにXORをとって得られる文字列). $r$が一様ランダムなので$x\oplus r$も一様ランダムとなり, もし敵対者が$r$を知らないとするとこの暗号化は条件をクリアしています.

しかし受信者は$n$ビットの文字列$r$をあらかじめ知っている必要があり, そもそも$r$を敵対者に知られずに共有できるならば$x$そのものを共有すれば良いことになるので, この手法は用途が非常に限られてしまいます. 実は, 統計距離を用いた識別不可能性を満たす暗号を構成するにはメッセージと同じ長さのランダムネスが必要となることが知られており, この問題点は解消できません.

2.3. 計算論的な識別不可能性

このような統計距離に基づく識別不可能性の現実味を削ぐ要因の一つには, 任意の識別者(=関数$E$)を考えるという点にあります. 実際には, 敵対者の計算能力は無限ではない(例えば多項式時間アルゴリズム)を想定すれば良いです. 従って分布の識別可能性を

ある効率的に計算できる関数$E\colon\Omega\to\{0,1\}$が存在して

\begin{align*}
|\mathbf{E}_{x\sim D}[E(x)] - \mathbf{E}_{x\sim \Omega}[E(x)]| > \epsilon
\end{align*}

によって定義すれば異なる結果が期待されます. このことを計算論的に識別できるといい, 計算論的に一様分布と区別できない分布を擬似ランダムであるといいます.

もう少しフォーマルに述べるしょう. 空間として$\Omega=\{0,1\}^k$を考え, $\{0,1\}^k$上の一様分布に従って選ばれた確率変数を$U_k$とします. 分布$D$と回路$C\colon\{0,1\}^k\to\{0,1\}$が

\begin{align*}|\mathbf{E}[C(D)-C(U_k)]|>\epsilon\end{align*}

を満たすとき, $C$はアドバンテージ$\epsilon$で$D$と$U_k$を識別するといいます. また, そのような回路であってサイズ$s$であるものが存在しないとき, $D$はサイズ$s$に対して$\epsilon$-擬似ランダムであるといいます.

3. 平均時困難性と識別不可能性の関係

統計的な識別不可能性から計算論的な識別不可能性への転換は, 本質的には敵対者(=識別者$E$)の範囲を限定するということに他なりません. しかしながらこの単純な転換が実に多くの(この記事に書ききれないほど)非自明な定理を生み出します.

実はこの両者の概念はBoolean関数においてはある意味で等価であるという結果が知られており, 今回はYaoのnext-bit predictorと呼ばれる結果を紹介します.

定理 ([Yao, 1982]).

関数$f\colon \{0,1\}^k\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon)$-困難であるとする. このとき, $z=U_k$に対して分布$(z,f(z))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダムである.

コメント1. 逆方向 ($(z,f(z))$が擬似ランダムならば$f$は$(1/2-\epsilon)$-困難)は簡単に示せます. 実際, $f$を成功確率$1/2+\epsilon$で計算するサイズ$s$の回路を$C$とすると, 「与えられた入力$(z,b)$に対して$b\oplus f(z)$を出力する回路を考えれば$(z,b)=(z,f(z))$か$(z,b)=(z,U_1)$かどうかを$\epsilon$のアドバンテージで識別することができます.

コメント2. 興味深いことに, 関数$G\colon z\mapsto (z,f(z))$を考えると, 定理よりこの関数はランダムな$k$ビットを受け取り, 擬似ランダムな$k+1$ビットを返す関数になっています. このように, 短いランダム文字列を受け取り長い擬似ランダム文字列を返す関数を擬似乱数生成器といいます (フォーマルな定義は本記事では割愛). これは統計的な識別不可能性に基づく枠組みでは不可能です. 実際, $G$は決定的な関数なので$G(z)$のランダムネス(=エントロピー)は高々$k$ビットであり, 統計的な意味ではランダムネスを増やすことはできないからです. 計算論的な識別不可能性を考えるとある意味で「エントロピーを増やす」ことができるのが重要な利点であり, 乱択アルゴリズムの脱乱択化や弱い仮定に基づく安全な暗号プリミティブの構成に応用されています. 再度述べますが, 敵対者を効率的なアルゴリズムに限定したからこそこのようなことが可能になっているのです.

定理の証明.

対偶を示します. $(z,f(z))$と$U_{k+1}$をアドバンテージ$\epsilon$で識別するサイズ$s'$の回路を$C\colon\{0,1\}^{k+1}\to\{0,1\}$とします. 識別するので

\begin{align*}
\mathbf{E}_{z,U_1}[C(z,f(z))-C(z,U_1)] > \epsilon
\end{align*}

です (必要があれば出力ビットを反転することにより絶対値を外すことができます). 特に$U_1$は$z$とは独立な確率変数なので, 確率$1/2$で$U_1=f(z)$になったときは差が$0$になります. 従って上式を書き換えると

\begin{align*}
\mathbf{E}_z[C(z,f(z))] - \mathbf{E}_z[C(z,\overline{f(z)})] > 2\epsilon
\end{align*}

を得ます ($\overline{b}=1\oplus b$はビットの反転).

回路$P(z,r)$を$P(z,r)=C(z,r)\oplus r \oplus 1$とすると, 以下で示すように$\Pr_{z,r\sim U_1}[P(z,r)=f(z)]> 1/2+\epsilon$を得ます. これを得ると$P(z,0)$と$P(z,1)$の少なくとも一方が$f$を成功確率$>1/2+\epsilon$で計算するサイズ$s'+O(1)$の回路になっており, 証明が完了します.

$r\sim U_1$より, 確率$1/2$で$r=f(z)$となります. したがって

\begin{align*}
\Pr_{z,r}[P(z,r)=f(z)] &= \mathbf{E}_{z,r}[P(z,r)\oplus f(z)\oplus 1] \\
&= \mathbf{E}_{z,r}[C(z,r)\oplus r \oplus f(z)] \\
&= \frac{1}{2}\mathbf{E}_z[C(z,f(z))] + \frac{1}{2}\mathbf{E}_z[1-D(z,\overline{f(z)})] \\
&> \frac{1}{2}+\epsilon
\end{align*}

を得ます (3番目の等式では$r=f(z)$と$r=\overline{f(z)}$の場合分けを行っています).

(証明終)