hardcore補題を使ったXOR補題の証明

 平均時計算量においてはXOR補題と呼ばれる定理がよく知られています. この分野では脱乱択化や暗号プリミティブの構成への応用を念頭に, 非常に難しい関数をどのように構成するかが研究されています.

関数$f\colon\{0,1\}^n\to\{0,1\}$に対する回路$C$の成功確率$p_{C,f}$を

$$\begin{align*} p_{C,f}:= \Pr_{x\sim\{0,1\}^n}[C(x)=f(x)] \end{align*}$$

と定めます. ここで, 有限集合$S$に対して$x\sim S$で$x$は$S$上一様分布に選ばれたことを意味します. 任意のサイズ$s$の回路$C\colon\{0,1\}^n\to\{0,1\}$に対してその成功確率が高々$1-\delta$であるとき, 関数$f$はサイズ$s$に対して$\delta$-困難であるといいます. 定数回路(常に$0$を出力, または常に$1$を出力する回路)を使えば成功確率$\geq1/2$を達成するので, 基本的に$\delta\leq1/2$の範囲で考えます. 特に, 小さい$\epsilon>0$に対して$(1/2-\epsilon)$-困難な関数は正解できる入力の個数が下界に近いので非常に困難な関数であるとみなすことができます. XOR補題とは, XORをとることによって関数の困難性を増幅できることを主張する定理です.

定理1 (XOR補題)

関数$f$, パラメータ$k\in\mathbb{N}$に対して関数$f^{\oplus k}\colon \{0,1\}^{nk}\to\{0,1\}$を

$$\begin{align*} f^{\oplus k}(x_1,\dots,x_k)=f(x_1)\oplus \dots \oplus f(x_k) \end{align*}$$
で定める. $f$がサイズ$O\left(\frac{\log(1/\delta)}{(\epsilon/k)^2}(s+kn)\right)$に対して$\delta$-困難かつ$k\geq \frac{C\log(1/\epsilon)}{\delta^2}$ならば,$f^{\oplus k}$はサイズ$s$に対して$(1/2-\epsilon)$-困難である. ここで$C$は十分大きな定数である.

一般に, 「関数$f$がサイズ$s$に対して$\delta$-困難ならば関数$g$はサイズ$s'$に対して$(1/2-\epsilon)$-困難である」という形の定理を困難性の増幅(hardness amplification)といい, XOR補題はその最も基本的な定理の一つです. 原則として$s'\approx s$であることが望まれます.

本記事ではこの定理を証明します. そのためにhardcore lemmaを使います. 回路$C$の問題$f$に対する入力集合$H\subseteq\{0,1\}^n$上での成功確率を$p_{C,f,H}:=\Pr_{x\sim H}[C(x)=f(x)]$と定義します. ここでは[Impagliazzo (1995)]のパラメータを改善した[Barak, Hardt, Kale (2009)]による以下のhardcore lemmaを用いることにします:

補題1. (hardcore lemma)

サイズ$s$に対して$\delta$-困難な関数を任意にとってきて$f$とすると, ある$|H|\geq\delta 2^n$を満たす集合$H\subseteq \{0,1\}^n$であって, 任意のサイズ$O\left(\frac{\epsilon^2}{\log(1/\delta)}s\right)$の回路$C$に対して$p_{C,f,H}\leq 1/2-\epsilon$を満たすものが存在する.

補題1によって存在性が保証されている集合$H$を$f$のハードコア集合と呼びます. hardcore lemmaの対偶をとると以下の主張を得ます:

補題1'. (hardcore lemma)

任意の$|H|\geq \delta 2^n$を満たす集合$H\subseteq \{0,1\}^n$に対してあるサイズ$s$の回路$C_H$が存在して$\Pr_{x\sim H}[C_H(x) = f(x)]\geq 1/2+\epsilon$を満たすならば, あるサイズ$O\left(\frac{\log(1/\delta)}{\epsilon^2} \cdot s\right)$の回路$C'$が存在して, $\Pr_{x\sim\{0,1\}^n}[C'(x)=f(x)]\geq 1-\delta$.

