エントロピーを使ったXOR補題の証明

嬉しいことに今年STOCに2本の論文を通せたのですが、そのうち一本は、XOR補題（の自然な拡張）をエントロピーを使って証明して、それをaverage-case fine-grained complexityのある数え上げ問題に応用した論文でした。XOR補題は計算量理論では80年代からよく知られている結果で、すでにいくつもの証明方法が知られている（例えば[GNW]が有名）のですが、我々が与えたエントロピーに基づく証明の方が、証明の筋道が直感的にわかり易いのと、（計算量的）疑似エントロピーの良い導入になるので、教育的なのではないかと思っているので、ここで概説します。あくまでも雰囲気がつかめる程度の粒度の記事ですので、細かい詳細は私に直接問い合わせてください（または後日full versionを出すのでそれを参照）。なお、応用についてはここでは省きます。

統計的 vs. 計算量的

平均時計算量という計算量理論の一分野では、情報理論におけるエントロピーなどの概念を「計算量的に」修正したアナロジーを考えることによって、情報理論的な議論に基づいて計算量の結果を証明するということがよく行われます。例えば二つの確率変数$X,Y$の近さを測る指標としてしばし統計距離が使われますが、これは（その確率変数の台を$\Omega$として）

\[
d_{TV}(X,Y)=\max_{D\colon \Omega\to\{0,1\}} \left\{|\Pr[D(X)=1] - \Pr[D(Y)=1]|\right\}
\]
によって定義されます（本来は分布に対して定義されるが、ここでは利便性のため、その分布に従ってサンプリングされた確率変数に対して距離を考えることにする）。ここでは簡単のため$\Omega$は有限集合としています。このとき考える関数$D$を識別者と呼びます。気持ちとしては、識別者は

「与えられた値は$X$と$Y$どちらからサンプリングされたものですか？」

という問題を解こうと頑張っており、その精度の限界値が統計距離となります。すなわち、統計距離が小さいということは、任意の識別者にとって$X$と$Y$が識別できないということになるので、この性質を統計的な識別不可能性（または情報理論的な識別不可能性）と呼びます。

さて、統計距離の定義で考える識別者とは任意の関数を考えていますが、これを

限定的な計算能力を持つ識別者のクラス

に制限することによって新たな識別不可能性の概念を考えることができます。例えば「任意の多項式時間アルゴリズムにとって一様ランダムな文字列と識別できない」といった議論が展開できるわけですが、これを計算量的な識別不可能性と呼び、特に一様ランダムと計算的に識別不可能であるという性質を計算量的疑似ランダムネスと呼びます。

情報理論的には、データ処理不等式により、任意の決定的な関数$f\colon \{0,1\}^n\to\{0,1\}$に対して、分布 $(U_n, f(U_n))$ のエントロピー（ここで$U_n$は$n$ビットの一様ランダムな文字列）は元のランダムシードのエントロピーと一致して必ず$n$のままになる（つまり、決定的な作用を施してもエントロピーは増えない）のですが、計算量理論的な枠組みではある種の計算困難性を仮定すると（計算量理論的）エントロピーを増大できる、という驚くべき結果が知られています。

証明は以前の記事に譲るとして、もう少し深掘りすると、関数$f\colon\{0,1\}^n\to\{0,1\}$が強い平均時困難性を持つとは、任意の効率的な乱択アルゴリズム（注：厳密には非一様なアルゴリズムを考えている）$A$に対して
\[
\Pr_{x\sim U_n,A}[A(x)=f(x)] \le \frac{1}{2} + \varepsilon
\]
を満たすことを言います（$\varepsilon$は文脈依存だがとにかく小さい値。とりあえず$1/\mathrm{poly}(n)$だと思えばよい）。例えば$A$として、$0$ or $1$をランダムに出力するアルゴリズムを考えると正しく$A(x)=f(x)$になる確率はぴったり$1/2$になるわけですが、非自明な精度で$f(x)$を推定しようとすると、その計算能力はすごく沢山要する、というわけです。一方で、右辺が$1$に近い、すなわち
\[
\Pr_{x\sim U_n,A}[A(x)=f(x)] \le 1 - \delta
\]
を満たすとき、弱い平均時困難性を持つと言います。

さて、強い平均時困難性を持つ$f$に対して
\[
(U_n,f(U_n))
\]
という$n+1$ビットの文字列は計算量的疑似ランダムであることが知られており、その逆も成り立ちます。すなわち、関数の計算困難性を計算量的疑似ランダム性で特徴づけられます。例えばNisan-Wigderson生成器を使うと（ある計算量下界の仮定の下での）脱乱択化ができるといった応用があります。

XOR補題

YaoのXOR補題とは、一方向性関数の文脈でYao(1982)で提示された（のちにLevin(1985)で証明が与えられた）結果です。簡単にいうと、弱い平均時困難性を持つ関数 $f\colon \{0,1\}^n\to\{0,1\}$ に対して、別の関数$f^{\oplus k}\colon\{0,1\}^{kn}\to\{0,1\}$を

