Revision | 密码学基础（下）

• Public Key Encryption
• Computational Hardness and Public-Key Encryption
  • Number Theoretic Hardness
  • Lattice Based Hardness
• Advanced Techniques
  • Identity-Based encryption
  • Fully Homomorphic encryption
  • Digital Signature
  • Zero-Knowledge Proof
  • Secure Multi-Party Computation
• Appendix: Techniques from Homeworks

Public Key Encryption

定义 1.1（Public Key Encryption Scheme）. 一个公钥加密方案包含以下资料：

• 算法 $\textsf{Gen}(1^\lambda) \rightarrow (pk, sk)$；
• 算法 $\textsf{Enc}(pk, m) \rightarrow c$；
• 算法 $\textsf{Dec}(sk, c) \rightarrow m$。

谈及公钥加密方案时，默认它是正确的，即 $\textsf{Dec}(sk, \textsf{Enc}(pk, m)) = m$。

接下来定义公钥加密方案的安全性。注意因为公钥 $pk$ 是众所周知的，所以公钥加密是计算上不可区分的自然是 CPA 安全的。

定义 1.2（Indistinguishability of PKES）. 考虑如下的 indistinguishability game：

1. Challenger 采样 $(pk, sk) \leftarrow \textsf{Gen}(1^\lambda)$ 并公开 $pk$；
2. $\mathcal{A}$ 选择一对同样长度的消息 $(m_0, m_1)$ 发送给 challenger；
3. Challenger 采样 $b\leftarrow {0, 1}$，发送 $\textsf{Enc}(pk, m_b)$ 给 $\mathcal{A}$；
4. $\mathcal{A}$ 给出猜测 $b’$。

称 Adversary $\mathcal{A}$ 赢下了 indistinguishability game（事件 $\textsf{PrivK}_{\mathcal{A}, \Pi}^{eav}(1^\lambda)$）若 $b’ = b$。称 $\Pi$ 是不可区分的，若对于任意 p.p.t 的算法 $\mathcal{A}$，存在可忽略的函数 $\mathrm{negl}$ 使得：

$$
\Pr[\textsf{PrivK}_{\mathcal{A}, \Pi}^{eav}(1^\lambda)] \leq \frac 12 + \text{negl}(\lambda)
$$

进一步，说 $\Pi$ 是 CCA 安全的，若 $\mathcal{A}$ 拥有对 $\textsf{Dec}(sk, \cdot)$ 的 oracle 访问。

一个事实是，如果有一个安全的私钥加密方案和某种密钥交换机制（双方根据自己的公钥和私钥，计算一个相同的 $k$，这个 $k$ 近乎随机），就能组装一个安全的公钥加密方案，以得到一种公钥加密方案构造的范式，这种方式当然还有一些好处，比如比一般构造的公钥加密方案高效等。首先定义需要的原素：密钥封装机制。

定义 1.3（Key Encapsulation）. 一个密钥封装机制 $\Pi$ 包含以下资料：

• 算法 $\textsf{Gen}(1^\lambda)\rightarrow (pk, sk)$；
• 算法 $\textsf{Encap}(pk)\rightarrow \{k, cap(k)\}$；
• 算法 $\textsf{Decap}(sk, cap(k))\rightarrow k$。

默认这东西是正确的。其安全性是任意的 p.p.t Adversary $\mathcal{A}$ 在看到 $pk$ 和 $cap(k)$ 之后，不能以不可忽略的概率区分 $k$ 和随机数。细节需要用 security game 定义，这里节省篇幅不写。

而密钥封装机制可以用如下的理论工具实现：

定义 1.4（Trapdoor Permutation）. 由某个算法 $\textsf{Gen}(1^\lambda)$ 给出的二元组 $(f, t)$ 被称为一个 trapdoor permutation，若

• $f: \mathcal{D}\rightarrow \mathcal{D}$，其中 $\mathcal{D}$ 接近 $\{0, 1\}^\lambda$；
• 存在高效算法 $\textsf{invert}: (t, f(x))\mapsto x$；
• 对于任意 p.p.t 的 adversary $\mathcal{A}$，$\Pr[\mathcal{A}(f, f(x))\rightarrow x]\leq \mathrm{negl}(\lambda)$。

定理 1.1. 存在 Trapdoor Permutation 便存在 Key Encapsulation。

构造. 令

• $\textsf{Gen}(1^\lambda)$ 生成 $(f, t)$；
• $\textsf{Encap}(f) \rightarrow (h(k), c = f(k))$，其中 $h(k)$ 是一个 hardcore function，如 $f$ 的一个 hardcore predicate，可以是一个安全的 hash 函数，最理想的建模是一个 random oracle。
• $\textsf{Decap}(t, c) \rightarrow h(\textsf{invert}(t, c))$。

根据 hardcore predicate 的定义，即便给定 $f, f(k)$，$h(k)$ 确实和随机生成的数不可区分。

$\blacksquare$

定理 1.2. 存在 Key Encapsulation 和安全的 Private Key Encryption Scheme 便存在安全的 Public Key Encryption。

构造. 串联这两个原素即可。让 Private Key Encryption 用 Key Encapsulation 算出的 $k$ 做密钥。

安全性证明考虑一个 Hybrid World $W’$，即用于 Public Key Encryption 的密钥真的是随机生成的。$W’$ 和 real world $W$ 依 key encapsulation 的安全性不可区分，$W’$ 中安全性游戏的 advantage 依 private key encryption 的安全性是可忽略的。

$\blacksquare$

Computational Hardness and Public-Key Encryption

本节基于几个困难性假设构造一些公钥加密方案。

Number Theoretic Hardness

假设 2.1.1（Dlog Assumption）. 离散对数的求解是困难的，即给定一个由 $g$ 生成的有限群 $G$，对于任意的 p.p.t adversary $\mathcal{A}$

$$
\Pr_{(G, g)\leftarrow \textsf{Gen}(1^\lambda), t\leftarrow {0, …, |G| - 1}}[\mathcal{A}(G, g, g^t)\rightarrow t] \leq \mathrm{negl}(\lambda)
$$

这里的群除了采用 $\mathbb{Z}_N^*$ 之类的群之外，还可以用椭圆曲线群。

假设 2.1.2（Diffie-Hellman Assumption）. CDH 问题和 DDH 问题是困难的，即：

• Computational Diffie-Hellman Assumption. 对于任意 p.p.t adversary $\mathcal{A}$，$\Pr[\mathcal{A}(g, g^x, g^y)\rightarrow g^{xy}]\leq \mathrm{negl}(\lambda)$；
• Decisional Diffie-Hellman Assumption. $(G, g, g^x, g^y, g^{xy}) \approx_c (G, g, g^x, g^y, g^r)$，其中 $r$ 为随机数。

这里我们使用了记号 $\approx_c$，它表示 computational indistinguishable。以后我们会常常使用这个简写。注意如果能计算离散对数，则 DHA 都会迎刃而解。而这里群的阶数是有讲究的。我们将证明：

定理 2.1.3（特殊阶群上的 DlogA 和 DDHA）. 若 $|G| = O(2^\lambda)$ 满足：

• $|G|$ 的质因子大小均为 $\lambda$ 的多项式级别，则存在高效算法求 $G$ 上的离散对数；
• $|G|$ 存在一个 $\lambda$ 的多项式级别的质因子，则存在高效算法能解决 DDH 问题。

证明. 只需要证明如下核心结论：对于多项式大小的质因子 $p_i$ 和任意的 $t\leq \alpha_i$（$|G| = \prod p_i^{\alpha_i}$），存在高效算法求 $(\log_g a) \bmod p_i^t$。注意：

• 若 $t = 0$. $\log_g a \bmod p_i^0 = 0$ 是自然成立的。
• 若已经知道了 $r = \log_g a\bmod p_i^{t - 1}$. 那么 $\log_g a \bmod p_i^t$ 无非是 $r + d\cdot p_i^{t - 1}$，其中 $d < p$。这里因为 $p_i$ 大小只有多项式级别，可以硬枚举 $d$ 检验。

要判断 $\log_g a \bmod p_i^t = r$ 是否成立，只需要查看 $(a / g^r)^{|G| / p_i^t}$ 是否是单位元 $1$ 即可。此时：

• 若所有质因子大小都是多项式级别，可以求出所有的 $\log_g a \bmod p_i^{\alpha_i}$，用 CRT 合并立即得到 $\log_g a$。
• 若有一个质因子 $p_i$ 大小为多项式级别，则可以求出 $x\bmod p_i, y\bmod p_i$ 和 $r\bmod p_i$。判断 $r$ 和 $xy$ 是否同余，即可高概率（$1 - 1 / p_i$）成功解决 DDH。