関数$f\colon \{0,1\}^n\to\{0,1\}$が$\delta$-困難であるならば, 一様ランダムな$x\sim \{0,1\}^n$に対して確率変数$f(s)$は1ビットのベルヌーイ試行$\mathrm{Ber}(\delta)$と区別がつかないということを意味します. ここでベルヌーイ試行$\mathrm{Ber}(\theta)$とは確率$\theta$で$1$, 確率$1-\theta$で$0$を出力する確率変数です. 従って, ハードコア補題は, 直感的には,

$f$が$\delta$-困難ならば, サイズ$|H|\geq \delta$を満たすある入力集合$H\subseteq \{0,1\}^n$が存在して, 一様ランダムな$x\sim H$に対して$f(x)$は1ビットの一様分布$\mathrm{Ber}(1/2)$と(計算論的に)区別がつかない

ということを主張しています. では, 定理1を証明しましょう. まずはアウトラインを述べます. 独立に$x_1,\dots,x_k\sim\{0,1\}^n$をランダムにとって$f^{\oplus k}(x_1,\dots,x_k)$を考えてみましょう. まず, $x_1,\dots,x_k$のうち少なくとも一つが$H$に入っている確率は下から$1-(1-\delta)^k\approx 1-\mathrm{e}^{-\delta k}\approx 1-\epsilon$で抑えられます. 非常に高確率で発生するこの事象で条件つけ, 例えば$x_i\in H$であるとします. このとき, $x_i$の分布は$H$上で一様ランダムです. したがって$f(x_i)$は$\mathrm{Ber}(1/2)$と区別がつきません. ここで確率変数$f(x_1),\dots,f(x_k)$は$x_1,\dots,x_k$が独立なのでこれらもまた独立であり, $f(x_i)$が$\mathrm{Ber}(1/2)$と区別できないので, XORをとった$f^{\oplus k}(x_1,\dots,x_k)$もまた$\mathrm{Ber}(1/2)$と区別できないです (一様ランダムなビットと他のビットのXORをとったらそれもまた一様ランダムなビットになる). すなわち, $f^{\oplus k}(x_1,\dots,x_k)$が$\mathrm{Ber}(1/2)$と区別できず, これは$f^{\oplus k}(x_1,\dots,x_k)$が$(1/2-\epsilon)$-困難であることを意味します (事象の発生確率が$1-\epsilon$なので$\epsilon$程度のロスが発生している).

以上の流れを対偶を使って証明します. 以下, 二つの確率変数$X,Y$に対し, $X\not\approx_c Y$で$X$と$Y$をcomputationalに識別できる (i.e., ある小さい回路$C$が存在して$|\Pr[C(X)=1]-\Pr[C(Y)=1]|$がnon-negligibleに大きい) ことを表すとします. また, $X\approx_s Y$によって, $X$と$Y$はstatisticalの意味で近い (つまりtotal variation distanceが小さい)ことを表すとします. 最後に, $U_k$によって一様ランダムな$k$ビットの文字列を表すとします. 例えば$(U_{nk},f^{\oplus k}(U_{nk}))$と書いた場合は, $x\sim U_{nk}$を一様ランダムにサンプリングして$x=(x_1,\dots,x_k)$に$k$分割して$(x,f^{\oplus k}(x_1,\dots,x_k))$の分布のことを表すものとします (なので分布のランダムネスは$x$の選び方のみです).

