Chapter 2 现代密码学与基础原语¶

1 现代密码学与可证明安全¶

现代密码学的三大原则

形式化的定义（Formal Definitions）：明确“安全保证”与“威胁模型”
精确的假设（Precise Assumptions）：如大整数分解、DDH 等数学难题
严格的安全性证明（Rigorous Proofs）：基于归约 (Reduction) 的证明

1. 1 形式化定义¶

安全保证（Security Guarantee）

错误直觉：攻击者“不能恢复明文”就算安全。
更准确的定义：攻击者无法从密文中获得关于明文的任何有效信息，即满足语义安全（Semantic Security）。

威胁模型（Threat Model）

密码方案的安全性必须指明敌手能力。常见模型按强弱递增如下：

Ciphertext-only：敌手只能看到密文。
Known-plaintext：敌手知道部分明密文对。
Chosen-plaintext Attack（CPA）：敌手可选择明文并获得对应密文。
Chosen-ciphertext Attack（CCA）：敌手还可访问解密接口，能请求对选定密文解密。

基于游戏的安全性定义示例：IND-CPA

若任意 PPT 敌手 $\mathcal{A}$ 赢得游戏的优势可忽略，即：

\[ \Pr[b=b'] \le \frac{1}{2} + negl(\kappa) \]

则称该公钥加密方案是 IND-CPA 安全的

1. 2 精确的假设¶

使用未经证明但久经考验的假设来证明密码方案的安全性。

DDH（Decisional Diffie-Hellman）假设

如果对任意概率多项式时间的敌手 $\mathcal{A}$，都存在一个可忽略函数 $\mathsf{negl}$，使得 $$ \left|\Pr\left[\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^z) = 1\right] - \Pr\left[\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^{xy}) = 1\right]\right| \leq \mathsf{negl}(\kappa) $$ 其中，群参数 $\mathbb{G}, q, g$ 是由群的生成算法 $\mathcal{G}(1^\kappa)$ 生成的，$x, y, z \xleftarrow{}_{\$} \mathbb{Z}_q$ 是均匀随机选择的。那么，我们说 DDH 问题在群 $\mathbb{G}$ 中是困难的。

1. 3 严格的安全性证明¶

如果存在敌手 $\mathcal{A}$ 能攻破方案 $\Pi$，那么存在算法 $\mathcal{B}$ 能攻破底层假设。

定义（ElGamal 加密方案）

考虑一个阶为 $q$ 的循环群 $\mathbb{G}$，生成元为 $g$。ElGamal 加密方案包含三个算法 $(\text{Gen}, \text{Enc}, \text{Dec})$：

密钥生成 $\text{Gen}$：随机选择 $\text{sk} \xleftarrow{}_{\$} \mathbb{Z}_q$，计算 $\text{pk} = g^{\text{sk}}$，输出 $(\text{pk}, \text{sk})$
加密 $\text{Enc}(\text{pk}, m)$：对消息 $m \in \mathbb{G}$，随机取 $r \xleftarrow{}_{\$} \mathbb{Z}_q$，输出密文 $c = (c_1, c_2) = (g^r, m \cdot \text{pk}^r)$
解密 $\text{Dec}(\text{sk}, c)$：对 $c = (c_1, c_2)$，输出 $\hat{m} = c_2 / c_1^{\text{sk}}$（/ 表示乘以群元素的逆元）

定理（ElGamal 加密方案的安全性）

假设 DDH 问题在群 $\mathbb{G}$ 中是困难的，那么 ElGamal 加密方案是 IND-CPA 安全的。

ElGamal 安全性证明（归约）

证明思路

$(\text{DDH 假设安全} \Rightarrow \text{ElGamal 加密方案安全}) \Leftrightarrow (\text{ElGamal 加密方案不安全} \Rightarrow \text{DDH 假设不安全})$

设 ElGamal 加密方案为 $\Pi$，假设存在敌手 $\mathcal{A}$ 能以不可忽略的优势 $\epsilon(\kappa)$ 攻破 ElGamal 的 IND-CPA 安全性：

\[ \Pr[PubK_{\mathcal{A},\Pi}^{CPA}(\kappa)=1]=\frac{1}{2}+\epsilon(\kappa) \]

