ITCS 2022 游记

r_64 posted @ 2022年1月27日 10:27 in 未分类 , 342 阅读

ITCS 2022于今年1月31日至2月3日在线上举办。今年ITCS有很多很有趣的文章,我摘抄了几篇写了点笔记放出来。

Small Circuits Imply Efficient Arthur-Merlin Protocols

这篇文章研究的是一个经典问题:${\sf IP}$是否存在很小的${\sf AC}^0\circ {\sf XOR}$电路?这里,${\sf IP}(x, y) := \bigoplus_{i=1}^nx_iy_i$表示“Inner Product mod $2$”。

文章的主要结果是:假设${\sf IP}$可以被一个多项式大小的${\sf DNF}\circ{\sf XOR}$电路近似,那么${\sf IP}$有一个两轮、${\rm polylog}(n)$通信复杂度的Arthur-Merlin协议。于是,我们把一个电路复杂度的问题(${\sf IP}$的${\sf DNF}\circ{\sf XOR}$平均复杂度下界)规约到了一个通信复杂度的问题。

假设Alice知道$x$,Bob知道$y$,Merlin知道$x$和$y$,三方的计算能力都是无限的,但是Alice和Bob都不信任Merlin。现在我们需要在Merlin的帮助下,以尽可能少的通信计算${\sf IP}(x, y)$。我们分两步走:

  • 第一步,我们先构造一个确定性的协议。给定$x, y$,这个协议只能证明${\sf IP}(x, y) = 1$(而不能证明${\sf IP}(x, y) = 0$)。并且,这个协议只能处理大部分$x, y$,对较少的$x, y$会出错。
    考虑一个中间层的${\sf AND}$门,管它叫做$g$。$g$底下是一些${\sf XOR}$门,设这些${\sf XOR}$门组成的线性空间的维度为${\rm dim}(g)$。如果${\rm dim}(g) \ge O(\log n)$,那么我们把$g$扔掉。注意到只有占比$2^{-{\rm dim}(g)}$的输入会满足$g$,所以当${\rm dim}(g)$太大的时候,我们扔掉$g$之后只会影响小部分输入。于是我们得到了一个被剪枝了的${\sf DNF}\circ{\sf XOR}$电路,它也能近似计算${\sf IP}$,且它的每个${\sf AND}$门的维度都只有$O(\log n)$。
    现在,我们要证明${\sf IP}(x, y) = 1$。Merlin找到这个电路中输出$1$的某个${\sf AND}$门,管它叫做$g$,然后把$g$的编号告诉Alice和Bob。于是Alice和Bob只需要计算${\rm dim}(g)$个${\sf XOR}$门的值——这只需要交换$O({\rm dim}(g))$个比特。
    这里重申一下该协议的两个缺点:(1)该协议只能证明${\sf IP}(x, y) = 1$,而不能证明${\sf IP}(x, y) = 0$。(2)对大部分的$x, y$,如果${\sf IP}(x, y) = 1$,那么该协议能够证明这一点;但是对于某些$x, y$该协议会失效——因为给出的电路是近似计算${\sf IP}$的,且我们砍掉了该电路中的一些${\sf AND}$门。
  • 第二步,我们利用${\sf IP}$的性质来把这个协议变成一个完整的协议——对于所有的$x, y$,它可以用来证明${\sf IP}(x, y)$的值。最终完整的协议会使用随机数,且会有很小的概率出错。Alice和Bob分别选择随机串$u, v\in\{0, 1\}^n$,然后利用如下性质:
    \[{\sf IP}(x, y) = {\sf IP}(x \oplus u, y \oplus v) \oplus {\sf IP}(x\oplus u, v) \oplus {\sf IP}(u, y\oplus v) \oplus {\sf IP}(u, v).\quad(*)\]
    Alice和Bob随机选择$q = {\rm polylog}(n)$个不同的$u, v$给Merlin,然后要求Merlin给出上述式子中四个${\sf IP}$的值。Merlin还需要证明这$4q$个${\sf IP}$中尽可能多的等于$1$的${\sf IP}$确实等于$1$。然后,Alice和Bob相信Merlin没有证明的所有${\sf IP}$都等于$0$。这$4q$个${\sf IP}$的分布都是均匀随机的,所以就算上面那个协议会在某些$x, y$上出错,Merlin还是可以证明大部分等于$1$的那些${\sf IP}$。如果对于这$q$个实验中的大部分实验,$(*)$式中算出的${\sf IP}(x, y)$的值都相等,那么Alice和Bob认为这就是${\sf IP}(x, y)$的值。
    且慢,为什么Alice和Bob可以直接相信Merlin没有证明的${\sf IP}$都是$0$?这是因为在上述$4q$个${\sf IP}$中,等于$1$的${\sf IP}$大概率至少有$2q - O(\sqrt{q})$个,且Merlin可以证明这些${\sf IP}$中的绝大多数。(如果Merlin想要骗人,他不可能声明一个等于$0$的${\sf IP}$“等于$1$”,只能声明一个等于$1$的${\sf IP}$“等于$0$”。)那么Alice和Bob如果发现Merlin证明的${\sf IP}$(等于$1$)的个数太少了,就可以直接拒绝Merlin的证明。如果Merlin证明的${\sf IP}$等于$1$的个数足够多,那么Alice和Bob就可以相信剩下的${\sf IP}$都是$0$。

