当前位置：首页 > 编程资源 > 编程问答 >内容正文

编程问答

现代密码学2.1--完美安全和完美不可区分/Perfectly secret, Perfectly indistinguishable

发布时间：2025/3/21 编程问答 37 豆豆

生活随笔收集整理的这篇文章主要介绍了现代密码学2.1--完美安全和完美不可区分/Perfectly secret, Perfectly indistinguishable 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

现代密码学2.1--完美安全和完美不可区分/Perfectly secret, Perfectly indistinguishable

完美安全
- 定义
- 定理
完美不可区分
- 实验过程定义
- 完美不可区分定义
- 定理

博主正在学习INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些笔记供自己回忆，如有错误请指正。整理成一个系列现代密码学，方便检索。

《现代密码学》第一章所介绍的古典密码，全都已经被破解了。之前由于没有正式的定义、精确的假设，无法证明一个密码方案是否具有严格的安全性。在第二章第一节中，《现代密码学》介绍了对抗具有无限算力的攻击者，也能被证明是安全的密码方案的定义，这样的密码方案被称为是完美安全的；而针对攻击者而言，密码方案的完美不可区分是等价于完美安全的。

完美安全

定义

对于信息空间 $M\mathcal{M}$ 上的每一种概率分布，所有信息 $m∈Mm\in \mathcal{M}$ ，所有密文 $c∈Cc\in \mathcal{C}$ ，如果 $P r [C = c] > 0$ ，都满足 $P r [M = m ∣ C = c] = P r [M = m]$ 。

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

定理

如果对于 $∀m,m′∈M,∀c∈C\forall m,m'\in \mathcal{M},\forall c\in \mathcal{C}$ ，都有 $Pr[Enc_K(m)=c]=Pr[Enc_K(m')=c]$ ，那么这个信息空间是 $M\mathcal{M}$ 的密码方案是完美安全的。

证明：
要证明“密码方案是完美安全的”，即证满足“ $P r [M = m ∣ C = c] = P r [M = m]$ ”。

