[人工智能]【密码学复习】【Chapter 2】【完美保密】

第二章 完美保密

Part 0 任务

• 证明一比特完美保密
• 证明完美保密的等价公式
• 证明完美保密等价不可区分性
• 证明一次一密是完美保密
• 证明完美保密的局限性

Part 1 定义和基本属性

• 随机变量： $K,M,C$
• 概率：$\mathrm{Pr}[K=k],\mathrm{Pr}[M=m],\mathrm{Pr}[C=c]$

1.1 定义完美保密

• 在$\mathcal{M}$上$\Pi$是完美保密的，若对于$\mathcal{M}$上的任意概率分布, $?m\in \mathcal{M}$ 与 $?c\in \mathcal{C}$ , 且 $\mathrm{Pr}[C=c]>0$:

  $$\mathrm{Pr}[M=m|C=c]=\mathrm{Pr}[M=m].$$

• 某个明文被发送的后验似然与该明文被发送的先验概率没有差别

1.2 一比特上的完美保密

• M = K = { 0 , 1 } , E n c k ( m ) = m ⊕ k \mathcal{M}=\mathcal{K} = \{ 0,1 \} , \mathsf{Enc}_k(m)= m \oplus k M=K={0,1},Enck?(m)=m⊕k
• 证明
• 只要密钥是均匀随机的，那么密文的概率分布就不收明文概率分布的影响；
• 虽然密文不独立与明文，但是密文是由明文和密钥共同决定的

1.3 完美保密的等价形式

• $\mathrm{Pr}[C=c|M=m]=\mathrm{Pr}[C=c]$
• 密文的先验概率等于其后验概率

1.4 完美不可区分性

• $\mathrm{Pr}[C=c|M=m_0]=\mathrm{Pr}[C=c|M=m_1]$
• 攻击者无法区分出密文是由哪个明文加密得到的

Part 2 一次一密 Vernam’s Cipher

• 定义
  • M = K = C = { 0 , 1 } l \mathcal{M} = \mathcal{K} = \mathcal{C} = \{0, 1\}^l M=K=C={0,1}l
  • $k\leftarrow Gen$，以$2^{?l}$的概率随机选择$k$
  • $c:=En{c}_k(m)=k\oplus m$
  • $m:=De{c}_k(c)=k\oplus c$
• 证明其完美保密性

Part 3 完美保密的局限性

• 密钥空间必须大于等于明文空间

• 证明

• 二次加密是错误的

• $c\oplus c^{\prime }=(m\oplus k)\oplus (m^{\prime }\oplus k)=m\oplus m^{\prime }$

Part 4 香农定理

• 当明文空间、密钥空间和密文空间规模相同时，加密方案是完美保密的，当且仅当满足两个条件：
  • （1）每个密钥是从密钥空间中均匀随机生成的；
  • （2）对于任意明文和密文对，存在唯一的密钥使得该明文加密成该密文。

Part 5 窃听不可区分性

5.1 窃听不可区分实验$Priv{K}_{\mathrm{A},\Pi }^{eav}(n)$

• 定义

  1. 给敌手$\mathrm{A}$指定$1^n$作为输入，(敌手在多项式时间内)输出一对等长的消息$m_0,m_1$
  2. 产生随机密钥$k\leftarrow Gen(1^n)$，随机选择一个比特 b ← { 0 , 1 } b \leftarrow \{0, 1\} b←{0,1}，计算密文$c\leftarrow En{c}_k(m_b)$并交给$\mathrm{A}$
  3. $\mathrm{A}$输出一个比特$$\begin{gathered} b^{{ \\ }^{\prime }} \end{gathered}$$
  4. 如果$$\begin{gathered} b^{{ \\ }^{\prime }}=b \end{gathered}$$，则实验输出为$1$，否则为$0$。如果$Priv{K}_{\mathrm{A},\Pi }^{eav}(n)=1$，则称敌手成功。

• 注意：每次实验使用新生成的密钥
  

5.2 完美保密下的窃听不可区分性

• $\mathrm{Pr}[Priv{k}_{\mathcal{A},\Pi }^{eav}=1]=\frac{1}{2}$