1. $f^{\oplus k}(x_1,\dots,x_k)$を成功確率$(1/2+\epsilon)$で計算するサイズ$s$の回路が存在するので, $(U_{nk},f^{\oplus k}(U_{nk}))\not\approx_c (U_{nk},U_1)$.
2. ランダム関数$f_H(x)$を, $x\in H$ならば$f_H(x)=U_1$, $x\not\in H$ならば$f_H(x)=f(x)$と定義する. 情報論的なバウンドによって, $(U_{nk},f_H^{\oplus k}(U_{nk}))\approx_s (U_{nk},U_1)$.
3. 1と2の議論によって, $(U_{nk},f_H^{\oplus k}(U_{nk}))\approx_s U_{nk+1}\not \approx_c (U_{nk},f^{\oplus k}(U_{nk}))$が得られる. 特に, $(U_{nk},f_H^{\oplus k}(U_{nk}))\not\approx_c (U_{nk},f^{\oplus k}(U_{nk}))$.
4. $(U_{nk},f^k(U_{nk})) \not\approx_c (U_{nk},f^k_H(U_{nk}))$を得る (k-wise XORを識別できるので). ここで, $f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$と定義していて, $(U_{nk},f^k(U_{nk}))$とは$(x_1,\dots,x_k)\sim U_{nk}$に対して$(x_1,\dots,x_k,f(x_1),\dots,f(x_k))$によって与えられるものです.
5. ハイブリッド議論(hybrid argument)によって$(x,f(x))\not\approx_c (x,f_H(x))$となる (ただし分布のランダムネスは$x\sim U_n$).
6. $H$が密(i.e., $|H|\geq \delta 2^n$)であることを使うと, $H$上一様ランダムな$x\sim H$に対して$(x,f(x))\not\approx_c (x,f_H(x))=(x,U_1)$が示せる.
7. Yao's next-bit predictorより, $x\sim H$に対して$f(x)$を成功確率$1/2+\epsilon$で計算できる.
8. ハードコア補題より$\{0,1\}^n$上で$f$を成功確率$1-\delta$で計算できる. これは元の$f$の条件に矛盾する.

それでは, 定理1の証明をします. 以下の議論では上記のステップ1〜8を補足しつつフォーマルに確認していくだけなので, 上記のアイデアで満足な人は読まなくても構いません.

関数$f$をサイズ$s$に対して$\delta$-困難な関数とし, $H\subseteq\{0,1\}^n$をハードコア集合とします. 回路$D$のサイズを$\mathrm{size}(D)$と表すことにします.

ステップ1. $f^{\oplus k}(U_{nk})$を成功確率$1/2+\epsilon$で計算する回路を$C$とします. 与えられた$(x,b)\in \{0,1\}^{nk+1}$に対して$C(x)\oplus b \oplus 1$を出力する回路を$C_1$とすると,

$$\begin{align*} &\Pr_{x\sim U_{nk}}[C_1(x,f^{\oplus k}(x))=1] = \Pr_x[C(x)=f^{\oplus k}(x)] \geq \frac{1}{2}+\epsilon \\ &\Pr_{x\sim U_{nk},b\sim U_1}[C_1(x,b)=1] = \frac{1}{2} \end{align*}$$

より, 二つの分布$(U_{nk},f^{\oplus k}(U_{nk}))$と$(U_{nk},U_1)$を$\epsilon$のアドバンテージで識別できます. $C_1$のサイズは, $\mathrm{size}(C_1) = \mathrm{size}(C)+O(1)$を満たします.

ステップ2. 関数$f_H\colon\{0,1\}^n\to\{0,1\}$を

$$\begin{align*}f_H(x) = \begin{cases}U_1 & \text{ if }x\in H,\\f(x) & \text{otherwise}\end{cases}\end{align*}$$

とします. ここで$U_1$は各$x\in H$ごとにランダムに生成されるランダムビットです. 厳密には$\mathcal{F}_H$を, 任意の$x\not\in H$に対して$g(x)=f(x)$を満たす関数$g$の集合, すなわち

$$\begin{align*} \mathcal{F}_H = \{g\colon \forall x\not\in H, g(x)=f(x)\} \end{align*}$$

と定義したときに$f_H$は$\mathcal{F}_H$から一様ランダムに選ばれたランダム関数として定義されます. 独立に$k$個の入力$x_1,\dots,x_k\sim U_n$と$k$個のランダム関数$f_H$をサンプリングして, $f_H(x_i)$のXORをとったときの値$f_H^{\oplus k}(x_1,\dots,x_k)$の分布を考えましょう (ランダムネスは$x_i$と$f_H$の選び方についてとる). どれか一つの$i$でも$f_H(x_i)=U_1$であったならば, そのXORの値もまた$U_1$となります. 従って, 統計距離は$\prod_{i=1}^k \Pr[x_i\not\in H] \leq (1-\delta)^k$となり (ここで$|H|\geq\delta\cdot 2^n$を使っている), 適当な$k=O(\log(1/\epsilon)/\delta)$に対して統計距離は高々$0.1\epsilon$となります.