则可构造算法 $\mathcal{B}$ 攻破 DDH 假设。

算法 $\mathcal{B}$（输入 $(\mathbb{G}, q, g, h_1, h_2, h_3)$）

设 $\text{pk} = h_1$，发送给 $\mathcal{A}$，获得 $m_0, m_1 \in \mathbb{G}$
随机取 $b' \xleftarrow{}_{\$} \{0, 1\}$，设 $c_1 = h_2,\ c_2 = m_{b'} \cdot h_3$
将 $(c_1, c_2)$ 发给 $\mathcal{A}$ 得到 $b$；若 $b = b'$ 输出 $1$，否则输出 $0$

若 $(h_1,h_2,h_3)=(g^x,g^y,g^z)$ 是随机三元组，此时 $(c_1,c_2)$ 与 $m_b$，因而有：

\[ \Pr[\mathcal{B}(\mathbb{G},q,g,g^x,g^y,g^z)=1] = \frac{1}{2} \]

若 $(h_1,h_2,h_3)=(g^x,g^y,g^{xy})$ 是 DDH 三元组，此时 $pk=h_1=g^x$，$c_1=h_2=g^y$，$c_2=m_{b'} \cdot h_3 = m_{b'} \cdot g^{xy} = m_{b'} \cdot pk^y$，与 ElGamal 的真实加密分布完全一致，因而有：

\[ \Pr[\mathcal{B}(\mathbb{G},q,g,g^x,g^y,g^{xy})=1]=\Pr[PubK_{\mathcal{A},\Pi}^{CPA}(\kappa)=1] \]

综上所述，有：

\[ \left|\Pr[\mathcal{B}(\mathbb{G},q,g,g^x,g^y,g^z)=1]-\Pr[\mathcal{B}(\mathbb{G},q,g,g^x,g^y,g^{xy})=1]\right|=\epsilon(\kappa) \]

由于 $\epsilon(\kappa)$ 不可忽略，说明 $\mathcal{B}$ 可以有效区分随机三元组与 DDH 三元组，这与 DDH 假设成立矛盾，因此 ElGamal 在 DDH 假设下必须是 IND-CPA 安全的。

2 基本术语与符号¶

可忽略函数（Negligible Function）：表示一个随安全参数增长而趋近于 0，且趋近速度快于任何多项式倒数的函数，记作 $negl(\kappa)$

\[ \forall c>0,\ \exists N,\ \forall \kappa>N,\ negl(\kappa)<\frac{1}{\kappa^c} \]

计算不可区分（Computational Indistinguishability）：对任意 PPT 区分器 $D$，都无法有效分辨两个分布 $X$ 和 $Y$，记作 $X \approx Y$

\[ \left|\Pr[D(X)=1]-\Pr[D(Y)=1]\right| \le negl(\kappa) \]

统计距离（Statistical Distance）：用于衡量两个分布在信息论意义上究竟差多大

\[ \delta(X,Y)=\frac{1}{2}\sum_d \left|\Pr[X=d]-\Pr[Y=d]\right| \]

统计距离与计算不可区分的区别

统计距离小：说明两个分布本身就非常接近，不依赖计算能力限制
计算不可区分：允许两个分布事实上不同，只要高效算法看不出来即可

3 密码学原语¶

定义：设 $\mathcal{D}$ 是秘密所在的域，$\mathcal{D}_1$ 是份额所在的域，$(t, n)$-门限秘密分享包含算法 $(\text{Share}, \text{Rec})$：
- $(s_1, \dots, s_n) \leftarrow \text{Share}(s)$：输入秘密 $s \in \mathcal{D}$，输出 $n$ 个份额 $s_1, \dots, s_n \in \mathcal{D}_1$
- $s = \text{Rec}(s_{i_1}, \dots, s_{i_k})$：输入任意 $k \geq t+1$ 个份额，恢复秘密 $s \in \mathcal{D}$
性质：
- 正确性：若 $(s_1, \dots, s_n) \leftarrow \text{Share}(s)$，则
\[ \Pr[\forall k \ge t+1,\ Rec(s_{i_1},\dots,s_{i_k})=s]=1 \]
- （完美）隐私性：任意 $|U| \leq t$ 的份额集合 $\{s_j\}_{j \in U}$ 的分布与 $s$ 无关，即敌手即便拥有这些份额，也得不到任何关于秘密的额外信息

Shamir Secret Sharing (基于多项式插值)

基于多项式插值构造 $t$ 次多项式：

\[ f(x)=s+a_1x+\cdots+a_tx^t \]

其中常数项 $s$ 是秘密，$a_1,\dots,a_t$ 为随机系数，第 $i$ 个参与方拿到份额 $y_i=f(i)$，由于 $t$ 次多项式需要至少 $t+1$ 个点才能唯一确定，因此天然满足门限恢复性质。

3.2 哈希函数与随机谕示机（Hash Functions & Random Oracle）¶

哈希函数：输入任意长度比特串，输出固定长度 $\kappa$ 比特串

\[ H:\{0,1\}^* \to \{0,1\}^{\kappa} \]

三类核心安全性质

抗原像性（Preimage Resistance）：给定 $y$，难以找到 $x'$ 使 $H(x')=y$
抗第二原像性（Second-preimage Resistance）：给定 $x$，难以找到 $x' \ne x$ 使 $H(x')=H(x)$
抗碰撞性（Collision Resistance）：难以找到任意 $x \ne x'$ 使 $H(x)=H(x')$

