現代密碼學2.1--完美安全和完美不可區(qū)分/Perfectly secret, Perfectly indistinguishable

• 完美安全
• • 定義
  • 定理
• 完美不可區(qū)分
• • 實驗過程定義
  • 完美不可區(qū)分定義
  • 定理

博主正在學習INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些筆記供自己回憶，如有錯誤請指正。整理成一個系列現代密碼學，方便檢索。

《現代密碼學》第一章所介紹的古典密碼，全都已經被破解了。之前由于沒有正式的定義、精確的假設，無法證明一個密碼方案是否具有嚴格的安全性。在第二章第一節(jié)中，《現代密碼學》介紹了對抗具有無限算力的攻擊者，也能被證明是安全的密碼方案的定義，這樣的密碼方案被稱為是完美安全的；而針對攻擊者而言，密碼方案的完美不可區(qū)分是等價于完美安全的。

完美安全

定義

對于信息空間$\mathcal{M}$上的每一種概率分布，所有信息$m\in \mathcal{M}$，所有密文$c\in \mathcal{C}$，如果$Pr[C=c]>0$，都滿足$Pr[M=m|C=c]=Pr[M=m]$。

也就是，密文$c\in \mathcal{C}$不會透露任何關于明文$m\in \mathcal{M}$的信息，完美地隱藏了關于被加密明文$m$的所有信息。

定理

如果對于$?m,m^{\prime }\in \mathcal{M},?c\in \mathcal{C}$，都有$Pr[En{c}_K(m)=c]=Pr[En{c}_K(m^{\prime })=c]$，那么這個信息空間是$\mathcal{M}$的密碼方案是完美安全的。

證明：
要證明“密碼方案是完美安全的”，即證滿足“$Pr[M=m|C=c]=Pr[M=m]$”。

• $Pr[M=m]=0$，則$Pr[M=m|C=c]$肯定也是0，那么有$Pr[M=m|C=c]=Pr[M=m]$；
• $Pr[M=m]>0$，
  貝葉斯定理得$Pr[M=m|C=c]=\frac{Pr[C=c|M=m]?Pr[M=m]}{Pr[C=c]}$，
  $=\frac{Pr[C=c|M=m]?Pr[M=m]}{{\sum }_{m^{\prime }\in \mathcal{M}}Pr[C=c|M=m^{\prime }]?Pr[M=m^{\prime }]}$，(1)
  因為$Pr[En{c}_K(m)=c]=Pr[En{c}_K(m^{\prime })=c]$，所以$Pr[C=c|M=m]=Pr[C=c|M=m^{\prime }]$，
  那么(1)式可寫為$=\frac{Pr[M=m]}{{\sum }_{m^{\prime }\in \mathcal{M}}Pr[M=m^{\prime }]}=Pr[M=m]$

完美不可區(qū)分

首先，定義某個實驗過程，在此實驗的基礎上，定義完美不可區(qū)分。

實驗過程定義

攻擊者$\mathcal{A}$選擇兩個明文$m,m^{\prime }\in \mathcal{M}$，傳給加密方。加密方隨機選擇一個比特$b\in \{0,1\}$，通過加密方案$\Pi$進行加密，得到一個密文$c\leftarrow En{c}_k(m_b)$，傳回給$\mathcal{A}$。此時，攻擊者$\mathcal{A}$猜測加密方選擇的比特是$b^{\prime }$。如果$b^{\prime }=b$，那么$Pri{K}_{\mathcal{A},\Pi }^{eav}=1$；反之，攻擊者$\mathcal{A}$猜錯，$Pri{K}_{\mathcal{A},\Pi }^{eav}=0$。

完美不可區(qū)分定義

如果對于所有的攻擊者$\mathcal{A}$，信息空間為$\mathcal{M}$的密碼方案$\Pi$都滿足$Pr[Pri{K}_{\mathcal{A},\Pi }^{eav}=1]=\frac{1}{2}$，那么稱這種密碼方案$\Pi$是完美不可區(qū)分的。

也就是，對于攻擊者而言，這種密碼方案加密不同明文，效果都是一樣的。

定理

密碼方案$\Pi$是完美不可區(qū)分的，當且僅當$\Pi$是完美安全的。

證明：互相規(guī)約。
用形式化表示，
完美安全是"$Pr[M=m|C=c]=Pr[M=m]$"，
完美不可區(qū)分是"$Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$"，

• 現在要證"$Pr[M=m|C=c]=Pr[M=m]$"$?$"$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=m]=Pr[C=c]$"

  • 從左到右(特殊$\to$一般)："$Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$"$\to$"$Pr[C=c|M=m]=Pr[C=c]$"
    $Pr[C=c]={\sum }_{m\in \mathcal{M}}Pr[C=c|M=m]?Pr[M=m]$
    因為$Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$，所以我們可以令$Pr[C=c|M=m_i]=\alpha$，那么
    $Pr[C=c]={\sum }_{m\in \mathcal{M}}\alpha ?Pr[M=m]=\alpha ?{\sum }_{m\in \mathcal{M}}Pr[M=m]=\alpha$
    即$Pr[C=c]=\alpha =Pr[C=c|M=m]$
  • 從右到左(一般$\to$特殊)："$Pr[C=c|M=m]=Pr[C=c]$"$\to$"$Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$"
    因為對于所有的明文信息$m\in \mathcal{M}$，都有$Pr[C=c|M=m]=Pr[C=c]$，所以$Pr[C=c|M=m_0]=Pr[C=c]=Pr[C=c|M=m_1]$

• 再證"$Pr[C=c|M=m]=Pr[C=c]$"$?$"$Pr[M=m|C=c]=Pr[M=m]$"
  $Pr[C=c|M=m]=\frac{Pr[M=m|C=c]?Pr[C=c]}{Pr[M=m]}=Pr[C=c]$
  $\to \frac{Pr[M=m|C=c]}{Pr[M=m]}=1$
  $\to Pr[M=m|C=c]=Pr[M=m]$

總結

以上是生活随笔為你收集整理的现代密码学2.1--完美安全和完美不可区分/Perfectly secret, Perfectly indistinguishable的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。