计算安全性 (computational security)

达不到完美安全（无信息泄露），安全性基于计算的复杂性。对于一个高效的敌手（计算的时间不很长），其攻击成功的概率很低。具体来说，有以下两种正式定义：

具体方法

如果一个加密方案，对任意至多计算时间为 $t$ 的敌手，攻击成功概率不超过 $ϵ$，则称这个方案是 $(t,ϵ)-secure$。

很显然，这个定义并不是很直接，因为不好描述“任意敌手”。

渐进方法

首先，渐进方法定义了一个安全参数 $n$。通常来说，这个参数可以简单地理解为秘钥的长度。

如果一个方案，对于任意多项式时间的敌手，攻破成功的概率为可忽略量，则称该方案是安全的。

敌手本质是一个算法，多项式时间是指 $\exists k\in N$， 这个算法的复杂度是 $O(n^k)$。可忽略量是小于任何多项式的倒数，也就是说，对 $\forall k\in N$，攻破成功的概率为 $O(n^{-k})$。

安全等级

单次加密 EAV-secure

EAV-secure，是指在窃听攻击的情况下安全。

针对加密方案 $\Pi =(\text{Gen, Enc, Dec})$ 和敌手 $\mathcal{A}$， 首先定义实验 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{eav}}(n)$

• 给敌手 $\mathcal{A}$ 安全参数 $n$，敌手输出两个等长的明文 $m_0$，$m_1$
• 通过 $\text{Gen}(1^n)$ 生成秘钥 $k$，并随机选择 b ∈ { 0 , 1 } b \in \{0, 1\} b∈{0,1}，计算密文 $c\leftarrow \text{Enc}(m_b)$，并将 $c$ 给 $\mathcal{A}$。
• $\mathcal{A}$ 输出 $b^{\prime }$。定义 ${\text{out}}_{\mathcal{A}}({\text{PrivK}}_{\mathcal{A},\Pi }^{\text{eav}}(n,b))=b^{\prime }$。
• 如果 $b^{\prime }=b$，则 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{eav}}(n)=1$，否则 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{eav}}(n)=0$。

对任意加密方案 $\Pi$，EAV-secure 有如下两个定义：
对任意多项式时间敌手$\mathcal{A}$，
$$\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{\text{eav}}(n)=1]\le \frac{1}{2}+\text{negl}(n)$$
或
$$|\mathrm{Pr}[{\text{out}}_{\mathcal{A}}({\text{PrivK}}_{\mathcal{A},\Pi }^{\text{eav}}(n,0))=1]-\mathrm{Pr}[{\text{out}}_{\mathcal{A}}({\text{PrivK}}_{\mathcal{A},\Pi }^{\text{eav}}(n,1))=1]|\le \text{negl}(n)$$

值得一提的是，两个定义都是基于概率的。实验的随机性正来自于秘钥的生成。现实中，都是先确定秘钥后有攻击的敌手。而实验中却是先有敌手后生成秘钥。但由于成功攻破的概率是可忽略量，这样的差距是可以忽略不计的。

以上两个定义的等价性是显然的。

多次加密 EAV-secure

针对加密方案 $\Pi =(\text{Gen, Enc, Dec})$ 和敌手 $\mathcal{A}$， 定义实验 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{mult}}(n)$

• 给敌手 $\mathcal{A}$ 安全参数 $n$，敌手输出两列等长的明文 M 0 = { m 0 , 1 , . . . , m 0 , t } M_0 = \{m_{0,1},...,m_{0,t}\} M0​={m0,1​,...,m0,t​}， M 1 = { m 1 , 1 , . . . , m 1 , t } M_1 = \{m_{1,1}, ..., m_{1,t}\} M1​={m1,1​,...,m1,t​}。$M_1$ 与 $M_2$ 的明文对应等长。
• 通过 $\text{Gen}(1^n)$ 生成秘钥 $k$，并随机选择 b ∈ { 0 , 1 } b \in \{0, 1\} b∈{0,1}，计算密文 $c_i\leftarrow {\text{Enc}}_k(m_{b,i})$，并将 $C=(c_1,...,c_t)$ 给 $\mathcal{A}$。
• $\mathcal{A}$ 输出 $b^{\prime }$。
• 如果 $b^{\prime }=b$，则 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{mult}}(n)=1$，否则 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{mult}}(n)=0$。

任意加密方案 $\Pi$，是多次加密 EAV-secure，当且仅当
$$\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{\text{mult}}(n)=1]\le \frac{1}{2}+\text{negl}(n)$$

显然，多次加密 EAV-secure 强于单次加密 EAV-secure。一个多次加密 EAV-secure 的加密方案，必然在加密时需要引入随机性。

CPA-secure

CPA-secure 是在选择明文攻击的情况下保持安全，敌手可以无限加密任何想加密的明文。

单次加密 CPA-secure

针对加密方案 $\Pi =(\text{Gen, Enc, Dec})$ 和敌手 $\mathcal{A}$， 定义实验 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cpa}}(n)$：

• 通过 $\text{Gen}(1^n)$ 生成秘钥 $k$。
• 给敌手 $\mathcal{A}$ 安全参数 $n$ 和 ${\text{Enc}}_k(\cdot )$，敌手两个等长的明文 $m_0$，$m_1$。
• 随机选择 b ∈ { 0 , 1 } b \in \{0, 1\} b∈{0,1}，计算密文 $c\leftarrow {\text{Enc}}_k(m_b)$，并将 $c$ 给 $\mathcal{A}$。
• $\mathcal{A}$ 仍能继续使用 ${\text{Enc}}_k(\cdot )$，并输出 $b^{\prime }$。
• 如果 $b^{\prime }=b$，则 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cpa}}(n)=1$，否则 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cpa}}(n)=0$。

