密码学的形式化

安全定义 = 安全目标 + 威胁模型

尝试给出加密算法的安全目标：

1. 安全目标想法 1：敌手不能够得到密钥 k
   1. 密钥甚至可以不使用，但是这个算法在任何意义上都不安全
2. 给定 c，很难恢复整个明文 m
   1. 只加密前半部分，泄露一半的明文已经不安全了
3. 给定 c，很难恢复任何明文中的字符
   1. 无法保证敌手不能得到明文中的某些关系
   2. 不能作为通用的安全目标，但是可以妥协到这里提高计算能力
4. 不管攻击者已经掌握了什么信息，密文都不应该泄露任何有关底层明文的额外信息
   1. 这个正确

威胁模型应该是限定能力而非策略

1. 唯密文攻击：最基本的攻击，只能得到一个或多个密文

2. 已知明文攻击：额外能够获得明文和密文对

3. 选择明文攻击：额外能够获得其任意选择的明文对应的密文

4. 选择密文攻击：额外能够获得任意的密文对应的明文

5. 适应性：敌手可以有适应性的选择

   1. 非随机化的加密都不是适应性的

6. 非适应性：一次发送多个

几乎所有密码方案的安全性暗含了 $P\ne NP$

安全证明保证了在某种难题假设下，针对某种威胁模型下的敌手，能够达到某种安全目标

• Knowledge: 通过算力提取到的
• Infomation: 任何人能够轻易拿到的东西