$\blacksquare$

若 DDHA 成立，拿着一个 random oracle $h$，可以构造 CCA 安全的密钥封装机制：

• $\textsf{Gen}(1^\lambda) = (pk = (G, g, g^x), sk = x)$，其中 $x$ 均匀随机采样；
• $\textsf{Encap}(pk) \rightarrow (h((g^y)^x), g^y)$，其中 $y$ 均匀随机采样；
• $\textsf{Decap}(sk, c)\rightarrow h(c^x)$。

选 One-time Pad 作为相应的 Private Encryption Scheme，得到一套基于 Diffie-Hellman 的加密方案：

DH Based Public Key Encryption.

• $\textsf{Gen}(1^\lambda) \rightarrow (pk = (G, g, g^x), sk = x)$，其中 $x$ 均匀随机采样；
• $\textsf{Enc}(pk, m) \rightarrow (g^y, h(g^{xy})\cdot m)$，其中 $y$ 均匀采样；
• $\textsf{Dec}(sk, (c_k, c_m)) \rightarrow h(c_k^x)^{-1}\cdot c_m$。

另外还有一些假设，也能推出相应的加密方案，比如：

假设 2.1.4. 质因数分解是困难的。即令 $p, q$ 在 $\lambda$ 位素数中产生，有对于任意 p.p.t adversary $\mathcal{A}$ 都有

$$
\Pr_{p, q\leftarrow \mathrm{Primes}(\lambda)}[\mathcal{A}(p, q)\rightarrow (p, q)] \leq \mathrm{negl}(\lambda)
$$

注意求 $\varphi(N)$ 和质因数分解等难。因为若 $N = pq$，有 $p + q = N - \varphi(N) + 1$，便获得了两个方程，可以解出 $p, q$。

基于这个直觉，提出 RSA 假设和强 RSA 假设：

假设 2.1.5（RSA Assumption）. 给定 $(N, e, m^e)$，则 $m$ 不易求，即对于任意 p.p.t 的 adversary $\mathcal{A}$ 都有

$$
\Pr_{p, q\leftarrow \mathrm{Prime}(\lambda), N = pq}[\mathcal{A}(N, e, m^e)\rightarrow m]\leq \mathrm{negl}(\lambda)
$$

假设 2.1.6（Strong RSA Assumption）. 给定任意的 $N, y$，则任意非平凡的 $(m, e)$ 使得 $m^e = y$ 都是难求的。即

$$
\Pr_{p, q\leftarrow \mathrm{Prime}(\lambda), N = pq}[\mathcal{A}(N, y) \rightarrow (m, e) \wedge e\ne 1 \wedge m^e = y] \leq \mathrm{negl}(\lambda)
$$

基于此，有如下加密方案：

Encapsulation RSA.

• $\textsf{Gen}(1^\lambda) \rightarrow (pk = (N = pq, e), sk = d = e^{-1}\bmod \varphi(N))$；
• $\textsf{Enc}(pk, m)\rightarrow (r^e \bmod N, h(r)\oplus m)$，其中 $r$ 从 $\mathbb{Z}_N^*$ 中均匀随机采样；
• $\textsf{Dec}(sk, (c_k, c_m)) \rightarrow h(c_k^d \bmod N)\oplus c_m$。

根据 RSA Assumption，这里 $r$ 是不好求的，所以 $h(r)$ 把 $m$ 给 one-time pad 住实现安全加密。

还有一套加密方案依赖于二次剩余。考虑 $N = pq$，其中 $p, q$ 都是安全素数（i.e. $p = 2p’ + 1, q = 2q’ + 1$），定义 $a$ 的 Jacobi 记号为：

$$
\left(\frac{a}{N}\right) = \left(\frac ap\right) \left(\frac aq\right)
$$

其中若 $p$ 是素数，Jacobi 记号就是 Legendre 记号

$$
\left( \frac ap\right) = \begin{cases}
0 & a = 0 \
1 & \exists x\in \mathbb{Z}_p^*, a = x^2 \
-1 & \text{otherwise}
\end{cases}
$$

定义 $\mathbb{QR}_p$ 为模 $p$ 的全体二次剩余。

假设 2.1.7（Quadratic Remainder Assumption）. 定义 $\mathbb{QR}_N := \{a\in \mathbb{QR}_p\wedge a\in \mathbb{QR}_q : a\in \mathbb{Z}_N^*\}$ 和 $\text{pseudo-}\mathbb{QR}_{N} := \{a\notin \mathbb{QR}_p\wedge a\notin \mathbb{QR}_q : a\in \mathbb{Z}_N^*\}$。注意 $a$ 的 Jacobi 记号是 $1$ 则它要么是 $\mathbb{QR}_N$ 的元素，要么是 $\text{pseudo-}\mathbb{QR}_N$ 的元素。二次剩余假设是说：如果不知道 $p, q$ 则 $\mathbb{QR}_N$ 和 $\text{pseudo-}\mathbb{QR}_N$ 是难以区分的。（如果知道 $p, q$，则 Cipolla 算法之类的东西可以容易地求二次剩余）

由此得到以下的加密方案：

Rabin Encryption.

• $\textsf{Gen}(1^\lambda)\rightarrow (pk = (N = pq, g\in \text{pseudo-}\mathbb{QR}_N), sk = (p, q))$；
• $\textsf{Enc}(pk, m) \rightarrow r^2 \cdot g^m$，其中 $r$ 在 $\mathbb{Z}_N^*$ 中均匀随机采样，$m \in \{0, 1\}$ 为欲加密的消息；
• $\textsf{Dec}(sk, c)$ 检查 $c$ 是否属于 $\mathbb{QR}_N$，便可知道 $m$ 的值。

Lattice Based Hardness

上面讲的数论上的困难性基本上都挡不住量子计算机。而基于格的困难性暂时还能挡得住量子计算机。

定义 2.2.1（Lattice）. 给定 $\mathbb{R}^n$ 上的一组基 $\boldsymbol{v}_1, …, \boldsymbol{v}_n$。则

$$
L := \{a_1\boldsymbol{v}_1 + \cdots + a_n \boldsymbol{v}_n: a_i\in \mathbb{Z}\}
$$

称为 $\mathbb{R}^n$ 上的一个格（Lattice）。

格上的 SVP（找 $L$ 中的最短向量）、CVP（找 $L$ 中 $\boldsymbol{v}$ 的最近邻） 之类的问题是众所周知的难题。我们这里主要使用以下的假设

假设 2.2.1（Learning with Error Assumption）. 随机取 $\boldsymbol{s}\in \mathbb{Z}_p^n$，$\mathbf{A}\in \mathbb{Z}_p^{n\times m}$，对于非常短的 $\boldsymbol{\varepsilon}$，有

$$
(\mathbf{A}, \mathbf{s}^\top \mathbf{A} + \boldsymbol{\varepsilon}^\top)\approx_c (\mathbf{A}, \boldsymbol{r}^\top)
$$

其中 $\boldsymbol{r}^\top$ 均匀随机。

这本质上就是 CVP 不好做。以此得到可以加密一位消息的加密方案：

LWE Based Public-Key Encryption.

• 私钥为 $\boldsymbol{s}$，公钥为 $\mathbf{A}, \boldsymbol{s}^\top \mathbf{A} + \boldsymbol{e}^\top$，其中 $\boldsymbol{e}$ 在方差很小的正态分布中采样；
• $\textsf{Enc}(pk, m) \rightarrow (\mathbf{A}\boldsymbol{r}, (\boldsymbol{s}\mathbf{A} + \boldsymbol{e})^\top \boldsymbol{r}’ + \frac{p}{2}m’ + e’)$，其中 $e’$ 非常小，$r’$ 随机。

在不知道私钥的人眼里看来，$(\boldsymbol{s}\mathbf{A} + \boldsymbol{e})^\top \boldsymbol{r}’$ 均匀随机，将后面的信息都 one-time pad 住了。

Advanced Techniques

Identity-Based encryption

本节讨论所谓的身份加密，即可以任意选择公钥的公钥加密系统。在传统的公钥加密系统中，如果 Alice 想要给 Bob 发送信息，他需要知道 Bob 的公钥是否确实是 Bob 本人的，这就需要第三方签发的证书。我们现在希望把这个机制改成：Alice 只需要 Bob 的名字（比如 bob@email.com）就可以加密密文，而 Bob 在解密需要证明自己是 Bob 才可以解密，具体地，我们需要以下几个函数：

定义 4.1.1（Identity-Based Encryption）. 一个基于身份的加密方案包含以下几个算法：

