【密码学复习】【Chapter2】【完美保密】

第二章 完美保密

Part 0 任务

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

Part 1 定义和基本属性

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

1.1 定义完美保密

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

  
  
  
  
  
  Pr
  
  
  ⁡
  
  
  [
  
  
  M
  
  
  =
  
  
  m
  
  
  ∣
  
  
  C
  
  
  =
  
  
  c
  
  
  ]
  
  
  =
  
  
  Pr
  
  
  ⁡
  
  
  [
  
  
  M
  
  
  =
  
  
  m
  
  
  ]
  
  
  .
  
  
  
  \Pr[M=m | C=c] = \Pr[M=m].
  
  
  Pr[M=m∣C=c]=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 完美保密的等价形式

• 
  
  
  
  
  Pr
  
  
  ⁡
  
  
  [
  
  
  C
  
  
  =
  
  
  c
  
  
  ∣
  
  
  M
  
  
  =
  
  
  m
  
  
  ]
  
  
  =
  
  
  Pr
  
  
  ⁡
  
  
  [
  
  
  C
  
  
  =
  
  
  c
  
  
  ]
  
  
  
  \Pr[C=c | M=m] = \Pr[C=c]
  
  
  Pr[C=c∣M=m]=Pr[C=c]
• 密文的先验概率等于其后验概率

1.4 完美不可区分性

• 
  
  
  
  
  Pr
  
  
  ⁡
  
  
  [
  
  
  C
  
  
  =
  
  
  c
  
  
  ∣
  
  
  M
  
  
  =
  
  
  
  m
  
  
  0
  
  
  
  ]
  
  
  =
  
  
  Pr
  
  
  ⁡
  
  
  [
  
  
  C
  
  
  =
  
  
  c
  
  
  ∣
  
  
  M
  
  
  =
  
  
  
  m
  
  
  1
  
  
  
  ]
  
  
  
  \Pr[C = c | M = m_0] = \Pr[C = c | M = m_1]
  
  
  Pr[C=c∣M=m0​]=Pr[C=c∣M=m1​]
• 攻击者无法区分出密文是由哪个明文加密得到的

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
    
    
    ←
    
    
    G
    
    
    e
    
    
    n
    
    
    
    k \leftarrow Gen
    
    
    k←Gen，以
    
    
    
    
    
    2
    
    
    
    −
    
    
    l
    
    
    
    
    
    2^{-l}
    
    
    2−l的概率随机选择
    
    
    
    
    k
    
    
    
    k
    
    
    k
  • 
    
    
    
    
    c
    
    
    :
    
    
    =
    
    
    E
    
    
    n
    
    
    
    c
    
    
    k
    
    
    
    (
    
    
    m
    
    
    )
    
    
    =
    
    
    k
    
    
    ⊕
    
    
    m
    
    
    
    c := Enc_k(m) = k \oplus m
    
    
    c:=Enck​(m)=k⊕m
  • 
    
    
    
    
    m
    
    
    :
    
    
    =
    
    
    D
    
    
    e
    
    
    
    c
    
    
    k
    
    
    
    (
    
    
    c
    
    
    )
    
    
    =
    
    
    k
    
    
    ⊕
    
    
    c
    
    
    
    m := Dec_k(c) = k \oplus c
    
    
    m:=Deck​(c)=k⊕c
• 证明其完美保密性

Part 3 完美保密的局限性

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

• 证明

• 二次加密是错误的

• 
  
  
  
  
  c
  
  
  ⊕
  
  
  
  c
  
  
  ′
  
  
  
  =
  
  
  (
  
  
  m
  
  
  ⊕
  
  
  k
  
  
  )
  
  
  ⊕
  
  
  (
  
  
  
  m
  
  
  ′
  
  
  
  ⊕
  
  
  k
  
  
  )
  
  
  =
  
  
  m
  
  
  ⊕
  
  
  
  m
  
  
  ′
  
  
  
  
  c\oplus c'=(m\oplus k)\oplus (m'\oplus k)=m\oplus m'
  
  
  c⊕c′=(m⊕k)⊕(m′⊕k)=m⊕m′

Part 4 香农定理

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

Part 5 窃听不可区分性

5.1 窃听不可区分实验




P


r


i


v



K



A


,


Π




e


a


v




(


n


)



PrivK_{\Alpha, \Pi}^{eav}(n)


PrivKA,Πeav​(n)

• 定义

  
  
  1. 给敌手
     
     
     
     
     A
     
     
     
     \Alpha
     
     
     A指定
     
     
     
     
     
     1
     
     
     n
     
     
     
     
     1^n
     
     
     1n作为输入，(敌手在多项式时间内)输出一对等长的消息
     
     
     
     
     
     m
     
     
     0
     
     
     
     ,
     
     
     
     m
     
     
     1
     
     
     
     
     m_0, m_1
     
     
     m0​,m1​
  2. 产生随机密钥
     
     
     
     
     k
     
     
     ←
     
     
     G
     
     
     e
     
     
     n
     
     
     (
     
     
     
     1
     
     
     n
     
     
     
     )
     
     
     
     k \leftarrow Gen(1^n)
     
     
     k←Gen(1n)，随机选择一个比特
     
     
     
     
     b
     
     
     ←
     
     
     {
     
     
     0
     
     
     ,
     
     
     1
     
     
     }
     
     
     
     b \leftarrow \{0, 1\}
     
     
     b←{0,1}，计算密文
     
     
     
     
     c
     
     
     ←
     
     
     E
     
     
     n
     
     
     
     c
     
     
     k
     
     
     
     (
     
     
     
     m
     
     
     b
     
     
     
     )
     
     
     
     c \leftarrow Enc_k(m_b)
     
     
     c←Enck​(mb​)并交给
     
     
     
     
     A
     
     
     
     \Alpha
     
     
     A
  3. 
     
     
     
     
     A
     
     
     
     \Alpha
     
     
     A输出一个比特
     
     
     
     
     
     b
     
     
     
     
     ′
     
     
     
     
     
     b^{\\'}
     
     
     b′
  4. 如果
     
     
     
     
     
     b
     
     
     
     
     ′
     
     
     
     
     =
     
     
     b
     
     
     
     b^{\\'} = b
     
     
     b′=b，则实验输出为
     
     
     
     
     1
     
     
     
     1
     
     
     1，否则为
     
     
     
     
     0
     
     
     
     0
     
     
     0。如果
     
     
     
     
     P
     
     
     r
     
     
     i
     
     
     v
     
     
     
     K
     
     
     
     A
     
     
     ,
     
     
     Π
     
     
     
     
     e
     
     
     a
     
     
     v
     
     
     
     
     (
     
     
     n
     
     
     )
     
     
     =
     
     
     1
     
     
     
     PrivK_{\Alpha, \Pi}^{eav}(n) = 1
     
     
     PrivKA,Πeav​(n)=1，则称敌手成功。

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

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

• 
  
  
  
  
  Pr
  
  
  ⁡
  
  
  [
  
  
  P
  
  
  r
  
  
  i
  
  
  v
  
  
  
  k
  
  
  
  A
  
  
  ,
  
  
  Π
  
  
  
  
  e
  
  
  a
  
  
  v
  
  
  
  
  =
  
  
  1
  
  
  ]
  
  
  =
  
  
  
  1
  
  
  2
  
  
  
  
  \Pr[Privk_{\mathcal{A}, \Pi}^{eav} = 1] = \frac{1}{2}
  
  
  Pr[PrivkA,Πeav​=1]=21​