Cryptography
encryption scheme 固定信息的长度和密钥的长度，(E,D)满足对所有密钥\(k\)，\(D_k(E_k(x))=x\)。
perfect secrecy 对每一对信息，若密钥等概率随机，加密后的分布相同。可以想象，对于攻击者来说，如果密钥没有任何信息，那么拿到加密后的结果，所有信息概率相等。以下介绍满足perfect secrecy的one time pad：密钥与信息等长，加密方式为按位异或。注意到一个密钥只能使用一次，即不能加密超过一倍长度的信息，否则将密文异或即可得到信息异或。另外可以观察到，如果要求perfect secrecy，密钥的长度不低于信息的长度。证明：设信息长度m，密钥长度n，设存在\(E_k(x)=y\)，那么有\(2^m\)个\((x,k)\)满足\(E_k(x)=y\)，即有\(2^m\)个\((x,k)\)满足\(D_k(y)=x\)，但至多只有\(2^n\)个\(k\)）
P=NP下不存在密码学 如果\(P=NP\)，对于任意密钥长度\(n\)小于信息长度\(m\)的\((E,D)\)，对任意\(x_0\in \{0,1\}^m\)，存在多项式时间算法\(A\)满足：若密钥和\(x_1\)等概率随机，\(A\)算法输入加密后结果，分辨信息为\(x_0\)和\(x_1\)的正确率不低于\(3/4\)。注意尽管\(P=NP\)，也无法得到随机密钥下\(x_0\)加密后结果的分布。令\(A\)直接判定输入是否是某个密钥加密\(x_0\)后的结果，如果是就认为是\(x_0\)，只需证明在\(x_1\)的情况下正确率不低于\(1/2\)。设\(S\)为某个密钥加密\(x_0\)后的结果集合，类似perfect secrecy种证明，如果固定密钥，由于\(m<n\)，\(|S|\le 2^m\)，随机\(x_1\)加密结果落在\(S\)中的概率不超过\(2^m/2^n\le 1/2\)，因此密钥和\(x_1\)都随机的情况下，\(x_1\)加密后结果属于\(S\)的概率不超过\(1/2\)。
one-way function one-way function定义为多项式时间可计算的单射函数，且任意算法在多项式时间内求逆正确率可忽略。one-way function存在的条件比\(P\ne NP\)要强，因为若\(P=NP\)可找出certificate，得到函数输入。可能的one-way function的例子：将两个质数映射到乘积；RSA函数：对\(n,e\)，将\(x\)映射到\(x^e \mod n\)；离散对数：对\(n,a\)，将\(x\)映射到\(a^x \mod n\)（注意这个问题存在worst-case to average-case reduction，即如果它hard on worst-case，那么hard on average-case，因为可以对于无法求解的\(a^x=c\)，如果不满足hard on average，即只有极少数难解，则容易找到\(d\)使得\(c^d\)可解出\(a^y\)，那么\(dx=y\)，可解决全部问题）；Rabin function：模数为两质数乘积的二次剩余。
universal one-way function 首先，如果存在one-way function，那么存在运行时间\(O(n^2)\)的one-way function：设one-way function\(f\)的运行时间\(O(n^a)\)，那么将输入均分成\(n^t\)段，输出每段作为输入的结果再拼起来，复杂度\(O(n^t(n^(1-t))^a)\)；然后，如下函数一定是one-way function：将长度为\(n\)的读入均分成\(\log n\)段，第\(i\)段作为图灵机\(M_i\)的输入并在\(O(n^2)\)时间内终止，将结果拼接起来，设上述\(O(n^2)\)的one-way function为\(M_t\)，当\(n\ge 2^t\)时，输出的第\(t\)段无法求逆，整体也无法求逆。
secure pseudorandom generator \(G\)将长度为\(n\)的串映射到\(l(n)\)的串，且对于任意多项式时间的随机算法\(A\)，\(A(G(U_n))\)的分布与\(A(U_{l(n)})\)的分布差距可忽略（\(|Pr(A(G(U_n))=1)-Pr(A(U_{l(n)})=1)|\le \epsilon\)）。可以想象，在任意算法看来，安全伪随机生成器得到的串与随机串无异，那么可以用来作为one-time pad的密钥。因此用较短的密钥解决加密问题，就可以转化为找到伪随机生成器的问题。（semantic secure的定义是对于任意信息的分布，任何多项式时间随机算法，解密出加密的结果的概率，不超过（高出的可忽略），只读入加密结果长度的多项式时间随机解密算法）接下来几个定理都是为了证明，one-way function存在可推导出secure pseudorandom generator，之后还会讨论average-case hardness可推导出peudorandom generator，都说明了难解的函数与伪随机之间的关系。
unpredictability implies pseudorandomness 可被\(B\)预测定义为，在种子均匀随机和位置\(i\)均匀随机下，由种子生成的串的前\(i-1\)个字符作为\(B\)的读入，\(B\)的输出与第\(i\)个字符相同的概率不可忽略（与\(1/2\)的差不可忽略）。在random generator中，如果存在\(A\)，以随机串和伪随机串为读入的输出为1的概率差超过\(\epsilon\)，那么存在\(B\)，预测成功的概率不低于\(1/2+\epsilon/l(n)\)。证明如下：不妨设\(A\)在伪随机下输出1的概率更大，令\(B\)的过程如下，将第\(i\)个字符及之后用随机串填充后的串作为\(A\)的输入，若输出1，则输出该输入的第\(i\)位，否则输出第\(i\)位的补。直观感受是，如果\(A\)在该串下运行结果是1，那么该串更有可能是伪随机串。hybrid argument就是利用差分来计算概率，令\(p_i\)为将伪随机串的第\(i\)位以后改为纯随机串作为\(A\)的输入，输出结果为\(1\)的概率，\(p_l-p_0>\epsilon\)，另外由于\(p_{i-1}=1/2p_i+1/2Pr[A=1|WrongRandom]\)，因此\(B\)对第\(i\)位的预测正确率\(1/2p_i+1/2Pr[A=0|WrongRandom]=1/2+p_i-p_{i-1}\)，因此随机\(i\)下预测正确率额不低于\(1/2+\epsilon/l(n)\)。
Goldreich-Levin Theorem 如果存在one-way function\(f\)满足\(|f(x)|=|x|\)，那么对于所有多项式时间随机算法\(A\)，在\(x\)和\(r\)均匀随机的情况下\(A(f(x),r)=x\odot r\)的正确率可忽略，其中\(a\odot b\)指的是\(\sum a_ib_i \mod 2\)。这个定理描述的是unpredictability，因此可以说明存在\(l(n)=n+1\)的secure pseudorandom generator。证明思路是，如果\(A\)能以较高的概率，对部分\(x\)得到一些正确的\(A(f(x),r)=x\odot r\)，那么就可以在只给出\(f(x)\)下构造\(r\)并利用\(A\)还原出\(x\)，与one-way function矛盾。首先由于\(f\)正向可计算，因此可以检验算出的\(x\)是否正确，那么可以多次重复提高正确率。设\(A\)正确率超过\(1/2+\epsilon\)，那么存在\(\epsilon/2\)个“好的”\(x\)，每个好的\(x\)有\(1/2+\epsilon/2\)比例的\(r\)可用\(A\)计算出正确答案。若\(1/2+\epsilon/2\)为\(0.9\)，那么可以利用\(x\odot(a \oplus b)=(x\odot a)\oplus (x\odot b)\)，随机一些\(r\)，利用\(A(f(x),r)\)和\(A(f(x),r \oplus e^i)\)求出\(x\)的第\(i\)位，每次正确率0.8，多次重复取结果的多数，利用随机变量和的方差等于方差的和，再用chebychev's inequality使得错误率不超过\(1/10n\)，整个串正确率0.9（每位分别求，或所有位都用同一组r一起求，在种情况下均可，但在下述情况下只能一起求）。而\(1/2+\epsilon/2\)的情况下，由于\(r\)和\(r\oplus e^i\)并不独立，可能几乎没有\(r\)可正确求出第\(i\)位，但由于方差的和等于和的方差只要求两两独立，设最终需要\(m\)个随机的\(r\)，可以只随机\(\log m\)个\(s\)，令\(r_i\)为\(i\)对应二进制位的\(s\)的异或，并且\(A(f(x),r)\)可直接通过这些\(A(f(x),s)\)得到。这里用到enumerate all guesses的技巧，先随机出\(\log m\)个串\(s\)，直接用\(O(m)\)枚举所有\(A(f(x),s)\)的值，算出\(A(f(x),r)\)，再用\(A\)查询\(A(f(x),r\oplus e^i)\)，每个\(r\)的正确率位\(1/2+\epsilon/2\)，尽管只是两两独立。这样只需要令\(m=O(n/\epsilon^2)\)，即可使得每位错误率不超过\(1/10n\)。
Goldreich-Levin Theorem and list decoding 原定理的证明就是要求在\(A(y,r)=x\odot r\)概率超过\(1/2+\epsilon\)时，找到\(B\)满足\(B(y)=x\)。实际上\(B\)通过调用\(A\)可以得到\(x\)经过污染的Walsh-Hadamard Code。由于Walsh-Hadamard Code距离不超过\(1/2\)且可任意local list decode，因此存在一个算法能通过把\(A\)作为black box调用解码出\(x\)。
arbitrary large secure pseudorandom generator 利用Goldreich-Levin Theorem，可以证明，只要存在\(|f(x)|=|x|\)的one-way function\(f\)，则存在对任意\(c\)存在\(l(n)=n^c\)的pseudorandom generator。令\(G\)将\((x,r)\)映射到\((r,f^l(x)\odot r,f^{l-1}(x)\odot r,...,f(x)\odot r\)，\(f^l(x)\)表示迭代\(l\)次。假设\(G\)可被预测，下证违反Goldreich-Levin Theorem。由于\(f\)是排列，因此对任意\(i\)和\(y\)，存在\(x'\)满足\(f^i(x')=y\)。那么给出\(f(x)=y\)，随机\(r\)和\(i\)，设\(y=f^i(x')\)，那么\(x=f^{i-1}(x')\)，预测\((r,f^{l-i}(y)\odot r,...,y \odot r)\)，可得\(x\odot r\)。
pseudorandom generator and derandomization 伪随机的存在，可以使得随机bit减少，再将随机改为枚举，即可实现derandomization，因此one-way function可蕴含\(BPP\subseteq DTIME(2^{n^\epsilon})\)。实际上在derandomize的时候，运行的程序并不是任意多项式复杂度的，并且generator生成的串相对原串的长度可能是指数级的，因此也不要求generator在多项式复杂度内，之后介绍的psedorandom generator更适用于derandomize。
pseudorandom function family 对每个\(n\)，\(2^n\)个将所有长度为\(n\)的串映射到长度为\(n\)的串的函数（总共有\((2^n)^{2^n}\)个）称为functions family。对每个\(n\)，和任意多项式时间随机算法\(A\)，若在family中随机选择一个函数作为\(A\)的oracle(black box)，与任意随机生成一个函数作为oracle，输出1的概率差距可忽略，则称为pseudorandom function family。直观感受是大大减少了随机一个函数的工作量，原本需要\(n2^n\)个bit，利用pseudorandom function family则只需要\(n\)个bit。在应用的加密系统中，只需要事先交流family中函数的编号（n个bit），此后每次传输\(x\)可利用one time pad加密为\((r,f(r)\oplus r)\)；再验证身份时，只需要将\(x\)的信息附上\(f(x)\)。
pseudorandom function family and generator 如果存在pseudorandom function family，那可将任何\(k\)映射到第\(k\)个函数在\(1,2,...,l(n)\)处的值，得到\(nl(n)\)的generator。下证如果存在\(l(n)=2n\)的pseudorandom generator\(G\)，则一定存在pseudorandom function family。令\(G_0(x)\)为\(G(x)\)后\(n\)位，\(G_1(x)\)为\(G(x)\)前\(n\)位，令family里的第\(k\)个函数\(f_k(x)=G_{x_n}(G_{x_{n-1}(...G_{x_1}(k)))\)，设\(A\)能区分\(f\)和随机函数，要构造\(B\)能区分\(y\)是\(G\)生成的结果还是随机串。对\(A\)“自适应”地选取\(G_0,G_1\)的点值，即每次访问\(f_k(x)\)，实际是确定了一部分\(G_0,G_1\)的值，未确定的\(G_0,G_1\)在之后访问\(f_k(x)\)可任选而不会有矛盾。利用hybrid argument，令\(p_i\)为前\(i\)次访问\(G_0,G_1\)的点值都使用纯随机函数确定，之后都使用\(G\)确定，最终\(A\)的运行结果的期望。设\(A\)确定了\(T\)次\(G\)，\(p_0-p_T\ge \epsilon\)，\(E|p_i-p_{i-1}|\ge \epsilon/T\)。令\(B\)的算法如下，随机\(i\)，运行\(A\)，前\(i-1\)次均随机串确定，第\(i\)次确定的\(G\)用\(y\)确定，此后都用\(G\)确定，返回\(A\)的结果。那么\(y\)是否是\(G\)的结果分别对应输出1的概率\(p_i\)和\(p_{i-1}\)。
crypto and machine learning 机器学习的一个目标是给定\(f:\{0,1\}^n\rightarrow \{0,1\}\)在一些位置的值，找到\(f\)的描述方式，如较小的电路等。利用Goldreich-Levin Theorem的构造，只要one-way function存在，这个函数虽然计算的电路很小，但不存在任何算法计算出正确答案有非平凡的正确率。