• $\textsf{Gen}(1^\lambda)\rightarrow (pk, msk)$，称为主公钥和主私钥，对所有人可见；
• $\textsf{Enc}(pk, \mathrm{ID}, m) \rightarrow c$；
• $\textsf{Dec}(sk_{\mathrm{ID}}, c) \rightarrow m$；
• $\textsf{Extract}(msk, \mathrm{ID})\rightarrow sk_{\mathrm{ID}}$。

若任意的 p.p.t adversary $\mathcal{A}$ 无法以不可忽略的优势赢得如下的 CPA Game，则称这个 IBE 是 CPA 安全的：

1. Challenger 生成 $pk, msk$，发送 $pk$ 给 Adversary；
2. Adversary 询问若干个 $\mathrm{ID}_i$，challenger 回答 $sk_{\mathrm{ID}_i}$；
3. Adversary 发送 $m_0, m_1, \mathrm{ID}$，challenger 回复 $c= \textsf{Enc}(pk, \mathrm{ID}, m_b)$；
4. Adversary 询问若干个 $\mathrm{ID}_i$，challenger 回答 $sk_{\mathrm{ID}_i}$；
5. Adversary 猜测 $b$。

这里 $\textsf{ID}$ 和 $\textsf{ID}_i$ 不可重复。

IBE 基本上都是基于所谓的 Pairing，即某种双线性映射的构造的。

定义 4.1.2（Pairing）. 给定两个群 $G, G_T$，他们都同构于某个 $\mathbb{Z}_q$，生成元分别为 $g, g_T$。他们之间的一个 pairing 为一个可以快速计算的映射 $e: G\times G \rightarrow G_T$，满足：

• $e(g, g) = g_T$；
• $e(g^a, g^b) = g_T^{ab}$。

实践中，这两个群都可以在椭圆曲线上找到。

定义这个东西，是希望通信双方拿着 $g^a, g^b$，可以借助一个拿着 $msk = c, pk = g^c$ 的第三方进行密钥交换，算出一个近乎随机的 $g_T^{abc} = e(g^a, g^b)^c$，然后套上一个 Private Key Encryption 实现 IBE。我们考虑以下的假设

假设 4.1.1（Decisional Bilinear Diffie-Hellman Assumption）. 对于同构于 $\mathbb{Z}_q$ 的群 $G, G_T$，pairing $e$ 和生成元 $g, g_T$，有

$$
(G, G_T, e, g, q, g^a, g^b, g^c, g_T^{abc})\approx_c(G, G_T, e, g, q, g^a, g^b, g^c, g_T^{abc})
$$

注意在这种 pairing 里面，“DDH”是不成立的，因为 $e(g^x, g^y) = e(g, g^{xy}) = g^{xy}_T$，据此可以区分 $g^x, g^y, g^{xy}$ 和随机数。

基于此，有如下的 IBE：

Paring-Based IBE.

• $\textsf{Gen}(1^\lambda)\rightarrow (pk = G, G_T, g, g_T, e, g^S, msk = s)$；
• $\textsf{Extract}(msk, \mathrm{ID}) \rightarrow h_{\mathrm{ID}} = H(\mathrm{ID})^{s}$，其中 $H$ 是 random oracle；
• $\textsf{Enc}(pk, \mathrm{ID}, m) = (g^r, H(e(h_{\mathrm{ID}}, g^s)^r)\cdot m)$；
• $\textsf{Dec}(sk_{\mathrm{ID}}, c) = H(e(h_{\mathrm{ID}}^2, g^r))^{-1} \cdot c$。

首先所有的 $sk_{\mathrm{ID}}$ 询问都是没用的，因为我们用 random oracle 保护了 $\mathrm{ID}$。根据 DBDHA，$g^s, h_{\mathrm{ID}} = g^{y_{\mathrm{ID}}}, g^r, H(g_T^{y_{\mathrm{ID}}rs})$ 和 $(g^s, g^{y_{\mathrm{ID}}}, g^r, h(g_T^w))$ 不可区分，后者完全就是随机四元组，因此将 $m$ one-time pad 住。

Fully Homomorphic encryption

如果希望直接用密文做计算而不暴露输入信息，我们就需要加密方案具有某种同态性质，即希望找一个加密方案，对于 $x, y\in R$（$R$ 是一个环），给定 $\textsf{Enc}(x)$ 和 $\textsf{Enc}(y)$，希望能够计算 $\textsf{Enc}(x + y)$ 和 $\textsf{Enc}(xy)$。进而，可以安全地计算 $R$ 上的算术电路。

我们改进 2.2 中所述地 LWE-Based Public Key Encryption 来得到一种全同态加密方案。

首先做一些尝试：考虑公钥 $\mathcal{A}$ 是一个 $n\times (n + 1)$ 的矩阵。令 $sk = \boldsymbol{s}\in \mathbb{R}^n, t = (\boldsymbol{s}, -1)$。

$$
\begin{aligned}
\textsf{Enc}(pk, m) &= \begin{pmatrix}
\mathbf{A} \\
\boldsymbol{s}^\top \mathbf{A} + \boldsymbol{\varepsilon}
\end{pmatrix} + m\mathbf{I} \\
\textsf{Dec}(sk, m) &= \boldsymbol{t}^\top \boldsymbol{c}
\end{aligned}
$$

那么假如有两个密文 $\boldsymbol{c}_1, \boldsymbol{c}_2$，计算

$$
\boldsymbol{t}^\top(\boldsymbol{c}_1 + \boldsymbol{c}_2) = -\boldsymbol{\varepsilon}_1 - \boldsymbol{\varepsilon}_2 + (m_1 + m_2) \boldsymbol{t}^\top
$$

因为 $\boldsymbol{\varepsilon_1}, \boldsymbol{\varepsilon_2}$ 都小，所以容易解密出 $m_1 + m_2$。但计算乘法发现

$$
\begin{aligned}
&\boldsymbol{t}^\top\left(\begin{pmatrix}
\mathbf{A} \\
\boldsymbol{s}^\top \mathbf{A} + \boldsymbol{\varepsilon}_1
\end{pmatrix} + m_1\mathbf{I}\right)\left(\begin{pmatrix}
\mathbf{B} \\
\boldsymbol{s}^\top \mathbf{B} + \boldsymbol{\varepsilon}_2
\end{pmatrix} + m_2\mathbf{I}\right) \\
&= {\color{red} \boldsymbol{\varepsilon}_1 \begin{pmatrix}
\mathbf{B} \\
\boldsymbol{s}^\top \mathbf{B} + \boldsymbol{e}_2
\end{pmatrix}} + m_2\boldsymbol{\varepsilon}_1 + m_1 \boldsymbol{\varepsilon}_2 + m_1m_2 \boldsymbol{t}^\top
\end{aligned}
$$

红色项的大小是 Bound 不住的。解决方法如下：定义 Gadget Matrix 为：

$$
\mathbf{G} = \begin{pmatrix}
1, 2, …, 2^{\log p} & & \\
& 1, 2, …, 2^{\log p} & \\
& & 1, 2, …, 2^{\log p}
\end{pmatrix}
$$

另外，定义 $\mathbf{G}^{-1}$ 为这样的一个变换：将矩阵的每个元拆成其二进制分解对应的列向量。注意 $\mathbf{G}\cdot \mathbf{G}^{-1}(\mathbf{M}) = \mathbf{M}$ 对于任意 $\mathbf{M}$ 成立。公钥 $\mathbf{A}$ 替换为 $n\times n\log p$ 的的矩阵，加密时的 $\mathbf{I}$ 换成 $\mathbf{G}$，然后这样构造同态运算：

• 加法. $C_1, C_2 \mapsto C_1 + C_2$；
• 乘法. $C_1, C_2 \mapsto C_1\cdot \mathbf{G}^{-1}(C_2)$。

现在我们来算一下乘法的结果：

$$
\begin{aligned}
&\left(\begin{pmatrix}
\mathbf{A} \\ \boldsymbol{s}^\top \mathbf{A} + \boldsymbol{\varepsilon}_1
\end{pmatrix} + m_1\mathbf{G}\right)\cdot \mathbf{G}^{-1} \left(\begin{pmatrix}
\mathbf{B} \\ \boldsymbol{s}^\top \mathbf{B} + \boldsymbol{\varepsilon}_2
\end{pmatrix} + m_2\mathbf{G}\right) \\
&= \begin{pmatrix}
\mathbf{A} \\ \boldsymbol{s}^\top \mathbf{A} + \boldsymbol{\varepsilon}
\end{pmatrix}\cdot \mathbf{G}^{-1}(\boldsymbol{C}_2) + m_1 \mathbf{C}_2 \\
&\approx \begin{pmatrix}
\mathbf{D} \\
\boldsymbol{s}^\top \mathbf{D} + \boldsymbol{\varepsilon}’
\end{pmatrix} + xy\mathbf{G}
\end{aligned}
$$