$P r [M = m] = 0$ ，则 $P r [M = m ∣ C = c]$ 肯定也是0，那么有 $P r [M = m ∣ C = c] = P r [M = m]$ ；
$P r [M = m] > 0$ ，
贝叶斯定理得 $Pr[M=m∣C=c]=Pr[C=c∣M=m]⋅Pr[M=m]Pr[C=c]Pr[M=m|C=c]=\frac{Pr[C=c|M=m]\cdot Pr[M=m]}{Pr[C=c]}$ ，
$=Pr[C=c∣M=m]⋅Pr[M=m]∑m′∈MPr[C=c∣M=m′]⋅Pr[M=m′]=\frac{Pr[C=c|M=m]\cdot Pr[M=m]}{\sum_{m'\in \mathcal{M}}Pr[C=c|M=m']\cdot Pr[M=m']}$ ，(1)
因为 $Pr[Enc_K(m)=c]=Pr[Enc_K(m')=c]$ ，所以 $P r [C = c ∣ M = m] = P r [C = c ∣ M = m^{'}]$ ，
那么(1)式可写为 $=Pr[M=m]∑m′∈MPr[M=m′]=Pr[M=m]=\frac{Pr[M=m]}{\sum_{m'\in \mathcal{M}}Pr[M=m']}=Pr[M=m]$

完美不可区分

首先，定义某个实验过程，在此实验的基础上，定义完美不可区分。

实验过程定义

攻击者 $A\mathcal{A}$ 选择两个明文 $m,m′∈Mm,m'\in \mathcal{M}$ ，传给加密方。加密方随机选择一个比特 $b∈{0,1}b\in \{0,1\}$ ，通过加密方案 $Π\Pi$ 进行加密，得到一个密文 $c←Enck(mb)c\leftarrow Enc_k(m_b)$ ，传回给 $A\mathcal{A}$ 。此时，攻击者 $A\mathcal{A}$ 猜测加密方选择的比特是 $b^{'}$ 。如果 $b^{'} = b$ ，那么 $PriKA,Πeav=1PriK_{\mathcal{A},\Pi}^{eav}=1$ ；反之，攻击者 $A\mathcal{A}$ 猜错， $PriKA,Πeav=0PriK_{\mathcal{A},\Pi}^{eav}=0$ 。

完美不可区分定义

如果对于所有的攻击者 $A\mathcal{A}$ ，信息空间为 $M\mathcal{M}$ 的密码方案 $Π\Pi$ 都满足 $Pr[PriKA,Πeav=1]=12Pr[PriK_{\mathcal{A},\Pi}^{eav}=1]=\frac{1}{2}$ ，那么称这种密码方案 $Π\Pi$ 是完美不可区分的。

也就是，对于攻击者而言，这种密码方案加密不同明文，效果都是一样的。

定理

密码方案 $Π\Pi$ 是完美不可区分的，当且仅当 $Π\Pi$ 是完美安全的。

证明：互相规约。
用形式化表示，
完美安全是" $P r [M = m ∣ C = c] = P r [M = m]$ "，
完美不可区分是" $Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$ "，

现在要证" $P r [M = m ∣ C = c] = P r [M = m]$ " $↔\leftrightarrow$ " $Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$ "
先证" $Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$ " $↔\leftrightarrow$ " $P r [C = c ∣ M = m] = P r [C = c]$ "
- 从左到右(特殊 $→\rightarrow$ 一般)：" $Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$ " $→\rightarrow$ " $P r [C = c ∣ M = m] = P r [C = c]$ "
  $Pr[C=c]=∑m∈MPr[C=c∣M=m]⋅Pr[M=m]Pr[C=c]=\sum_{m\in \mathcal{M}}Pr[C=c|M=m]\cdot Pr[M=m]$
  因为 $Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$ ，所以我们可以令 $Pr[C=c∣M=mi]=αPr[C=c|M=m_i]=\alpha$ ，那么
  $Pr[C=c]=∑m∈Mα⋅Pr[M=m]=α⋅∑m∈MPr[M=m]=αPr[C=c]=\sum_{m\in \mathcal{M}}\alpha \cdot Pr[M=m]=\alpha \cdot \sum_{m\in \mathcal{M}}Pr[M=m]=\alpha$
  即 $Pr[C=c]=α=Pr[C=c∣M=m]Pr[C=c]=\alpha =Pr[C=c|M=m]$
- 从右到左(一般 $→\rightarrow$ 特殊)：" $P r [C = c ∣ M = m] = P r [C = c]$ " $→\rightarrow$ " $Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$ "
  因为对于所有的明文信息 $m∈Mm\in \mathcal{M}$ ，都有 $P r [C = c ∣ M = m] = P r [C = c]$ ，所以 $Pr[C=c|M=m_0]=Pr[C=c]=Pr[C=c|M=m_1]$
再证" $P r [C = c ∣ M = m] = P r [C = c]$ " $↔\leftrightarrow$ " $P r [M = m ∣ C = c] = P r [M = m]$ "
$Pr[C=c∣M=m]=Pr[M=m∣C=c]⋅Pr[C=c]Pr[M=m]=Pr[C=c]Pr[C=c|M=m]=\frac{Pr[M=m|C=c]\cdot Pr[C=c]}{Pr[M=m]}=Pr[C=c]$
$→Pr[M=m∣C=c]Pr[M=m]=1\rightarrow \frac{Pr[M=m|C=c]}{Pr[M=m]}=1$
$→Pr[M=m∣C=c]=Pr[M=m]\rightarrow Pr[M=m|C=c]=Pr[M=m]$

总结

以上是生活随笔为你收集整理的现代密码学2.1--完美安全和完美不可区分/Perfectly secret, Perfectly indistinguishable的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。

上一篇：基本数据结构与图
下一篇：现代密码学2.2、2.3--由“一次一密