随机谕示机（RO）是一个理想化公共函数 $H$：
- 如果输入 第一次出现，则返回一个随机值 $r_x \leftarrow \{0,1\}^{\kappa}$
- 如果输入 之前出现过，则返回和之前完全相同的结果

现实含义

RO 是理想模型，不是现实中真实存在的函数，实际协议通常用哈希函数去实例化随机谕示机。
因此，在 RO 模型下证明安全，不等于在真实世界中无条件安全。

3. 3 伪随机数生成器（PseudoRandom Generator, PRG）¶

定义：确定性算法，输入短种子，输出更长的比特串

\[ G:\{0,1\}^{\kappa} \to \{0,1\}^{\ell(\kappa)}, \quad \ell(\kappa)>\kappa \]

两项核心要求

扩展性：输出长度必须大于输入种子长度
伪随机性：输出与真正均匀随机串计算不可区分

\[ \{G(s)\}_{s \leftarrow \{0,1\}^{\kappa}} \approx \{r\}_{r \leftarrow \{0,1\}^{\ell(\kappa)}} \]

3. 4 对称加密方案（Symmetric Encryption Schemes）¶

对称加密 (Symmetric Encryption)

设密钥空间为 $\mathcal{K}$，明文空间为 $\mathcal{M}$，密文空间为 $\mathcal{E}$，对称加密方案包含算法 $(\text{Gen}, \text{Enc}, \text{Dec})$：

$\text{k} \leftarrow \text{Gen}(1^\kappa)$：输出密钥 $\text{k} \in \mathcal{K}$
$c \leftarrow \text{Enc}_\text{k}(m)$：输入 $\text{k} \in \mathcal{K}$ 与 $m \in \mathcal{M}$，输出 $c \in \mathcal{E}$
$m \leftarrow \text{Dec}_\text{k}(c)$：输入 $\text{k} \in \mathcal{K}$ 与 $c \in \mathcal{E}$，输出 $m \in \mathcal{M} \cup \{\perp\}$

正确性：对任意 $k \leftarrow Gen(1^\kappa)$ 和 $m \in M$，有 $Dec_k(Enc_k(m)) = m$
IND-CPA 安全性：与公钥场景不同的是，敌手可能拥有一个可自适应调用的加密接口 $Enc_k(\cdot)$，若对任意 PPT 敌手 $\mathcal{A}$ 满足下式，则称 $\Pi = \text{(Gen, Enc, Dec)}$ 是 IND-CPA 安全的：

\[ \Pr\left[ \begin{array}{l} k \leftarrow Gen(1^\kappa); (m_0,m_1) \leftarrow \mathcal{A}^{Enc_k(\cdot)}(1^\kappa); \\ b \leftarrow \{0,1\}; c \leftarrow Enc_k(m_b); \\ b' \leftarrow \mathcal{A}^{Enc_k(\cdot)}(1^\kappa,c,m_0,m_1) \end{array} : b=b' \right] \le \frac{1}{2}+negl(\kappa) \]