这里在算的时候，若两个矩阵 $\mathbf{A}, \mathbf{B}$ 满足 $\boldsymbol{t}^\top (\mathbf{A} - \mathbf{B})$ 非常小，就称 $\mathbf{A}\approx \mathbf{B}$。

至此我们构造了一个不是很 practical 的 Homomorphic Encryption，我们主要会担心 $\boldsymbol{\varepsilon}$ 随着运算次数累积。最后我们来考虑设计一种机制，能够提高密文的信噪比。

下面的东西没学懂，很可能是假的。

定理 3.2.1（Bootstrapping）. 若一个 Homomorphic Encryption 满足：

• Circular Security. 存在 Simulator $\mathcal{S}$，$\mathcal{S}(1^\lambda) \approx_c \textsf{Enc}(sk, sk)$。
• Somehow Homomorphic. 若对于任意不超过某个 $d$ 次运算的密文，都有一个同态的解密方案 $\textsf{Dec}(sk, \textsf{Enc}(sk, m)) = m$。

则可以基于此 Homomorphic Encryption 构造 Fully Homomorphic Encryption

证明. 注意因为 $\textsf{Dec}(\cdot, \textsf{Enc}(sk, m)) = m$ 是同态，所以

$$
\textsf{Dec}(\textsf{Enc}(sk, sk), \textsf{Enc}(sk, m)) = \textsf{Dec}(sk, \textsf{Enc}(sk, m)) = \textsf{Enc}(sk, m)
$$

如果 $d$ 比 $\textsf{Dec}$ 函数的计算次数略大，则你可以一直用这种方法来刷新密文。

$\blacksquare$

Digital Signature

数字签名是 MAC 在公钥密码学中的对应。其形式定义为

定义 3.3.1（Digital Signature）. 一个数字签名方案包含以下三个算法：

• $\textsf{Gen}(1^\lambda)\rightarrow (pk, sk)$；
• $\textsf{Sign}(sk, m) \rightarrow \sigma$；
• $\textsf{Verify}(pk, m, \sigma) \rightarrow 0/1$。

其安全性定义为任意的 p.p.t adversary $\mathcal{A}$ 都不能以不可忽略的概率赢得如下的安全性游戏：

1. Challenger 生成 $(pk, sk)$，发送 $pk$ 给 Adversary；
2. Challenger 多次询问 $m_i$，Adversary 须回复 $\sigma_i$；
3. Adversary 尝试伪造 $m, \sigma$。

$\mathcal{A}$ 胜利当且仅当 $\textsf{Verify}(pk, m, \sigma) \rightarrow 1$ 且 $m\notin \{m_i\}$。更强的安全性要求 $(m, \sigma)\notin \{m_i, \sigma_i\}$。

可以发现，Trapdoor Permutation 非常适合做这件事情。据此，我们用 RSA 构造一个 Trapdoor Permutation，然后以此构造一个 Signature：

RSA Based Digital Signature.

• $\textsf{Gen}(1^\lambda)\rightarrow (pk = (N, e), sk = d)$，其中 $N = pq, de \equiv 1 \pmod \varphi(N)$；
• $\textsf{Sign}(sk, m) = H(m)^d$，其中 $H$ 是 Random Oracle；
• $\textsf{Verify}(pk, m, \sigma)$ 判断是否有 $H(m) = \sigma^e$

Remark. 这里 random oracle $H$ 实乃必要。否则，你问 $m_1, m_2$ 就可以 forge 一个 $m_1m_2$。

其 unforgeability 的证明的核心就是你可以耦合 RSA 假设和 random oracle 的随机性。具体证明这里摆了。

Zero-Knowledge Proof

本节讨论所谓的零知识证明：一个 Prover 想要向 Verifier 证明他有一个 NP 问题的 witness，但不想让 NP 问题知道这个 witness。形式化地：

定义 4.4.1（ZKP Protocol）. 语言 $L$ 的一个 ZKP Protocol 指定了两个可以通信的 p.p.t 算法 $\mathcal{P}, \mathcal{V}$ 之间的交互方式，双方的交互结果（包括聊天记录和 Verifier 是否接受）合记作 $\langle \mathcal{P}(x, w), \mathcal{V}(x)\rangle$，$\mathcal{V}$ 能看到的全部信息记作 $\textsf{View}_V(\langle \mathcal{P}(x, w), \mathcal{V}(x)\rangle)$，满足：

• Completeness. 对于任意的 $x\in L$ 和相应的 witness $w$，有 $\Pr[\langle \mathcal{P}(x, w), \mathcal{V}(x)\rangle\rightarrow 1] = 1$ 即有 witness 时 Verifier 必然接受这个证明；
• Soundness. $\forall x\notin L, \forall \mathcal{P}^*, \Pr[\langle P^*(x), \mathcal{V}(x)\rightarrow 1\rangle] \leq \frac 12$，即没有 witness 时 Verifier 高概率拒绝这个证明。
• Honest Verifier (Perfect) Zero Knowledge. 存在一个 p.p.t simulator $\mathcal{S}$，使得 $\forall x\in L, \forall w, S(x) =_d \textsf{View}_V(\langle \mathcal{P}(x, w), \mathcal{V}(x)\rangle)$，即不知道 witness 者可以在同分布意义下模拟出 $V$ 看到的聊天记录。

其中第三个条件可以弱化成 $=_s$（statistical）乃至 $=_c$（computational）。

注意 soundness 里的 $\frac 12$ 可以改成任意的 $1 - 1 / \mathrm{poly}(n)$，因为否则通过多项式次重复即可把这个概率 amplitude 到 $1 / \mathrm{e}$。amplitude 的方式可以是 parallel（同时独立地 run 多个证明）和 sequential（进行多轮交互，每轮交互是一次证明）。两者看似没有差别，实际上在我们引入了 malicious verifier 和 rewind 之后可见仅有 sequential 是合适的。

以下是几个 ZKP 的例子。

Graph Isomorphism. $L = \{\left(G, G’\right): \exists \pi, G’ = \pi(G)\}$，即图同构问题，witness 为 $\pi$。

协议如下：

• Prover sample 一个排列 $\pi’$，得到 $G’’ = \pi’(G) \cong G$，将 $G’’$ 发送给 Verifier；
• Verifier sample 一个随机比特 $b$ 发送给 Prover；
• 若 $b = 0$，Prover 发送 $\pi’$；否则，Prover 发送 $\pi’ \circ \pi^{-1}$。
• 若 $b = 0$，Verifier 检查是否收到 $G$ 和 $G’’$ 间的同构映射；若 $b = 1$，Verifier 检查是否收到 $G’$ 和 $G’’$ 之间的同构映射。

显然这是一个满足 completeness、soundness 和 honest verifier zero-knowledge 的协议。

Quadratic Remainder. 语言 $\mathbb{QR} := \{(G, x) : \exists y\in G, y^2 = x\}$。

• Prover sample 一个 $r\in G$，发送 $xr^2$ 给 Verifier；
• Verifier sample $b\in \{0, 1\}$。
• 若 $b = 0$，Prover 发送 $r^2$ 给 Verifier（用于检验 $xr^2$ 是真的还是假的）；若 $b = 1$，Prover 发送 $yr$ 给 Verifier（用于检验 $x = y^2$ 是真的还是假的）。

显然这是一个 complete，sound 和 honest verifier zero-knowledge 的协议。

关于 ZKP 的一个重要结果是：

定理 4.4.1. $\mathbf{ZKP} = \mathbf{NP}$。

方法是给出 $\mathrm{3COL}\in \mathbf{ZKP}$。直觉上，你要证明一个图有三染色，只需要把这个三染色加密之后放在桌子上，然后 Verifier 抽一条边解密来看是不是不是同色。这里需要保证 Prover 解密出的结果必须是加密时的结果，因此需要如下原素：

定义 4.4.2（commitment）. 一个 commitment 机制包含以下两个操作：

• Commit. 根据 $m$ 和密钥，计算 $\hat{m}$；
• Open. 根据 $\hat{m}$ 和密钥，计算 $m$。

满足以下两个条件（Perfect，Statistical，Computational）：

• Hiding. 从 $\hat{m}$ 中不能拿到 $m$ 的信息；
• Binding. 在 commitment 之后，$m$ 不能被篡改。

定理 4.4.2. 存在 OWP / CRHF 则存在 commitment。

构造.

