课程笔记 - Intro to CS W1
Modern Cryptography
传统密码学要求两人拥有一套只有他们知道的密钥，然后利用这个密钥来加密信息。若第三者截获了加密信息，则因为不知道密钥而无法解密。
引子：如何使用完全数学的方法，玩一个两个人的游戏，使得两个人的获胜概率相等。
博弈论：这是不可能的，根据 Zermelo 定理，总有一个人有必胜策略。
解：Alice 随机生成两个 $4k+3$ 型素数 $p,q$，令 $n=pq$，把 $n$ 告诉 Bob。然后 Alice 随机一个数 $x\in [1,n)$，并告诉 Bob 以下两个数之一：$x^2\bmod n$ 或 $-x^2\bmod n$。Bob 需要指出 Alice 告诉他的是 $x^2\bmod n$ 还是 $-x^2\bmod n$，若猜对则 Bob 赢，否则 Alice 赢。
问题：一对互不认识的陌生人 Alice 和 Bob 如何进行加密通信？
信息论：这是不可能的，因为陌生人之间没有任何共识，任何一个第三方拥有和他们同等的初始信息。
Diffie & Hellman：
我们确定一个质数 $p$ 以及其一个原根 $g$ 作为公开信息，然后 Alice 和 Bob 分别自己随机生成一个数 $a,b$ 作为私密信息。
接下来，Alice 向 Bob 发送 $A=g^a\bmod p$，而 Bob 向 Alice 发送 $B=g^b\bmod p$，那么有：
因此 Alice 和 Bob 此时可以获得一个共识 $C=B^a\bmod p=A^b\bmod p$，这个 $C$ 就可以被用作他们通信的密钥。
对于外人，由于既不知道 $a$ 也不知道 $b$，所以即使知道了 $A,B$，也无法算出密钥 $C$。
这被认为是现代密码学的开端。
在上面两个例子中，所谓的“公平性”和“安全性”都不是绝对的，如果某人（第一个例子中的 Bob 或第二个例子中的第三方）拥有无穷的算力，就可以破解。所以这和博弈论/信息论并不矛盾，只是我们当今的计算机算力保证了其安全性或公平性（如果量子计算机出现，情况可能不一样）。
问题（Millionaires’ Problem）：Alice 和 Bob 各有一个数 $a,b$，他们希望在不告知对方自己的数的情况下，比较 $a,b$ 的大小。
假设有一个中间方，该问题有如下解法：将中间方看成一个长度为 $N (a,b
下面我们要去掉这个中间方，可以转化为解决如下问题：
问题（Oblivious Transfer）：Alice 有一个长度为 $N$ 的数组 $x_1,\ldots,x_n$，Bob 要访问其中某个下标处的值，如何在满足 Alice 不知道这个下标，且 Bob 不知道数组其余值的情况下做到这一点。
解决：首先简单介绍一下 RSA：
RSA 需要两个素数 $p,q$，令 $n=pq$，则 $\varphi(n)=(p-1)(q-1)$。寻找一个满足 $\gcd(e,\varphi(n))=1$ 的 $e$，这样就会存在一个 $d$ 使得 $ed\equiv 1\bmod\varphi (n)$。其中 $e,n$ 为公钥，$d$ 为私钥。加密信息 $c$ 时只需要计算密文 $c^e\bmod n$，而解密密文 $x$ 时只需要计算 $c=x^d\bmod n$。
回到原问题。首先 Alice 生成一组 RSA 密钥，将 $e,n$ 告知 Bob（$d$ 为私密信息）。然后 Alice 随机 $N$ 个数 $y_1,\ldots,y_n$，将它们发送给 Bob。
接下来，Bob 随机一个数 $k$（作为私密信息），假设它要访问的下标是 $b$，那么令 $v=(y_b+k^e)\bmod n$，将 $v$ 发送给 Alice。
接下来，Alice 计算 $z_i=(v-y_i)^d\bmod n$，并把 $z_i+x_i$ 发送给 Bob。
最后，Bob 知道 $z_b=k\bmod n$，因此 $(z_b+x_b)-k$ 就是他要访问的信息。
Millionaires’ Problem 是 Multiparty Computation（多方安全计算）的一个例子。
Quantum Computing
这段可能有点民科，因为是根据课件自己理解的。
薛定谔的猫。
考虑一个二维平面，如果说经典物理研究的状态只包含 $(1,0),(0,1)$ 两种，那么一个量子所处的状态就可能是单位圆位于第一象限的整个部分，考虑状态 $(x,y)$，它表示在观测后有 $x^2$ 的概率为 $(1,0)$，有 $y^2$ 的概率为 $(0,1)$。
$n$ 维情况也是类似。
下面介绍一个具体例子。
问题（Simon’s Problem）：设 $S$ 是 $\mathbb F_2$ 下 $n$ 维向量集合。考虑函数 $f:S\to \mathbb R$，满足 $f(x_1)=f(x_2) (x_1\ne x_2)$ 当且仅当 $x_1+x_2=s$。求 $s$。
这里采用的方法可以用一个自然科学中的比喻：为了确定某种晶体的结构，科学家们可以用 X 射线照射它，晶体的内部结构可以根据 X 射线衍射的结果推测出来。
在这里，我们考虑一个（广义的）二维平面 $S\times\mathbb R$，并如下定义一个函数 $B(y,z) (y\in S,z\in \mathbb R)$：对于固定的 $y$，我们枚举每一个 $x\in S$，并给 $B(y,f(x))$ 加上值 $\dfrac{1}{\sqrt{2^n}}(-1)^{x\cdot y}$，注意 $x\cdot y=\operatorname{popcount}(x\land y)\bmod 2$。
Remarks：对 OIer，事实上你可以认为对于确定的 $z$，我们令 $A(x)=[f(x)=z]$，则 $B(,z)=\dfrac{1}{\sqrt{2^n}}\operatorname{FWT}(A())$ 只是做了一次 FWT。
现在我们定义 $|B(y,z)|$ 是 $(y,z)$ 这个点的亮度，那么有许多亮点是随机分布的，但是我们可以发现有一些点比其他点要更亮一些。
若 $y\cdot s=0$，则 $(-1)^{x\cdot y}=(-1)^{(x+s)\cdot y}$，所以所有的 $(y,f(x))$ 就会更亮，这一系列亮点的 $y$ 相同，可以姑且称之为亮条纹。
反之，$y\cdot s=1$ 时所有 $B(y,f(x))=0$，就是暗条纹（一种类比的说法）。
那么所有亮条纹对应的 $y$ 就是那些满足 $y\cdot s=0$ 的点了。如果我们能够求出 $n-1$ 个线性无关的 $y$，设它们张成空间 $S’$，则 $S’$ 的正交补 $S’’$ 就是仅包含 $0,s$ 的空间，这样我们就知道了 $s$。
但在普通计算机上这是个指数级别的算法（如同暴力一样），而在量子计算机上这将有快速方法，不过上课没讲，咱也不会。
之后，Shor(1994) 用类似的方法提出了大数分解的量子算法。Shor 此后还解决了量子计算机的 error-correction 问题，这吸引物理学家和计算机科学家们真正关注量子计算这一领域。
参考资料
计算机入门 Lec 1.