第二章 完美保密
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)
-
定义
- 给敌手 A \Alpha A指定 1 n 1^n 1n作为输入，(敌手在多项式时间内)输出一对等长的消息 m 0 , m 1 m_0, m_1 m0,m1
- 产生随机密钥 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
- A \Alpha A输出一个比特 b ′ b^{\\'} b′
- 如果 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