• 基于 OWP 的 commitment. perfect binding，computational hiding。
  • commit. 采样 $r, z$，发送 $f(r), b = h(r)\oplus m$。其中 $h$ 是一个 hardcore predicate。
  • open. 发送 $r$。
• 基于 CRHF 的 commitment. statistical hiding, computational binding。
  • commit. 采样 $r, z$，发送 $H(r), z, \langle r, z\rangle\oplus m$；
  • open. 发送 $r$。

$\blacksquare$

最后我们证明 $\text{3COL}\in \mathbf{ZKP}$ 来完成定理 4.4.2 的证明。

• Prover commit 每条点的颜色作用一个随机置换的结果；
• Verifier 随机 sample 一条边，open 这两个点的颜色；
• Verifier 检查颜色是否相同。

这个证明的 completeness 和 soundness 比较显然，需要着重说明 $\mathcal{S}$ 的构造。

• $\mathcal{S}$ 首先随机 sample 那条边。
• 如果 $v$ 不是这条边的端点，$\mathcal{S}$ 生成一个 commit $0$；
• 如果 $a, b$ 是这两条边的端点，则 $\mathcal{S}$ 随机两个 $c_1\ne c_2$，生成 commit $c_1$ 和 commit $c_2$。

注意 commitment 的 statistical hiding 表明对于没有 open 的 commitment，它分布上和均匀随机几乎无异，因此全部 commit $0$ 仍然保证了 statistical honest verifier zero knowledge。

至此，因为 $\mathrm{3COL}$ 是 NPC 问题，$\mathbf{ZKP} = \mathbf{NP}$ 得证。

$\blacksquare$

考虑到实践中，一个恶意的 Verifier 可以不按照协议要求的概率分布采样。这样的 Verifier 称为 Malicious Verifier $\mathcal{V}^*$，其交互框架相同，但是使用的随机性不同。定义 Malicious Verifier Zero Knowledge 为：对于任意的 malicious verifier $\mathcal{V}^*$，存在一个 p.p.t Simulater $\mathcal{S}$ 使得

$$
\textsf{View}_V(\langle P(x, w), \mathcal{V}^*\rangle) \approx \mathcal{S}(x)
$$

其中 $\mathcal{S}$ 有模拟和回退（rewind）交互流程的权限。以 QR 的ZKP 为例，一个针对 Malicious Verifier 的 simulator 可以形如：

1. $\mathcal{S}$ 自己均匀随机 sample 一个 $\hat{b}$，据此模拟出一个 view $\Pi$；
2. $\mathcal{S}$ 模拟 $\mathcal{V}^*$ 到输出 $b$ 这一步：
   1. 如果 $b = \hat{b}$，输出 $\Pi$；
   2. 否则，rewind $\mathcal{V}^*$ 到最开头，然后自己回到 1. 一步。

---

以上的所有构造都是基于 commitment - challenge - response 这样的三轮交互的范式。如何将其修改成所谓的 Non-interactive ZKP？有两种方法：

• Fiat-Shamir Transform. 在第二轮 challenge 环节中，改为由 Prover 本人调用一个 Random Oracle $\mathcal{O}(\mathrm{commitment})$ （实践中使用哈希函数近似）来生成 challenge 的信息（即 $b$，或者 $\mathrm{3COL}$ 中的那条边）。Verifier 需要额外检查 $b$ 是否确实是调用 random oracle 产生的；
• Common Reference String Model. 没看懂。

Secure Multi-Party Computation

本节考虑所谓的多方计算：有 $n$ 个参与方计划共同计算一个函数 $f: F^n \rightarrow F^n$，但是不希望其他人知道自己的输入。

一个老生常谈的例子是现在 $n$ 个人想要计算他们手里的数之和。一个经典的协议是第一个人 sample 一个数 $r$，然后将 $r + a_1$ 发给下一个人；每个人将收到的数加上自己手里的数 $a_i$ 发给下一个人，转一圈之后便得到了答案。这个协议的问题是 $i, i + 2$ 两个人联合起来可以知道 $i + 1$ 手里的数字。

我们现在来形式化多方计算、“联合起来”知道某人的输入这些事情。

定义 4.5.1（MPC Protocol）. 一个 MPC Protocol 指定了多个参与方 $1, 2, …, n$。如何完成对函数 $f$ 的计算，包括计算和通信过程。一个子集 $S \subseteq \{1, 2, …, n\}$ 可见的全部信息（包括输入、聊天记录、计算结果）记作 $\textsf{View}_S$。

称一个 MPC 是对子集 $S$ 安全的，若对于任意的输入 $x_1, …, x_n$，存在一个 simulator $\mathcal{S}$ 使得

$$
\mathcal{S}((x_i)_{i\in S}, (y_i)_{i\in S}) =_d \textsf{View}_S
$$

即，$S$ 中的参与方联合起来也无法知道其私人信息和众所周知的信息以外的任何额外信息。 当然这里 $=_d$ 可以改成 $\approx_s$ 或者 $\approx_c$

现在回到之前那个求和的问题。

MPC for Summation. 令 $f: \mathbb{Z}_p^n\rightarrow \mathbb{Z}_p^n$，其中

$$
f(x_1, …, x_n)_i = \sum_{j=1}^n x_i
$$

构造一个对于任意 $[n]$ 的真子集都安全的 MPC 协议。

对于参与方 $P_i$：

1. 采样 $x_{i1}, …, x_{in}$，满足 $\sum_{j}x_{ij} = x_i$，把 $x_{ij}$ 发给 $P_j$；
2. 收到 $x_{1i}, …, x_{ni}$ 之后，将其和记作 $s_i$，广播 $s_i$；
3. 收到所有 $s_i$ 之后，将其求和得到答案。

Simulator 的构造是平凡的：注意 $x_{i1}, …, x_{in}$ 是 $(n - 1)$-wise 独立的，故对于任意的真子集 $S$，$j$ 发送给 $i\in S$ 的数字都是独立均匀随机的。

上述构造展示了 MPC 的如下范式：

• 将自己的输入用一种具有同态性质的 Secret Sharing 方法发给其他人，其中任意 $S$ 个人联合起来算不出 secret 的内容，但是收集充分多的 sharing 之后自己可以计算出 secret；
• 完成计算之后收集 Secret Sharing 的结果，并复原。

这里提到了一个重要的原素 Secret Sharing。

定义 4.5.2（Secret Sharing）. 一个 $t$-out-of-$n$ 秘密共享机制包含如下两个算法：

• 算法 $\textsf{Distr}(s)\rightarrow [s] := (s_1, …, s_n)$；
• 算法 $\textsf{Rec}(S, (s_i)_{i\in S})\rightarrow s$，其中 $|S|\geq t$。

需满足正确性（常规自然的定义）和安全性：对于任意 $T\subseteq [n], |T| < t$，有 $(s_i)_{i\in T}$ 这个联合分布和 $s$ 独立。

有一些显然的 Secret Sharing 方案：

• Trivial Secret Sharing. 直接把秘密 $s$ 广播出去，就是一个 $1$-out-of-$n$ secret sharing。
• Additive Secret Sharing. 随机 $s_1, …, s_n$ 使得 $s_1 + \cdots + s_n = s$。这是 $n$-out-of-$n$ secret sharing，但是没有同态性质。
• Shamir Secret Sharing. 令 $f$ 是度数不超过 $t$ 的，常数项为 $s$ 的随机多项式。令 $s_i = f(i)$。注意任意 $t$ 个人可以联合起来插出多项式 $f$ 从而知道 $s$，但是不超过 $t$ 个人的话常数项和点值都是独立的。

注意，Shamir secret sharing 具有良好的同态性质：$[x + y] = [x] + [y]$，$[xy] = [x][y]$。但是这里隐藏了一个问题：如果你将两个多项式乘起来，其度数将会倍增，这导致你调用了一次 $[xy]$ 之后，参数 $t$ 会倍增。一旦解决了这个问题，我们便可以做任意的多项式函数的 MPC。

这里记 $[x]^{(t)}$ 为 $x$ 的一个 $t$-out-of-n secret sharing，$[x]^{(t)}_i$ 表示其散发给第 $i$ 个人的分量。

考虑你现在手里有一个 $[x]^{(t)}$ 和一个 $[y]^{(t)}$，那么直接将其乘起来，即可得到 $[xy]^{(2t - 1)}$。但我们不希望得到 $[xy]^{(2t - 1)}$ 而是 $[xy]^{(2t)}$，怎么实现？注意，根据拉格朗日插值公式：

$$
f(0) = \sum_{i=1}^n f(i) {\color{blue} \prod_{j\ne i} \frac{-j}{i - j}} := \sum_{i=1}^n {\color{blue} a_i} f(i)
$$