\[
f^{\oplus k}(x_1,\dots,x_k) = f(x_1) \oplus \dots \oplus f(x_k)
\]

と定義したとき、この関数は（十分大きな$k$に対して）強い平均時困難性を持つ、という結果です。ですので、弱い困難性を持つ関数の下でも、XORをとることでその困難性を増幅させることで、脱乱択といった応用にあてはめることができるようになります。

冒頭でも述べたように、XOR補題の証明は色々知られていて

• 直積定理＋Goldreich-Levin
• hardcore補題
• isolation lemma (Levinによる証明）

などが知られています。本記事で説明する別アプローチの証明は、ZhengのD論(2014)で証明された弱い平均時困難性の計算量的疑似平均最小エントロピー (pseudo average min-entropy)による特徴づけ(PAME theorem)を用います。

疑似（最小）エントロピーとXOR補題

関数 $f$ の強い平均時困難性は疑似ランダム性で特徴づけられると述べましたが、弱い困難性は最小エントロピーの言葉で特徴づけることができます。直感的には、弱い困難性を持つ関数 $f\colon \{0,1\}^n\to\{0,1\}$ に対して

\[
f(U_n)
\]

という確率変数を考えます。この平均時困難性は、$U_n$が与えられても計算能力が制限された識別者にとっては$f(U_n)$の値が類推できない、すなわちランダムに見えることを保証します。もし$f$が弱い困難性を持つとき、ある程度の精度で類推できるものの、ある程度の確率で間違えます。これを、「$f(U_n)$はある程度のエントロピーを持つ」と解釈します。このエントロピーを疑似エントロピーと呼びます。

もう少しちゃんと述べると、関数 $f$ が疑似エントロピー $\theta$ を持つとは、ある確率変数の組 $(U_n,Z)$ が存在して、

• $(U_n, f(U_n))$ と $(U_n, Z)$ が計算量的に識別不可能
• 条件付き最小エントロピーが$H_{\mathrm{min}}(Z|U_n) \ge \theta$

を満たすことを言います。文脈によってShannonエントロピーを考えることも多いのですが、ここではminエントロピーを考えます（両者の差分については踏み込まないので、詳しくない読者はとりあえず「エントロピーがある」程度の認識で大丈夫です）。

もしも$Z$が一様ランダムなビットだったら疑似ランダム性を持つということになるのですが、この定性的な主張をエントロピーを使って定量的な主張にできます：

定理（Zheng (2014),  informal)

関数 $f\colon \{0,1\}^n\to\{0,1\}$ が弱い困難性を持つ $\iff$ $f$が疑似エントロピー $\log_2 \frac{1}{1-\delta}$ を持つ。

この定理の証明はZhengのD論に書いてあります（私は咀嚼でかなり苦労しました）。ひとまずこの特徴づけを用いると、XOR補題を以下のような流れで証明できます：

1. $f$が弱い困難性を持つので、特徴づけより疑似エントロピーを持つ。
2. $x_1,\dots,x_k \sim U_n$ を独立に選ぶと、$f(x_1),\dots,f(x_k)$はそれぞれ独立でしかも各は$\log_2 \frac{1}{1-\delta}$ の疑似エントロピーを持つ。
3. 情報理論的な議論（本当はフーリエ解析）によって、エントロピーを持つ独立な確率変数の和 $\bmod 2$ はエントロピーが増大する。
4. $k$が十分大きいときはエントロピーはほぼ最大値$1$になる。すなわち$f^{\oplus k}(x_1,\dots,x_k)$は疑似ランダムなので、$f^{\oplus k}$ は強い困難性を持つ。

XOR補題の拡張

XOR補題ではBoolean関数 $f\colon\{0,1\}^n\to\{0,1\}$を考えており、和をとることでBooleanであることを保証するために$\mathbb{F}_2$上での演算を考えていました。我々の論文ではこれを$\mathbb{F}_p$値をとる関数$f\colon\{0,1\}^n\to\mathbb{F}_p$に拡張しました（ただし$p$は素数）。

議論は上のステップ1から4のままです。実はZheng(2014)の結果は$f$がBooleanでなくても成り立つ結果であることを利用します。$p$が素数であるという条件はステップ3において本質で、合成数だと一般には成り立ちません（例えば$\bmod 4$だと、$\{0,2\}$上一様ランダムな確率変数をいくつ足してもエントロピーは変わらない）。

なお、これまで知られているXOR補題の証明はBoolean関数であることを利用しており、例えばhardcore補題ではboostingのために多数決をとるという操作がありますがここでBoolean関数であることを本質的に利用してます。Goldreich-Levinは$\mathbb{F}_2$上のHadamard符号のリスト復号アルゴリズムですが、これを$\mathbb{F}_p$に拡張したリスト復号アルゴリズム（[GRS])を用いると、少し異なる主張になってしまいます。