总结:如果${\sf IP}$可以被很小的${\sf DNF}\circ{\sf XOR}$电路近似,那么${\sf IP}$也有很好的Arthur-Merlin通信协议,这在通信复杂度中被认为是不太可能的。所以,我们把${\sf IP}$的电路复杂度下界问题规约到了一个通信复杂度问题。

Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

这篇文章研究的是一种叫比较电路(comparator circuit)的计算模型。如下图就是一个比较电路:电路中有一些线(wire)和一些门(gate),每条线的初始值是某个$x_i$或$\lnot x_i$(可以有多条线有相同的初始值),每个门会输入两根线$a, b$,然后将$a$的新值赋成$a_{\rm new} := a\land b$,将$b$的新值赋成$b_{\rm new} := a\lor b$。

Gal和Robere证明了这种电路的第一个$\Omega((n/\log n)^{1.5})$的下界,这篇文章把上述结果推广到了平均复杂度下界、#SAT算法和PRG。

文章中最重要的技术是一个shrinkage引理:假设我们随机给若干变量赋值,那么我们会得到一个剩下的电路,这个电路作用在所有未赋值的变量上。shrinkage说的是:剩下的那个电路会比原电路显著更小。事实上,如果一个比较电路有$\ell$条线,那么它至多有$O(\ell^2)$个门(或者说与某个$O(\ell^2)$个门的电路等价)。所以如果我们随机将占比为$p$的变量赋值成$0$或$1$,那么期望意义下只会剩下$p\ell$条线,也就只剩下$O(p^2\ell^2)$个门了。

一个open problem:能否证明比$O(n^{1.5})$更强的比较电路的复杂度下界?我感觉有理由认为当前的技术不紧。。。。

Smaller ACC0 Circuits for Symmetric Functions

这篇文章证明了${\sf MAJ}$(事实上,任意对称函数)都可以用一个深度为$3$、大小为$2^{n^{o(1)}}$的${\sf CC}^0$电路计算。更精确地说,对任意$\epsilon > 0$,存在一个模数$m$,使得${\sf MAJ}$可以用一个深度为$3$、大小为$2^{n^\epsilon}$的只由${\sf MOD}_m$门构成的电路计算。作为对比,如果只允许用${\sf AND}$、${\sf OR}$和${\sf MOD}_2$,那么在深度为$3$的情况下我们至少需要$2^{\Omega(n^{1/2})}$大小的电路。这些结果表明${\sf ACC}^0$电路的表达能力很可能比我们想象中更加强大。

在这里我们只证明$\epsilon = 1/3 + o(1)$、$m = 30$的情况:事实上,存在一个计算${\sf MAJ}$的${\sf MOD}_5\circ {\sf MOD}_6\circ {\sf MOD}_5$电路,它的大小仅为$2^{O(n^{1/3}\log n)}$。