是关于 $f(x_i)$ 的线性函数，系数是容易计算的。而加法不会让 $t$ 改变。因此可以想到这样的乘法协议：给定 $[x]^{(t)}, [y]^{(t)}$：

1. 各方在本地计算 $[xy]^{(2t - 1)}$，方法是 $[xy]^{(2t - 1)}_i \leftarrow [x]^{(t)}_i[y]^{(t)}_i$。记 $z_i := [xy]^{(2t - 1)}_i$
2. 对于所有的参与方 $i$，散发 secret sharing $\left[z_i\right]^{(t)}$。
3. 所有参与方在本地计算
   $$
   [xy]^{(t)} = \sum_{i=1}^n a_i [z_i]^{(t)}
   $$

最后临近输出时，想要从 $[x]$ 中知道 $x$。但此时当然不可以把 $[x]_i$ 发给所有人，这样就泄露了信息。有两种方法来做保护：

1. 这本质上就是每个人输入是 $a_i[x]_i$，要求和的问题。调用之前的求和 Protocol 即可。
2. 所有人广播一个 $0$ 的 secret sharing $[0_i]^{(t)}$，然后在本地计算 $[\text{fresh $x$}] = [x] + \sum [0_i]$，广播 fresh $x$ 的 secret sharing 后可以解出 $x$。注意，在广播了 $[0_i]^{(t)}$ 和已知答案之后，fresh $x$ 完全可以由插值算出，因此广播 fresh $x$ 的 secret sharing 完全没有问题。

以上的 Shamir secret sharing、degree reduction 操作并上 2. 的 open 构成了著名的 BGW Protocol，其解决了如下问题：

定理 4.5.1. 对于任意的算术电路 $f: \mathbb{F}_p^n\rightarrow \mathbb{F}_p$，存在对于任意大小不超过 $(n - 1) / 2$ 的子集都安全的 MPC。

---

接下来讨论一些具体的 MPC（实际上是 2PC）。首先是所谓的 不经意传输（Oblivious Transfer），即有一个发送方和一个接收方，发送方手里持有 $m_0, m_1$ 两个消息，接收方手里有一个索引 $b$。希望用安全 MPC 计算一个函数

$$
f: ((m_0, m_1), b) \mapsto (\bot, m_b)
$$

这称为 $1$-out-of-$2$ Oblivious Transfer。可以将角标拓展至 $0, 1, …, t - 1$ 的 $1$-out-of-$t$ Oblivious Transfer。显然有如下定理：

定理 3.5.2. 若存在 $1$-out-of-$2$ Oblivious Transfer，便对于任意常数 $t$ 存在 $1$-out-of-$t$ Oblivious Transfer。

构造. WLOG 假设消息 $m_i$ 都只有一个 bit。则我们可以进行 $t$ 轮 $1$-out-of-$2$ Oblivious Transfer，其中第 $i$ 轮时 $\hat{m}_0 = 0, \hat{m}_1 = m_i$。

$\blacksquare$

OT 可以由 Trapdoor OWP 得来。

定理 3.5.3. 若存在 Trapdoor OWP，则存在 $1$-out-of-$2$ Oblivious Transfer。

构造. 协议内容如下：

• Sender 持有一个 trapdoor OWP $f$ 和相应的 trapdoor $t$。Sender 随机 sample 一个 $\Delta$，发送 $f, \Delta$ 给 Receiver。
• Receiver 采样 $x_b$，计算 $y_b = f(x_b)$，令 $y_{1 - b} = \Delta - y_b$。发送 $y_0, y_1$ 给 Sender；
• Sender 用 trapdoor 还原 $x_0 = f^{-1}(y_0), x_1 = f^{-1}(y_1)$，发送 $h(x_0)\oplus m_0$ 和 $h(x_1)\oplus m_1$ 给 Receiver。这里 $h$ 是 $f$ 的一个 harcore bit。
• Receiver 知道 $x_b$，因此可以计算 $m_b$，但另一个则看起来是完全随机的。

$\blacksquare$

这个构造，如果双方都是 semi-honest 的，在 Sender 一侧是 Perfect Secure，在 Receiver 一侧是 Computational Secure。

此外如果有 FHE，也可以得到 Oblivious Transfer。

定理 3.5.3. 若存在一个 homomorphic encryption，则存在 Oblivious Transfer。

构造. 协议内容如下：

• Receiver 给 Sender 发送 $\textsf{Enc}(b)$；
• Sender 发送 $\textsf{Enc}(m_0) + (m_1 - m_0)\textsf{Enc}(b) = \textsf{Enc}(m_b)$。

$\blacksquare$

一个类似于 OT 的东西是 Oblivious Linear Function Evaluation（OLE）。这是一个 2PC 问题，双方要计算函数

$$
f: ((a, b), x) \mapsto (\bot, ax + b)
$$

其中 $a, b, x$ 都是某个 $\mathbb{F}_p$ 中的元素。

基于 Pallier 可以构造 OLE（其中 $g, h$ 为两个 hard subgroup 的生成元）。

• Receiver 采样 $s, s’, r$，发送 $c := g^sh^{-r}, c’ = g^{s’}h^{-x + r}$ 给 Sender；
• Sender 采样 $t, w$，发送
  $$
  \begin{aligned}
  &g^t \\
  &\textsf{Enc}(a) = h^t(N + 1)^a \\
  &\textsf{Enc}(w) = c^t(N + 1)^2 \\
  &\textsf{Enc}(b - w) = c’^t(N + 1)^{b - w}
  \end{aligned}
  $$
• Receiver 计算收到的三个 $\textsf{Enc}$ 的积，发现这是
  $$
  (N + 1)^{ax + b}g^{t(s + s’)}
  $$
  因为 Receiver 知道 $s + s’$，也收到了 $g^t$，便可知道 $ax + b$。

---

最后我们来讨论 Yao’s Garbled Circuit（混淆电路）。这个密码学原素的用途是在加密过的函数上计算加密过的输入，只暴露输出。用 Garbled Circuit 和 Oblivious Transfer 可以实现常数轮交互的 MPC。

定义 3.5.3（Garbling Scheme）. 一个 Garbling Scheme 包含以下几个算法：

• $\textsf{Gb}$：随机算法，读入一个布尔电路 $f: \{0, 1\}^n\rightarrow \{0, 1\}^n$，输出 $(F, e, d)$，表示混淆后的电路、编码信息和解码信息。
• $\textsf{ev}$：用于计算明文电路的算法，即 $\textsf{ev}(f, x) = f(x)$。
• $\textsf{En}$：给输入加密的算法，$\textsf{En}(e, x) \rightarrow X$。其中 $e = (L_i^0, L_i^1)_{i = 1, 2, …, n}$，$X = (L_i^{x_i})_{i = 1, 2, …, n}$；
• $\textsf{Ev}$ 用混淆后电路 $F$ 和混淆后的输入计算一个混淆后的输出 $Z’$ 的算法。
• $\textsf{De}$ 用解码信息 $d$ 将 $Z’$ 解码成明文输出 $z$ 的函数。一般 $d = (Z_0, Z_1)$，解码就是若 $Z’ = Z_i$ 就输出 $i$，否则输出 $\bot$。

$\textsf{En}, \textsf{De}, \textsf{ev}$ 在混淆电路中基本上都是固定的方法，已经在上面给出。在构造混淆电路时我们只重点关注 $\textsf{Gb}$ 和 $\textsf{Ev}$ 两个函数。

算法应当满足正确性和安全性。正确性的定义为：

$$
\textsf{De}(\textsf{Ev}(\textsf{Gb}(C), \textsf{En}(x))) \rightarrow C(x) \text{ with $1 - \mathrm{negl}$ probability}
$$

安全性的定义是存在一个 simulator $\mathcal{S}$，使得

$$
\mathcal{S}(C, C(x)) \approx_c (\hat{C}, \hat{x})
$$

即混淆后的输入和混淆后的电路只泄露了电路结构和输出的信息。混淆电路的一个实际应用就是做 2PC：

定理 3.5.4. 若存在 Garble Scheme 和 $1$-out-of-$2$ OT，则对于任意的布尔电路 $f(x, y)$，存在一个 2PC 协议计算：

$$
(x, y) \mapsto (\bot, f(x, y))
$$

构造.

• Sender 计算 $\textsf{Gb}(f) = (\hat{f}, (e_x \Vert e_y), d)$，发送 $\hat{f}, d$ 给 Receiver；
• Sender 发送 $\hat{y}$ 给 Receiver；
• Sender 通过 OT 发送 $\hat{x}$ 给 Receiver；
• Receiver 用 $\textsf{Ev}$ 算出结果，然后自己解码。