ステップ3. 統計距離の性質から, ステップ1で構成された回路$C_1$は二つの分布$(U_{nk},f^{\oplus k}(U_{nk}))$と$(U_{nk},U_1)$をアドバンテージ$0.9\epsilon$で識別します.

ステップ4. 二つの分布$(U_{nk}, f^k(U_{nk}))$と$(U_{nk},f_H^k(U_{nk}))$を識別する回路$C_2$を以下のように構成します: 入力$(x_1,\dots,x_k,b_1,\dots,b_k)$に対し, $C_1(x_1,\dots,x_k,b_1\oplus\dots\oplus b_k)$を出力する. この回路$C_2$は, $C_1$の識別性により確かに二つの分布$(U_{nk}, f^k(U_{nk}))$と$(U_{nk},f_H^k(U_{nk}))$をアドバンテージ$0.9\epsilon$で識別します. 回路$C_2$のサイズは高々$\mathrm{size}(C_1)+O(k)$です.

ステップ5. ステップ4で構成された回路$C_2$は二つの分布
$$\begin{align*} &D_0 := (x_1,\dots,x_k,f(x_1),\dots,f(x_k)),\\ &D_k := (x_1,\dots,x_k,f_H(x_1),\dots,f_H(x_k)) \end{align*}$$
をアドバンテージ$0.9\epsilon$で識別します. これら二つの分布を滑らかに補間するような分布列$D_1,\dots,D_{k-1}$を
$$\begin{align*} D_i := (x_1,\dots,x_k,f(x_1),\dots,f(x_{i-1}),f_H(x_i),\dots,f_H(x_k)) \end{align*}$$
とします(これをハイブリッド分布とよぶ). $i=0,k$の場合でもそれぞれ$D_0,D_k$になっていることが分かります. $p_i = \Pr[C_2(D_i)=1]$とすると, $p_0 - p_k = \sum_{i\in[k]}(p_{i-1} - p_{i}) \geq 0.9\epsilon$なので, ある$i\in[k]$が存在して$p_{i-1} - p_i \geq 0.9\epsilon/k$を満たします. 

さらに, ある$z_1,\dots,z_{i-1},z_{i+1},\dots,z_k \in \{0,1\}^{n}$および$c_1,\dots,c_{i-1},c_{i+1},\dots,c_k\in \{0,1\}$が存在して,