实践结论

若想达到 IND-CPA 安全，通常必须使用随机 IV（Initialization Vector）或 概率加密，单纯的确定性加密通常不满足 IND-CPA 安全。

3.5 消息认证码（Message Authentication Codes, MACs）¶

消息认证码（MAC）

设密钥空间为 $\mathcal{K}$，消息空间为 $\mathcal{M}$，标签空间为 $\mathcal{T}$，MAC 方案包含算法 $(\text{Gen}, \text{Mac}, \text{Ver})$：

$\text{k} \leftarrow \text{Gen}(1^\kappa)$：输出密钥 $\text{k} \in \mathcal{K}$
$t \leftarrow \text{Mac}_\text{k}(m)$：输入 $\text{k}$ 与 $m \in \mathcal{M}$，输出标签 $t \in \mathcal{T}$
$0/1 \leftarrow \text{Ver}_\text{k}(m, t)$：验证标签合法性

正确性：对任意 $k \leftarrow \text{Gen}(1^\kappa)$ 与 $m \in \mathcal{M}$，有 $\text{Ver}_k(m, \text{Mac}_k(m)) = 1$
安全性：若对任意敌手 $\mathcal{A}$，其伪造一个新消息合法标签的概率可忽略，即：

\[ \Pr\left[ \begin{aligned} &\text{k} \leftarrow \text{Gen}(1^\kappa);\ m' \leftarrow \mathcal{A}(1^\kappa); \\ &t' \leftarrow \text{Mac}_\text{k}(m');\ (m, t) \leftarrow \mathcal{A}(1^\kappa, m', t') \end{aligned} : \text{Ver}_\text{k}(m, t) = 1 \land m \neq m' \right] \leq \text{negl}(\kappa) \]

则称 $\Pi = (\text{Gen}, \text{Mac}, \text{Ver})$ 为信息论安全的一次性 MAC

线性一次性 MAC

令消息空间 $\mathcal{M}$、标签空间 $\mathcal{T}$ 都为 $\mathbb{Z}_p$，密钥 $(a,b)\leftarrow \mathbb{Z}_p^2$，定义：

\[ Mac_{a,b}(m)=a \cdot m + b \pmod p \]

3. 6 承诺（Commitments）¶

隐藏性（Hiding）：在打开之前，接收方无法得知承诺的消息 $m$
绑定性（Binding）：承诺方一旦生成承诺值 $c$，之后就不能把它解释成另一个不同消息 $m' \ne m$

常见构造

Hash-based 承诺：$c=H(m \| r)$，一般依赖随机谕示机模型
Pedersen 承诺：$c=g^m h^r$，基于离散对数困难性，具有完美隐藏、计算绑定性质

3.7 茫然传输（Oblivious Transfer, OT）¶

接收方隐私：发送方不知道接收方选择了哪一条，即不知道 $b$
发送方隐私：接收方只能知道 $x_b$，不知道另一条消息 $x_{1-b}$

1. 可证明安全的协议在现实中一定安全吗？

不一定。

可证明安全只说明协议在某个形式化模型和明确假设下安全。
现实中还可能出现：

侧信道攻击
实现漏洞
随机数生成错误
物理攻击
系统配置问题

2. 密码学游戏与日常游戏的共同点是什么？

两者都强调：

规则明确
参与方行为明确
交互流程清晰
胜负判定条件清晰

现代密码学的很多安全定义，本质上就是把“安全”写成一个可判定输赢的游戏。

3. 随机谕示机与现实哈希函数的区别是什么？

随机谕示机：理想化黑盒，对每个新输入返回真正随机值
现实哈希函数：确定性算法，只能尽量逼近这种理想行为

因此，RO 模型下的安全证明具有很强启发意义，但不能机械等同于现实绝对安全。

4. 若 P = NP，是否仍然存在 PRG？

通常认为不存在。

原因在于：

PRG 的构造通常依赖单向函数
若 $P=NP$，则单向函数不复存在
没有单向函数，就无法支撑标准意义上的 PRG