在这个协议中，Garble Scheme 的安全性保证了 Receiver 不知道 $x$，OT 的安全性保证了 Sender 不知道 $y$。

接下来我们构造一个 Garble Circuit 的方案。对于一个 circuit $f$，其中有 $T$ 条线（wire），WLOG 设 $f$ 里面都是 NAND Gate。假设我们有一个 PRF $G: 2^k\times 2^k\times T\rightarrow 2^{2k}$，你可以理解为前两项都是密钥，只要藏住一个密钥，这个 PRF 就和随机的看起来差不多。一个构造是

$$
G(A, B, i) = \mathcal{F}(A, i)\oplus \mathcal{F}(B, i)
$$

其中 $\mathcal{F}$ 就是一个 PRF。

• Garbling. 算法 $\textsf{Gb}$ 如下：
  • 对于每条 wire，产生两个随机串 $(K_0^i, K_1^i)$；所有的输入 wire 的随机串作为 $e$ 暴露出去。
  • 对于每个门，定义一个混淆表 $(C_0^i, C_1^i, C_2^i, C_3^i)$ 如下：
    • 对于任意 $(a, b)\in \{0, 1\}\times \{0, 1\}$，计算
      $$
      C’_{(a, b)} = G(K_a^{L(i)}, K_b^{(R_i)}, i)\oplus (K_{\neg ab}^i, 0^k)
      $$
      此处 $L(i), R(i)$ 表示输入这个门的两条线的编号。
    • 选一个随机排列 $\pi: \{0, 1, 2, 3\}\rightarrow \{0, 1\}\times \{0, 1\}$，将 $C’_{i, j}$ 填入表的第 $\pi(i, j)$ 项。
• Evaluate. 对于一个门，其混淆表中的四个数为 $C_0^i, C_1^i, C_2^i, C_3^i$。对于 $j = 0, 1, 2, 3$，计算
  $$
  (K_j’, \tau_j) = G(K^{L(i)}, K^{R(i)}, i)\oplus C_j^{i}
  $$
  若存在唯一的 $\tau_j = 0^k$，则定义 $K^i = K_j’$，否则输出 $\bot$。

这东西的正确性是显然的。其安全性来源于如下直觉：在 Evaluate 一个 Garbled Circuit 的时候，你可以知道 $K^i_{\neg ab}$，但是没法知道 $K^i_{ab}$：在转发表的其他三项中，信息都被一个遮住了密钥的 PRF 给 one-time pad 住了。因此 Adversary 不能区分转发表的其他三项和三个随机数。容易据此原理设计 Simulator $\mathcal{S}$。

Appendix: Techniques from Homeworks

这一节写一些零散的作业里面讲的东西。

定理 4.1（Leftover Hash Lemma）. 设 $X$ 是一个 $k$-source 随机变量，即对于任意的 $x$，有 $\Pr[X = x] \leq 2^{-k}$。

哈希函数族 $\mathcal{H} = \{h : \{0, 1\}^n \rightarrow \{0, 1\}^\ell\}$ 是通用的，即 $\Pr[h(x) = h(y)] = 2^{-\ell}$。

若 $\ell = k - 2\log(1 / \varepsilon) - O(1)$，则有

$$
\Delta((H, H(X)), (H, U)) \leq \frac{\varepsilon}{2}
$$

证明. 根据 $X$ 是 $k$-source 随机变量和 $\mathcal{H}$ 是通用哈希函数族有

$$
\begin{aligned}
\Pr[(H, H(X)) = (H’, H’(X’))] &= |\mathcal{H}|^{-1}\Pr[H(X) = H(X’)] \\
&\leq |\mathcal{H}|^{-1}(\Pr[X = X’] + \Pr[H(X) = H(X’) | X \ne X’]) \\
&\leq |\mathcal{H}|^{-1}(2^{-k} + 2^{-\ell})
\end{aligned}
$$

据此可以知道这两个分布的 $L_2$ 距离不大：

$$
\begin{aligned}
\left\lVert (H, H(X)) - (H, U)\right\rVert_2^2 &= \sum_{h\in \mathcal{H}, s\in \{0, 1\}^\ell}\left(\Pr[(H, H(X)) = (h, x)] - \frac{1}{|\mathcal{H}|2^{\ell}}\right)^2 \\
&\leq |\mathcal{H}|^{-1}(2^{-k} + 2^{-\ell}) + \frac{1}{|\mathcal{H}|2^{\ell}} - \frac{2}{|\mathcal{H}|2^{\ell}} \\
&= \frac{\varepsilon^2}{|\mathcal{H}|2^\ell}
\end{aligned}
$$

最后 $L_2$ 距离和 $L_1$ 距离之间的 bound 由 Cauchy-Schwartz 不等式给出：

$$
\Delta_{TV}((H, H(X)) , (H, U)) \leq \sqrt{|\mathcal{H}|2^\ell}\cdot \sqrt{\left\lVert (H, H(X)) - (H, U) \right\rVert_2^2} \leq \frac{\varepsilon}{2}
$$

$\blacksquare$

有了 Leftover Hash Lemma，我们可以证明 LWE-based Encryption 的 CPA 安全性。考虑以下 Hybrid Argument：

• Hybrid 0. distinguisher 收到 $pk = (\mathbf{A}, \boldsymbol{b}) = (\mathbf{A}, \boldsymbol{s}^\top \mathbf{A} + \boldsymbol{\varepsilon}^\top)$ 和 $c = \mathbf{A}\boldsymbol{r}, \boldsymbol{b}^\top \boldsymbol{r} + \lceil p / 2\rceil x$
• Hybrid 1. disgintuisher 收到 $pk = (\mathbf{A}, \boldsymbol{b})$（$\mathbb{b}$ 纯随机）和 $c = \mathbf{A}\boldsymbol{r}, \boldsymbol{b}^\top \boldsymbol{r} + \lceil p / 2\rceil x$；
• Hybrid 2. distinguisher 收到 $(\mathbf{A}, \boldsymbol{b})$ 和 $c = \boldsymbol{a}, v + \lceil p / 2\rceil x$，其中 $\boldsymbol{a}, v$ 纯随机。

Hybrid 0 和 Hybrid 1 不可区分，因为 LWE Assumption。Hybrid 1 和 Hybrid 2 不可区分，因为 $\mathcal{H} := \{\boldsymbol{r}\mapsto \mathbf{A}\boldsymbol{r}, \boldsymbol{b}^\top \boldsymbol{r} + \lceil p / 2\rceil x\}$ 是 universal hash，套用 leftover hash lemma 得证。

---

Pallier Encryption 是另一种加密方案。设 $p, q$ 是两个安全素数（i.e. $p = 2p’ + 1, q = 2q’ + 1$），$N = pq$，考虑群 $\mathbb{Z}_{N^2}^{*}$，其所有二次剩余 $\mathbb{QR}_{N^2}$ 也构成一个群，而且显然 $\mathbb{QR}_{N^2}\cong \mathbb{QR}_{p^2}\times \mathbb{QR}_{q^2}$。

注意群 $\mathbb{Z}_{p^2}^*$ 中 $x\rightarrow x^2$ 是一个 2 对 1 的映射。因此 $|\mathbb{QR}_{p^2}| = \frac 12 |\mathbb{Z}_{p^2}^*| = pp’$，根据有限阿贝尔群分解定理，$\mathbb{QR}_{p^2}\cong \mathbb{Z}_p\times \mathbb{Z}_{p’}$，综上

$$
\mathbb{QR}_{N^2} \cong \mathbb{Z}_p\times \mathbb{Z}_{p’}\times \mathbb{Z}_q\times \mathbb{Z}_{q’}\cong \mathbb{Z}_N \times \mathbb{Z}_{p’q’}
$$

因此 $\mathbb{QR}_{N^2}$ 可以被分解成两个群 $\mathbb{G}_N$ 和 $\mathbb{H}_N$ 的内置积，其中 $\mathbb{G}_N$ 是唯一的大小为 $n$ 的子群，$\mathbb{H}_N$ 是唯一的大小为 $p’q’$ 的子群，分别称为 easy subgroup 和 hard subgroup。显然，$N + 1$ 是 $\mathbb{G}_N$ 的一个生成元（因为 $(1 + N)^k = 1 + kN \pmod{N^2}$），$\mathbb{G}_N$ 中的离散对数容易求解。$\mathbb{H}_N$ 则没什么结构，但是给定 $N$ 容易在 $\mathbb{H}_N$ 中 sample 元素：先随机 sample $\mathbb{QR}_N$ 的元素和 $\mathbb{G}_N$ 的元素然后做除法。

