Perfect Secrecy(完全保密)
Outline
- Basic Probability Theory(基本概率论)
Conditional probability(传统概率论)
Total probability formula(全概率公式)
Baye’s formula(贝叶斯公式)
- ℳ: Message space M m
- 𝒦: Key space K k
- 𝒞: Ciphertext space C c
Definition
ciphertext reveals nothing about the underlying plaintext
不能从密文中获取任何有关明文的信息称为完全保密
Equivalent Formulation(等效公式)
the probability distribution of the ciphertext does not depend on the plaintext
密文的概率分布不依赖于明文
For any 𝑚, 𝑚′∈”ℳ”, the distribution of the ciphertext when 𝑚 is encrypted should be identical to the distribution of the ciphertext when 𝑚′ is encrypted
任意两个message取自message space加密后的密文的概率分布应该是完全相同的
以下是等效公式：
引理2.4
一个加密模式(Gen、Enc、Dec)对message space M是完全保密当且仅当2.1的公式对任意两个m∈M和任意c∈C都成立
Adversarial indistingguishability
过程阐述：
1.attacker A从message space中取出两个信息，m0,m1发送给challenger
2.challenger接收到m0,m1之后用密钥生成器Gen生成k，并且从{0,1}中选取一个比特作为b，用加密器Enck加密mb形成密文c，将这个密文c称为挑战密文，然后将c传给A
3.A输出一个比特b’
4.如果b=b’，那么PrivK(eav)(A,π)=1,并称A成功了，反之则PrivK(eav)(A,π)=0，称A失败了
An encryption scheme has adversarial indistinguishability if no adversary “𝒜” can succeed with probability better than 1/2.
一个加密模式具有对手不可区分性如果A成功的概率不高于2/1
One-Time Pad(一次一密)
解释：
- Gen:一个根据均匀分布从l长的比特串中选取k的密钥生成算法
- Enc:得到l长的比特串的密钥k和l长的比特串信息m，通过加密算法输出密文：c=k⊕m
- Dec:得到密钥k和密文c，通过解密算法输出信息：m=k⊕c
一次一密符合完全保密定义
Limitations of Perfect Secrecy
如果(Gen,Enc,Dec)是完善加密模式，那么密钥空间K大于信息空间M