做法用的是中国剩余定理。首先考虑两个参数$T, s$,我们可以使用卢卡斯定理(见论文Theorem 3.2)构造一个度数不超过$O(2^s)$的多项式$p_2$,使得:

  • 当$\sum_{i=1}^nx_i\equiv T\pmod {2^s}$时,$p_2(x_1, x_2, \dots, x_n) \equiv 0\pmod 2$,否则$p_2(x_1, x_2, \dots, x_n)\equiv 1\pmod 2$。

同理,给出参数$T, t$,我们可以构造一个度数不超过$O(3^t)$的多项式$p_3$,使得:

  • 当$\sum_{i=1}^nx_i\equiv T\pmod {3^t}$时,$p_3(x_1, x_2, \dots, x_n) \equiv 0\pmod 3$,否则$p_3(x_1, x_2, \dots, x_n)\equiv 1\pmod 3$。

于是,如果我们取$2^s, 3^t\approx O(\sqrt{n})$,且$T\le n \le 2^s3^t$,那么我们就能够搞到一个度数为$O(\sqrt{n})$的多项式$p = 3p_2 + 2p_3$,使得$p\equiv 0\pmod 6$当且仅当$\sum_{i=1}^n x_i = T$。

有了这个多项式之后,我们就可以用一些分块小技巧了。我们把输入划分成$\ell = n^{1/3}$块,每块大小为$n^{2/3}$。我们枚举$\vec{T} = (T_1, T_2, \dots, T_\ell)$,其中$T_i$表示第$i$块中$1$的个数。对所有满足条件的$\vec{T}$,我们检查这个$\vec{T}$是否符合我们的输入。(如果我们算的函数是${\sf MAJ}$,那么“满足条件”的意思是$\sum_{i=1}^\ell T_i \ge n/2$;显然,这个做法也可以扩展到一般的对称函数上去。)一共有$2^{O(n^{1/3}\log n)}$种可能的$\vec{T}$。对一个固定的$\vec{T}$,我们只要用一个度数为$\sqrt{n/\ell}=O(n^{1/3})$的$\bmod 6$多项式就可以检查第$i$个块里是否恰好有$T_i$个$1$。我们把所有$\vec{T}$的检查结果用一个${\sf MOD}_5$合并起来就行了。(因为符合我们输入的$\vec{T}$要么有一个,要么一个也没有,所以最顶层可以选包括但不限于${\sf OR}$、${\sf MOD}_p$的门。)

这样,我们得到了一个计算${\sf MAJ}$的${\sf MOD}_5\circ {\sf AND}\circ {\sf MOD}_6\circ {\sf AND}$电路,它的大小是$2^{O(n^{1/3}\log n)}$,且每个${\sf AND}$的大小都是$O(n^{1/3})$。我们可以用一些经典的技术把${\sf AND}$门换成大小为$2^{O(n^{1/3})}$的${\sf MOD}_5$或${\sf MOD}_6$门,最终得到一个大小为$2^{O(n^{1/3}\log n)}$的${\sf MOD}_5\circ {\sf MOD}_6\circ {\sf MOD}_5$电路。

一个open problem:既然${\sf MAJ}$能用$2^{n^{o(1)}}$大小的${\sf CC}^0$电路计算,我们能不能用差不多大小的${\sf CC}^0$电路计算${\sf NC}^1$中的问题呢?(比如说$S_5$上的word problem?)

Pseudorandom Self-Reductions for NP-Complete Problems

这篇文章的结论很有意思!我先介绍一下背景。