至此我们准备完了 Pallier 加密所需的工具。基于如下假设：

假设 4.2（Decisional Composite Residuosity Assumption）. 设 $h$ 从 $\mathbb{H}_N$ 中随机抽取，$x$ 从 $\mathbb{QR}_{N^2}$ 中随机抽取，$(N, h)\approx_c (N, x)$。

提出如下加密方案：

• $\textsf{Gen}(1^n) \rightarrow (pk = N, sk = p’q’)$；
• $\textsf{Enc}(pk, m)\rightarrow h\cdot (1 + N)^m$，其中 $h$ 从 $\mathbb{H}_N$ 中均匀随机采样。
• $\textsf{Dec}(sk, c) \rightarrow (p’q’)^{-1}\cdot \log_{1 + N}(c^{p’q’})$。

根据 DCRH，$h$ 把密文 one-time pad 住了，因此具有 CPA 安全性。

---

关于 Circular Security. CPA 安全的加密方案不一定是 Circular Secure 的。具体地

定理 4.3. 只要存在 CPA 安全的加密方案，便存在 CPA 安全但是不 circular secure 的加密方案。

构造. 假设已经有一个 CPA 安全的加密方案 $\textsf{Enc}, \textsf{Dec}$，新的加密方案如下：

• 随机 sample $x_1, x_2$；
• 判断是否有 $\textsf{Dec}(m, \textsf{Enc}(pk, x_i)) = x_i$ 成立（$\star$）。
  • 若是，直接泄露私钥；
  • 否则，正常加密。

注意 $\star$ 发生的概率必是 negligible 的，然而这个加密方案加密 $sk$ 必然泄露 $sk$ 本身。

$\blacksquare$

---

Linear Relation 的零知识证明. 一个 $p$ 阶群 $G$ 上，$m\times n$ 的矩阵 $g_{ij}$ 和 $u_1, …, u_m$、$x_1, …, x_n$ 间的 Linear Relation 是这样的一个表达式：

$$
\boldsymbol{u} = \mathbf{G}\boldsymbol{x} := \left(\forall i = 1, 2, …, m, \qquad \prod_{j=1}^n g_{ij}^{x_j} = u_i\right)
$$

令 $L: \{(\mathbf{G}, \boldsymbol{u}): \exists \boldsymbol{x}, \boldsymbol{u} = \mathbf{G}\boldsymbol{x}\}$。

定理 4.4. 存在 $L$ 的零知识证明。

构造.

• Prover 采样 $y_1, …, y_n$，发送 $\{v_i\} = \{\prod_{i=1}^n g_{ij}^{y_j}\}$ 给 Verifier；
• Verifier 采样 $r$ 发送给 Prover；
• Prover 发送 $\{x_i + ry_i\}$ 给 Verifier；
• Verifier 验证是否有 $\prod_{j=1}^n g_{ij}^{x_{j}r + y_j}$ 是否就是 $u_i^r v_i$

$\blacksquare$

实际上，这是一个 Zero-Knowledge Proof of Knowledge（ZKPoK）。ZKPoK 要求：存在一个 Extractor，该 Extractor 有 Prover 的 oracle access 和 rewind 权限，若 Prover 的证明被拒绝的概率充分小，则 Extractor 可以拿到 witness。这个问题的 Extractor 如下：

• 首先照常跑一轮 Verifier；
• 把 Prover rewind 到第二步交互，向其发送 $r’ \ne r$。
• 现在就收到了 $x_i r + y_i$ 和 $x_i r’ + y_i$，其中 $r’ \ne r$，容易反解出 witness $x_i$。

注意，以下的问题都可以翻译作 Linear Relation，翻译方法类似于线性规划转换成标准型。

• DH Triple. $(a, b, c)$ 是 DH-Triple，即存在 $x, y, z$，$a = g^x, b = g^y, c = g^{xy}$；
• Encrypted DH-Triple. Alice 手里有三个二元组 $(v_1, e_1), …, (v_3, e_3)$，欲证明这是一个 DH-Triple 用一个公钥为 $u$ 的 Diffie-Hellman 加密得到的结果，即 $\exists \beta_1, \beta_2, \beta_3, x, y, z$ 使得
  $$
  \begin{aligned}
  (v_1, e_1) = (g^{\beta_1}, u^{\beta_1}g^x) \\
  (v_2, e_2) = (g^{\beta_2}, u^{\beta_2}g^y) \\
  (v_3, e_3) = (g^{\beta_3}, u^{\beta_3}g^{xy})
  \end{aligned}
  $$

---

Threshold Secret Sharing Lower Bound. 这里证明安全的 $t$-out-of-$n$ secret sharing 的密文空间不能过小，即

定理 4.4. 设 $\textsf{Share}: \{0, 1\}\times \mathcal{R} \rightarrow \mathcal{S}_1\times \cdots \times \mathcal{S}_n$ 是一个利用 $\mathcal{R}$ 中的随机性的、Perfect Correct 且 Perfect Private 的 $t$-out-of-$n$ secret sharing，则 $\sum_i \log |\mathcal{S}_i| \geq \Omega((n - t)\log (n - t))$。

证明. 这里先考虑 $2$-out-of-$n$。从 $2$-out-of-$n$ 加强到 $t$-out-of-$n$ 只需要 conditional on 前 $t - 1$ 个人即可。

根据 Perfect Correctness，任意两个人联合起来必须要能知道一条消息是哪个秘密得到的。因此对于任意两个随机种子 $r, r’$

$$
\sum_{i=1}^n \mathbf{1}\{\textsf{Share}_i(0, r) = \textsf{Share}_i(1, r’)\} \leq 1
$$

如果左边大于 1，则对其产生两个贡献的人联合起来不能知道这个消息是 $0$ 在随机种子 $r$ 下生成的还是 $1$ 在随机种子 $r’$ 下生成的。令 $r, r’$ 独立均匀随机求期望，得到

$$
\begin{aligned}
1&\geq \sum_{i=1}^n \mathbb{E}[\mathbf{1}\{\textsf{Share}_i(0, r) = \textsf{Share}_i(1, r’)\}] \\
&= \sum_{i=1}^m \sum_{s\in \mathcal{S}_i} \Pr[\textsf{Share}_i(0, r) = s]\Pr[\textsf{Share}_i(1, r’) = s] \\
&= \sum_{i=1}^m \sum_{i=1}^n \Pr[\textsf{Share}_i(0, r) = s]^2 \\
&\geq \sum_{i=1}^m \frac{1}{|\mathcal{S}_i|}\sqrt{\sum_{s\in \mathcal{S}} \Pr[\textsf{Share}_i(x, r) = s]} \\
&= \sum_{i=1}^n \frac{1}{|\mathcal{S}_i|}
\end{aligned}
$$

第三行是 Perfect Privacy，第四行是 Cauchy-Schwartz 不等式，第五行是概率归一化。至此我们知道了 $\sum_{i=1}^n \frac{1}{|\mathcal{S}_i|}\leq 1$，这和欲证结论之间就差一个 Log-sum inequality。

$\blacksquare$

Remark. [Bogdanov-Guo-Komargodski 2016] 证明了 $\sum_i \log |\mathcal{S}_i|\geq t\log t$，因此 $\sum_i \log |\mathcal{S}_i| \geq \Omega(n\log n)$，Shamir Secret Sharing 是最优的。

---

MPC 的存在性. 我们将证明 MPC 并非万能。

定理 4.5. 不存在一个安全（Perfect Secure against semi-honest adversaries）2PC 能够计算

$$
f: (a, b) \mapsto (a\wedge b, a\wedge b)
$$

证明. 施归纳于消息条数 $T$。

• 不存在 $0$ 条消息交互的协议. 显然。
• 不存在 $T$ 条消息交互的协议. WLOG 设第一轮 $P_2$ 给 $P_1$ 发消息。若 $x_1 = 0$，则 $a\wedge b = 0$。因为这个 2PC 是 Perfect Secure 的，所以存在一个 simulator $\mathcal{S}(x_1, y_1)$ 能精确求出第一条消息的分布。因此，第一条消息的分布就是 $\mathcal{S}(0, 0)$ 给出的那个分布，$T$ 条消息的交互等价于 $P_1$ 自己从 $\mathcal{S}(0, 0)$ 中采样一条消息，然后双方进行 $T - 1$ 条消息的交互，这也是不存在的。

$\blacksquare$

Remark. 然而存在安全的 2PC 能够计算不对称的 AND，即 $f: (a, b)\mapsto (\bot, a\wedge b)$。方法是 $P_1$ 令 $(m_0, m_1) = (0, a)$，用 oblivious transfer 发送 $m_b$ 给 $P_2$。