事实上，CPA-secure 显著强于多次加密 EAV-secure。不妨设在 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{eav}}$ 实验中，敌手查询前 $t-1$ 个时攻破的概率为可忽略量，查询第 $t$ 个时攻破的概率为不可忽略量。那么对于 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cpa}}$ 实验，可以先查 $m_{0,i}$ 和 $m_{1,i}$，$i\le t-1$，然后输出 $m_{0,t}$ 和 $m_{1,t}$ 进行最终的判断。

相比 EAV-secure，CPA-secure 的敌手不需要一次性给出所有的明文，可以一点点查询。这样的好处是后面的查询可以根据此前的查询进行调整。

多次加密 CPA-secure

简单来说，对于敌手需要猜测的 $b$，敌手可以无限构造等长的 $m_0$，$m_1$，查询 ${\text{Enc}}_k(m_b)$。

一个结论是 CPA-secure 与多次加密 CPA-secure 等价。对此的直观理解是，多次加密的好处是能多次获得 $b$ 的信息，而不能多获得任何关于 $\Pi$ 的信息。破解密码的本质是通过各种手段，对明文的分布的认识发生了变化。那么多获得 $b$ 的信息是无法实现的。

CCA-secure

CCA-secure 是在选择密文的情况下保证安全

针对加密方案 $\Pi =(\text{Gen, Enc, Dec})$ 和敌手 $\mathcal{A}$， 定义实验 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cca}}(n)$：

• 通过 $\text{Gen}(1^n)$ 生成秘钥 $k$。
• 给敌手 $\mathcal{A}$ 安全参数 $n$， ${\text{Enc}}_k(\cdot )$ 和 $\text{Dec}(\cdot )$，敌手两个等长的明文 $m_0$，$m_1$。
• 随机选择 b ∈ { 0 , 1 } b \in \{0, 1\} b∈{0,1}，计算密文 $c\leftarrow {\text{Enc}}_k(m_b)$，并将 $c$ 给 $\mathcal{A}$。
• $\mathcal{A}$ 仍能继续使用 ${\text{Enc}}_k(\cdot )$ 和 ${\text{Dec}}_k(\cdot )$，但不许查 ${\text{Dec}}_k(m_b)$，并输出 $b^{\prime }$。
• 如果 $b^{\prime }=b$，则 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cpa}}(n)=1$，否则 ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cpa}}(n)=0$。

感觉 CCA-secure 主要是有理论价值，使用价值可能不太大。

伪随机

现实中生成长度为 $n$ 的随机数，复杂度远超生成长度为 $1$ 的随机数的 $n$ 倍。因为生成随机数需要足够的随机源。通常来讲，这样的随机源是有限的。这时就需要伪随机了。

伪随机生成器

$G$ 是一个确定性多项式时间算法，且对于任意输入 s ∈ { 0 , 1 } n s \in \{0,1\}^n s∈{0,1}n，$G(s)$ 为长度为 $l(n)$ 的字符串。

$G$ 是伪随机生成器当且仅当：

• 对任意 $n$ 都有 $l(n)>n$
• 对任意多项式时间算法 $D$
  $$|\mathrm{Pr}[D(G(s))=1]-\mathrm{Pr}[D(r)=1]|\le \text{negl}(n)$$
  其中 $s$ 是 { 0 , 1 } n \{0,1\}^n {0,1}n 的随机数，$r$ 是 { 0 , 1 } n \{0,1\}^n {0,1}n 的随机数。

相比此前定义安全等级的实验，敌手可以选择明文，判断伪随机生成器的算法是不能指定 $s$ 的，甚至它不能知道输入的 $s$。每次调用伪随机生成器，都只是从中获取一个结果。

伪随机函数

F : { 0 , 1 } ∗ × { 0 , 1 } ∗ → { 0 , 1 } ∗ F :\{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^* F:{0,1}∗×{0,1}∗→{0,1}∗，是一个高效算法。输入的第一个参数是秘钥，第二个参数是自变量，输出与自变量等长。

$F$ 是伪随机函数当且仅当：

• 对任意多项式时间算法 $D$
  $$|\mathrm{Pr}[D^{F_k(\cdot )}(1^n)=1]-\mathrm{Pr}[D^{f(\cdot )}(1^n)=1]|\le \text{negl}(n)$$

同理可定义伪随机排列

CPA-secure 构造

固定长度

$F$ 是一个伪随机函数。定义加密长度为 $n$ 的加密方案如下：

• $\text{Gen}$：输入 $1^n$，输出随机的 k ∈ { 0 , 1 } n k \in \{0,1\}^n k∈{0,1}n
• $\text{Enc}$：输入 k ∈ { 0 , 1 } n k\in \{0,1\}^n k∈{0,1}n 和明文 m ∈ { 0 , 1 } n m \in \{0,1\}^n m∈{0,1}n，选择随机的 r ∈ { 0 , 1 } n r \in \{0,1\}^n r∈{0,1}n 并输出 $c\leftarrow <r,F_k(r)⨁m>$
• $\text{Dec}$：输入 k ∈ { 0 , 1 } n k \in \{0,1\}^n k∈{0,1}n 和密文 $c=<r,s>$，输出 $m\leftarrow F_k(r)⨁s$

任意长度

最常用的是 CBC 模型：

其中 $IV$ 是长度为 $n$ 的初始化向量。最终的密文是 $<IV,c_1,c_2,...,c_l>$