$$\begin{align*} \Pr_{x\sim U_n}[C_2(\mathbf{v}(i,x,f(x))=1] - \Pr_{x\sim U_n}[C_2(\mathbf{v}(i,x,f_H(x))]\geq \frac{0.9\epsilon}{k} \end{align*}$$
が成り立ちます. ここで, $\mathbf{v}(i,x,b)$は
$$\begin{align*} \mathbf{v}(i,x,b) = (z_1,\dots,z_{i-1},x,z_{i+1},\dots,z_k,c_1,\dots,c_{i-1},b,c_{i+1},\dots,c_k) \end{align*}$$
で定義される文字列である (インデックス$i$と各$z_j$と$c_j$は入力$x$に依存しない値なので, これらの情報を回路にあらかじめ組み込むことによって, 与えられた$x,b$に対し$\mathbf{v}(i,x,b)$はサイズ$O(kn)$の回路で計算できる). 従って, 関数$(x,b)\mapsto C'(\mathbf{v}(i,x,b))$はサイズ$s+O(nk)$程度で計算でき, さらに上記の式より二つの分布$(x,f(x))$と$(x,f_H(x))$をアドバンテージ$0.9\epsilon/k$で識別する. この回路を$C_3$とします.

ステップ6. 全ての$x\not\in H$に対して定義より$f(x) = f_H(x)$となるので, $(U_n,f(U_n))$と$(U_n,f_H(U_n))$が区別できるということは, ステップ5の回路$C_3$を使って$x\sim H$に対して$(x,f(x))$と$(x,f_H(x))$が区別できるということになります. 実際,
$$\begin{align*} \frac{0.9\epsilon}{k} &\leq \Pr[C_3(U_n,f(U_n))=1] - \Pr[C_3(U_n,f_H(U_n))=1] \\ &= 2^{-n}\sum_{x\in\{0,1\}^n} (C_3(x,f(x)) - \mathbb{E}_{f_H}[C_3(x,f_H(x))]) \\ &= 2^{-n}\sum_{x\in H}(C_3(x,f(x)) - \mathbb{E}[C_3(x,U_1)]) & & \text{since $f_H(x)=U_1$ for $x\in H$} \\ &\leq \frac{1}{|H|}\sum_{x\in H}(C_3(x,f(x)) - \mathbb{E}[C_3(x,U_1)]) & & \text{since $f_H(x)=U_1$ for $x\in H$} \\ &= \Pr_{x\sim H}[C_3(x,f(x))=1] - \Pr_{x\sim H,U_1}[C_3(x,U_1)=1] \end{align*}$$

なので$C_3$は, $x\sim H$に対して$(x,f(x))$と$(x,U_1)$を識別します.

ステップ7. 以前の記事で紹介した計算量的な識別不可能性の概念を思い起こします. この概念は関数の困難性と等価であることがYao's next-bit predictorからわかります.

定義1.

$\{0,1\}^n$上の二つの確率変数$X,Y$は, あるサイズ$s$の回路$C$が存在して
$$\begin{align*} \Pr[C(X)=1]-\Pr[C(Y)=1]\geq \epsilon \end{align*}$$

を満たすとき, サイズ$s$で$\epsilon$-識別可能であるといい, $C$を識別回路という. 逆に, そのような回路$C$が存在しない場合はサイズ$s$で$\epsilon$-識別不可能であるという.

補題2 (Yao's next-bit predictor; 以前の記事の定理の対偶の言い換え).

関数$f\colon \{0,1\}^n\to\{0,1\}$に対し, 二つの分布$(U_n,f(U_n))$と$(U_n,U_1)$がサイズ$s$で$\epsilon$-識別可能であるならば, サイズ$s+O(1)$のある回路$C$が存在して

$$\begin{align*} \Pr_{x\sim U_n}[C(x) = f(x)] \geq \frac{1}{2} + \epsilon. \end{align*}$$

上記の補題において, $U_n$を$H$上の一様分布に置き換えることによって以下の補題を得ます.

補題3.

関数$f\colon \{0,1\}^n\to\{0,1\}$と任意の集合$H\subseteq\{0,1\}^n$を考える. $x\sim H$に対して二つの分布$(x,f(x))$と$(x,U_1)$がサイズ$s$で$\epsilon$-識別可能であるならば, サイズ$s+O(1)$のある回路$C$が存在して
$$\begin{align*} \Pr_{x\sim H}[C(x) = f(x)] \geq \frac{1}{2} + \epsilon. \end{align*}$$

補題3の証明は省略しますが, $\ell = \lceil \log_2 |H|\rceil$に対して, $H$上の一様分布を$U_\ell$とみなすことができることから分かると思います.

ステップ6までの議論より補題3の仮定を満たす回路が存在するので, あるサイズ$\mathrm{size}(C_3)+O(1) = s+O(nk)$の回路$C_4$が存在して
$$\begin{align*} \Pr_{x\sim H}[C_4(x) = f(x)] \geq \frac{1}{2} + \frac{0.9\epsilon}{k} \end{align*}$$
が成り立ちます.

ステップ8. ハードコア補題(補題1)の対偶を適用する. 任意の$|H|\geq \delta 2^n$を満たす$H$に対してある回路$C_4$が存在して$p_{C_4,f,H}\geq \frac{1}{2} + \frac{0.9\epsilon}{k}$となるので, 補題1'より, $f$を成功確率$1-\delta$で計算する回路$C_5$であって, サイズ
$$\mathrm{size}(C_5) = O\left(\frac{\log(1/\delta)}{(\epsilon/k)^2}(s+kn)\right)$$
となるものが存在する. これは定理1の$f$の困難性の仮定に矛盾します.