如果一个问题$L$是${\sf NP}$-完全的,那么你无法把$L$的最坏情况规约到平均情况(除非${\sf NP}\subseteq{\sf coNP}_{/{\rm poly}}$)。比如说,你无法把“在最坏情况下解决$L$”规约到“在平均情况下解决$(L, {\cal U})$”,其中${\cal U}$是指$L$上的输入的均匀随机分布。HS17证明了如果存在单向函数(one-way functions),那么我们可以把“在最坏情况下解决${\sf GapMCSP}$”规约到“在平均情况下解决$({\sf MCSP}, {\cal U}')$”。这里${\cal U}'$是一个伪随机分布——任意多项式时间的算法无法区分${\cal U}$和${\cal U}'$。HS17把这一结论看成是${\sf MCSP}$和一般的${\sf NP}$-完全问题的一个不同点。

这篇文章证明了:假设Planted Clique是困难的,那么我们可以把“在最坏情况下解决${\sf Clique}$”规约到“在平均情况下解决$({\sf Clique}, {\cal U}')$”!其中${\sf Clique}$是最大团问题(这是个${\sf NP}$-完全问题!),${\cal U}'$是一个伪随机分布。这说明HS17的结论不应该看成“${\sf MCSP}$和一般的${\sf NP}$-完全问题的不同点”,而是应该看成“伪随机规约比真随机规约更强”。

具体地说,文章中的规约长这样:首先我们假设我们只需要区分最大团大小$\le n^{0.1}$和最大团大小$\ge n^{0.9}$。(这是因为$n^{0.8}$-近似最大团仍然是${\sf NP}$-完全的。)给出一个图$G$,令$f(G)$为如下的随机图:随机取一个大小为$n^{0.3}$的集合$S$,然后$f(G)$中$S$内部的边与$G$完全相同,剩下的边完全随机。

  • 正确性:如果$G$的最大团大小$\ge n^{0.9}$,那么$f(G)$的最大团大小大概率至少是$n^{0.2}$。如果$G$的最大团大小$\le n^{0.1}$,那么$f(G)$的最大团大小大概率也不会超过$n^{0.1}$。
  • 伪随机性:如果令$K_S$表示$S$上的完全图,$\oplus$表示异或操作,那么$f(G)\oplus G\oplus K_S$的分布恰好是一个偷偷插入了一个大小为$n^{0.3}$的团的随机图。如果Planted Clique假设成立,那么$f(G)\oplus G\oplus K_S$是伪随机的,所以$f(G)$也是伪随机的。

Excluding PH Pessiland

文章的结果是:${\sf DistPH}$的复杂度很高,当且仅当存在一个可以在${\sf PH}$内计算出来的PRG。“复杂度很高”有两种定义方法——${\sf BPP}$算法无法解决某个问题、或者${\sf P}_{/{\rm poly}}$算法无法解决某个问题。对于这两个定义,文章都证明了上述等价性。

  • ${\sf DistPH}\not\subseteq {\sf HeurP}_{/{\rm poly}}$当且仅当${\sf PH}$内可以计算出${\sf P}_{/{\rm poly}}$无法破解的PRG。
    $\implies$方向:用Yao's XOR lemma和Nisan-Wigderson PRG。
    $\impliedby$方向:可以用Liu-Pass来证明${\rm MINK}^{{\rm poly}, {\sf PH}}$在均匀随机的输入上是困难的。
  • ${\sf DistPH}\not\subseteq {\sf HeurBPP}$当且仅当${\sf PH}$内可以计算出${\sf BPP}$无法破解的PRG。
    $\implies$方向:由于Nisan-Wigderson PRG只能搞${\sf P}_{/{\rm poly}}$不能搞${\sf BPP}$,所以我们得用其他的PRG。这里我们使用advice complexity很小的direct product PRG($\rm DP$)。如果$\rm DP$不安全,那么${\sf DistPH}\subseteq{\sf HeurBPP}_{//\log}$。然后我们用一些其他的思路把这$\log n$位的advice去掉(具体没太看)。
    $\impliedby$方向:破解一个${\sf PH}$内计算出来的PRG可以规约到一个平均复杂度问题$(L, {\cal D})$,其中$L\in{\sf PH}$,${\cal D}$是一个能用${\sf PH}$的复杂度采样的输入分布。因为${\sf DistPH}\subseteq {\sf HeurBPP}$,我们可以用一个多项式时间采样的分布${\cal D}'$来近似${\cal D}$。再用一遍${\sf DistPH}\subseteq {\sf HeurBPP}$,我们有$(L, {\cal D}')\in{\sf HeurBPP}$,于是这个PRG是不安全的。

不管是哪种情况,本文都证明了一个很有趣的结论:$({\rm MINK}^{{\rm poly}, {\sf PH}}[n - \log n], {\cal U})$是${\sf DistPH}$中最难的问题,其中${\cal U}$是均匀随机分布。

这篇文章可以和Hirahara-FOCS20对比着阅读!虽然技术不太一样,但是它们的结论很相似:

  • 这篇文章:${\sf DistPH}\subseteq {\sf HeurBPP}$当且仅当${\rm MINKT}^{\sf PH}\times\{{\cal U}\}\in{\sf HeurBPP}$当且仅当${\sf PH}$中没有无法被${\sf BPP}$破解的PRG。
  • Hirahara-FOCS20:${\sf DistPH}\subseteq {\sf AvgP}$当且仅当${\rm GapMINKT}^{\sf PH}\in{\sf P}$当且仅当${\sf PH}$中没有无法被${\sf P}$破解的HSG。(最后一个“当且仅当”需要假设${\sf P} = {\sf ZPP}$。)

另外我看了一下这篇文章的视频,Shuichi提出了“${\sf PH}$版本的五个世界”,感觉很有意思!

Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity

视频里讲了3SUM的Merlin-Arthur协议,我好像听懂了所以就摘抄一下(

给出整数$t$和$a_1, a_2, \dots, a_n$,我们希望在$\tilde{O}(n)$的时间内证明不存在$i, j, k$使得$a_i + a_j + a_k = t$。首先,Merlin选择一个比较好的质数$p\le n^2$,使得满足$a_i + a_j + a_k \equiv t \pmod p$的$(i, j, k)$的个数不超过$\tilde{O}(n)$。(因为每个$(i, j, k)$只会给$O(\log n)$个质数做贡献,所以这样的$p$是存在的。)接下来,Merlin把所有满足$a_i + a_j + a_k \equiv t \pmod p$的$(i, j, k)$都发给Arthur。最后,Merlin还需要向Arthur证明他已经发了所有可能的$(i, j, k)$。于是我们把问题归结到了如下版本的#3SUM:

给出整数$t,p,count\le n^2$和$a_1, a_2, \dots, a_n \le p$,证明满足$a_i + a_j + a_k \equiv t\pmod p$的$(i, j, k)$的个数恰好为$count$。

由于只有三个数相加,所以三个数的和一定是$t$、$t+p$或者$t+2p$。简单起见我们只考虑证明$a_i+a_j+a_k=t$的解有$count$个的情况。

注意这个版本的问题与最一般的3SUM问题的区别在于:所有的$a_i$都不超过$n^2$了。接下来我们用某种“分块”把$a_i$的值域分成$O(n)\times O(n)$,然后使用一些FFT的技术。具体地说,令$A(x) = \sum_{i=1}^n x^{a_i}$,$A(x)^3 = \sum_{t=1}^{3n^2} b_tx^t$,那么$b_t$就是满足$a_i+a_j+a_k=t$的$(i, j, k)$的个数。我们搞一个如下的分块trick:令$T = \{t' \le 3n^2: t' \equiv t \pmod n\}$,可以把$T$看成一个步长为$n$的包含$t$的等差数列。我们把$A(x)^3$的次数在$T$内的那些项都拿出来,得到多项式
\[\bar{A}(r) = \sum_{s\in T}b_sr^s.\]
Merlin会给Arthur发送$\bar{A}$的所有系数(于是当然也会发送$b_t$)。设Merlin发送的系数为$\bar{A}_{\rm Merlin}(r) = \sum_{s \in T}{\rm merlin}_sr^s$。Arthur只需要随机选取一个数$r$并计算$\sum_{s\in T}{\rm merlin}_sr^s$,并验证其的确等于$\bar{A}(r)$即可。

现在问题变成我们需要在$\tilde{O}(n)$的时间内计算$\bar{A}(r)$。事实上,$\bar{A}(r)$就是多项式$A(xr)^3\bmod (x^n-1)$在第$x^{t\bmod n}$项的系数。我们只要先算出多项式$A(xr)\bmod (x^n-1)$然后再求立方即可,这可以用FFT在$\tilde{O}(n)$的时间内完成。

Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions

为了解释这篇文章在干嘛,我们需要先回顾一下它的前作(Hirahara-STOC21)。前作证明了如果${\sf DistNP}\subseteq{\sf AvgP}$,那么${\sf UP}\subseteq{\sf DTIME}[2^{O(n/\log n)}]$。

具体地说,定义一个串的计算深度(computational depth)为${\rm cd}^{s, t}(x) = {\rm K}^s(x) - {\rm K}^t(x)$,其中$s,t$为两个参数。假设${\sf DistNP}\subseteq{\sf AvgP}$,那么存在一个多项式$p$使得如下结论成立:对任意$L\in{\sf UP}$,存在一个(最坏复杂度下的)算法,给出输入$x$和参数$t$,令$k = {\rm cd}^{t, p(t)}(x)$,能在${\rm poly}(n, t, 2^k)$时间内算出$L(x)$。于是,我们有如下的trick:令$I = \epsilon \log n$为一个参数,$t_0$为一个初始值,$t_i = p(t_{i-1})$。我们有

\[n\ge {\rm K}^{t_I}(x) - {\rm K}^{t_0}(x) = \sum_{i=1}^I{\rm cd}^{t_{i-1}, t_i}(x),\]

所以一定存在一个$i$使得${\rm cd}^{t_{i-1}, t_i}(x) \le n/I$。这样的话,我们就可以在${\rm poly}(n, t_I, 2^{n/I}) \le 2^{O(n/\log n)}$的时间内解决$L$。

这篇文章证明了一个更加精细的结论:如果${\sf DistNTIME}[n]\subseteq {\sf AvgTIME}[\tilde{O}(n)]$,那么${\sf UP}\subseteq {\sf DTIME}[2^{O(\sqrt{n\log n})}]$。我觉得这篇文章最重要的insight是:如果上述推导中的$p$不仅仅是个多项式,而且是$\tilde{O}(n)$的,那么在精心选取$I$之后,最终的复杂度会变成$2^{O(\sqrt{n\log n})}$。当然,文章需要用很多新的技术才能把$p$从多项式改进到$\tilde{O}(n)$。

Beating Classical Impossibility of Position Verification

虽然是我完全不懂的领域但是我听了talk之后觉得问题很有意思!于是我稍微记录一下(

问题是这样的:假设有一个宇航员(称他为prover好了),他希望向我们证明他所在的位置。我们可以和他互相发信息,并且假设信息的传播速度等于光速。prover可以向我们证明他的位置吗?简单起见假设空间是一维的,光速等于$1$,我们在坐标$0$和$2$处有两个verifier(分别称作$V_0$和$V_2$),prover希望证明他的坐标是$1$。如果prover是恶意的(即:坐标不是$1$但是希望骗过verifier),那么他可以控制$1$除外的所有位置。(比如说可以有两个prover,一个在$0.5$,一个在$1.5$。)

一个naïve的做法如下:事先确定一个函数$f$。两个verifier分别向prover发送信息$m_0, m_1$,然后prover在收到所有信息后立即把$f(m_0, m_1)$返回给两个verifier。如果两个verifier都能在两个单位时间内收到正确的答案,那么我们认为prover的确是在坐标$1$的。可以参考下图,其中横轴是空间、纵轴是时间。

这个naïve的做法是不安全的!假设空间中有两个(恶意的)prover $A_0$、$A_1$,其中$A_0$在$r$处、$A_1$在$2-r$处。那么$A_0$可以在收到$m_0$后立马把$m_0$传给$A_1$,$A_1$在收到$m_1$后立马把$m_1$传给$A_0$,$A_0$在收到$m_1$后把$f(m_0, m_1)$传给$V_0$,$A_1$在收到$m_0$后把$f(m_0, m_1)$传给$V_2$。这样,虽然$A_0$和$A_1$都可以离$x=1$很远,但是他们可以联合起来骗过两个verifier。如下图。

如果只考虑经典的prover和verifier的话,这件事情其实是不可能的!于是我们考虑量子协议。注意到上述攻击中,$A_0$需要把消息$m_0$复制一遍然后传给$A_1$,而量子信息是不可复制的。利用这一点,我们可以构造一个量子协议:$V_0$给prover发送一个BB84量子态(形如$H^\theta|b\rangle$,其中$\theta,b\in\{0, 1\}$,$H$是Hadamard变换),同时$V_2$给prover发送$\theta$。prover在得到了量子态和$\theta$之后,根据$\theta$决定如何观测得到的量子态($\theta=0$就是标准基、$\theta=1$就是Hadamard基),然后将观测结果发送给两个verifier即可。注意,如果有两个恶意的prover $A_0$、$A_1$的话,$A_0$会需要把量子态复制一份发给$A_1$,而根据不可复制定理,这件事是做不了的。

注意到上述协议要求verifier向prover发送一些量子信息。本文考虑的是如下问题:一个经典的verifier能不能验证prover的位置?(也就是说verifier的计算能力是经典的、同时只能给prover发送经典信息。)本文证明了这样的协议至少蕴含一个proof of quantumness——也就是说prover不仅得是量子的,还得能够向verifier证明他有做量子计算的能力!另一方面,基于之前的一个proof of quantumness的协议,本文提出了一个只需要经典verifier的位置验证协议。(协议的安全性是基于LWE的量子复杂性的。)此外,文章中使用了一种叫“computational no-cloning”的概念:多项式时间的量子计算机无法克隆某些量子态。

Secret Sharing, Slice Formulas, and Monotone Real Circuits

设$f:\{0, 1\}^n \to \{0, 1\}$是一个单调函数,本文研究了$f$的三种复杂度:

  • Secret sharing:假设我们有一个秘密要发给$n$个人,我们给每个人发一些消息,并且使得如下条件成立。对任意$x\in\{0, 1\}^n$,假设$x_i = 1$的这些人聚在一起共享他们得到的消息。那么当且仅当在$f(x) = 1$时,他们能够还原出我们发送的秘密。$f$的秘密共享复杂度即为至少需要给大家发送的消息总长度。
  • Formula over slices:一个$(k,\ell)$-slice门是指任意一个$\ell$个输入的函数$g$,使得$g$接受所有$1$的个数大于$k$的输入,并拒绝所有$1$的个数小于$k$的输入。在$1$的个数等于$k$的输入上,$g$可以是任意函数。$f$的FOS复杂度即为用slice门组成的formula计算$f$所需要的最少的slice门的个数。
  • monotone real formula:我们希望用一个formula来计算$f$,其中这个formula的每个门都计算一个单调的实值函数$f:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$。(因此每条线储存的是一个实数。)当然,formula的输入输出必须都是$0$和$1$。$f$的MRF复杂度即为计算$f$的formula所需要的最少的门的个数。

一般的计算模型中,一个随机的$n$个变量的函数大约需要$2^n$的复杂度才能计算。但是对于这三个模型,任何单调函数都有$(1.5+o(1))^n$的复杂度上界Applebaum和Nir构造了一个$(1.5+o(1))^n$复杂度的秘密共享机制;本文发现这个构造可以转化为$(1.5+o(1))^n$复杂度的FOS和MRC。

本文证明了单调${\sf NP}$中存在一个FOS复杂度和MRF复杂度都至少是$2^{\Omega(n/\log^2 n)}$的函数。所以,如果我们希望通过改进FOS和MRF的复杂度上界来证明秘密共享复杂度上界,那么这一做法不可能比$2^{O(n/\log^2 n)}$更优。

PCPs and Instance Compression from a Cryptographic Lens

因为我太懒了所以只讲PCP,不讲instance compression。考虑一个${\sf NP}$中的问题$L$,假设它的输入长度比witness长度要大很多。(例如:$L$的输入是一个大小为$n^{\omega(1)}$的电路,witness是它的一个SAT assignment。注意这里的witness长度只有$n$。)我们希望构造一个常数询问的PCP,且PCP证明的长度只和witness长度有关,和输入长度无关。(在上面那个例子中,我们希望PCP证明的长度为${\rm poly}(n)$。)Fortnow和Santhanam证明了除非${\sf NP}\subseteq{\sf coNP}_{/{\rm poly}}$,否则这样的PCP是不存在的。

但是,我们可以这样放宽PCP的要求:原来的PCP要求$x\not\in L$时不存在任何合法的证明;现在我们只需要$x\not\in L$时,任意多项式时间的malicious prover都无法生成一个合法的证明。在一些密码学的假设下,这样的PCA(“probabilistic checkable argument”)是存在的!本文的主要贡献是:基于LWE构造了一个各种参数更优的PCA。本文主要用到的技术是JKKZ的SNARG for ${\sf P}$。

视频中提到了一个很有意思的问题。众所周知,PCP和近似问题的复杂度(hardness of approximation)有关。我们能否利用文章中构造出来的PCA证明一些(目前无法被PCP证明出来的)近似问题的复杂度下界?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter