可证明安全——对称加密 _伪随机

计算安全性 ( )
达不到完美安全（无信息泄露），安全性基于计算的复杂性。对于一个高效的敌手（计算的时间不很长），其攻击成功的概率很低。具体来说，有以下两种正式定义：
具体方法
如果一个加密方案，对任意至多计算时间为t t t 的敌手，攻击成功概率不超过? \ ? ，则称这个方案是( t , ? ) ? s e c u r e (t,\)- (t,?)? 。
很显然，这个定义并不是很直接，因为不好描述“任意敌手” 。
渐进方法
首先，渐进方法定义了一个安全参数n n n 。通常来说，这个参数可以简单地理解为秘钥的长度。
如果一个方案，对于任意多项式时间的敌手，攻破成功的概率为可忽略量，则称该方案是安全的。
敌手本质是一个算法，多项式时间是指? k ∈ N \exist k \in N ?k∈N ，这个算法的复杂度是O ( n k ) O(n^k) O(nk) 。可忽略量是小于任何多项式的倒数，也就是说，对? k ∈ N \ k \in N ?k∈N ，攻破成功的概率为O ( n ? k ) O(n^{-k}) O(n?k) 。
安全等级单次加密 EAV-
EAV- ，是指在窃听攻击的情况下安全。
针对加密方案Π = ( Gen,Enc,Dec ) \Pi = (\text{Gen, Enc, Dec}) Π=(Gen,Enc,Dec) 和敌手A \{A} A ，首先定义实验PrivK A , Π eav ( n ) \text{PrivK}^{\text{eav}}_{\{A},\Pi}(n) ,Πeav?(n)
对任意加密方案Π \Pi Π ， EAV- 有如下两个定义：
对任意多项式时间敌手 A \{A} A ，
Pr ? [ PrivK A , Π eav ( n ) = 1 ] ≤ 1 2 + negl ( n ) \Pr[\text{PrivK}^{\text{eav}}_{\{A},\Pi}(n) = 1] \le \frac 12 + \text{negl}(n) Pr[,Πeav?(n)=1]≤21?+negl(n)
或
∣ Pr ? [ out A ( PrivK A , Π eav ( n , 0 ) ) = 1 ] ? Pr ? [ out A ( PrivK A , Π eav ( n , 1 ) ) = 1 ] ∣ ≤ negl ( n ) |\Pr[\text{out}_{\{A}}(\text{PrivK}^{\text{eav}}_{\{A},\Pi}(n,0))=1]-\Pr[\text{out}_{\{A}}(\text{PrivK}^{\text{eav}}_{\{A},\Pi}(n,1))=1]| \le \text{negl}(n) ∣Pr[outA?(,Πeav?(n,0))=1]?Pr[outA?(,Πeav?(n,1))=1]∣≤negl(n)
值得一提的是，两个定义都是基于概率的。实验的随机性正来自于秘钥的生成。现实中，都是先确定秘钥后有攻击的敌手。而实验中却是先有敌手后生成秘钥。但由于成功攻破的概率是可忽略量，这样的差距是可以忽略不计的。
以上两个定义的等价性是显然的。
多次加密 EAV-
针对加密方案Π = ( Gen,Enc,Dec ) \Pi = (\text{Gen, Enc, Dec}) Π=(Gen,Enc,Dec) 和敌手A \{A} A ，定义实验PrivK A , Π mult ( n ) \text{PrivK}^{\text{mult}}_{\{A},\Pi}(n) ,Πmult?(n)
任意加密方案Π \Pi Π ，是多次加密 EAV- ，当且仅当
Pr ? [ PrivK A , Π mult ( n ) = 1 ] ≤ 1 2 + negl ( n ) \Pr[\text{PrivK}^{\text{mult}}_{\{A},\Pi}(n) = 1] \le \frac 12 + \text{negl}(n) Pr[,Πmult?(n)=1]≤21?+negl(n)
显然，多次加密 EAV- 强于单次加密 EAV- 。一个多次加密 EAV- 的加密方案，必然在加密时需要引入随机性。
CPA-
CPA- 是在选择明文攻击的情况下保持安全，敌手可以无限加密任何想加密的明文。
单次加密 CPA-
针对加密方案Π = ( Gen,Enc,Dec ) \Pi = (\text{Gen, Enc, Dec}) Π=(Gen,Enc,Dec) 和敌手A \{A} A ，定义实验PrivK A , Π cpa ( n ) \text{PrivK}^{\text{cpa}}_{\{A},\Pi}(n) ,Πcpa?(n)：
事实上， CPA- 显著强于多次加密 EAV- 。不妨设在PrivK A , Π eav \text{PrivK}^{\text{eav}}_{\{A},\Pi} ,Πeav? 实验中，敌手查询前t ? 1 t-1 t?1 个时攻破的概率为可忽略量，查询第t t t 个时攻破的概率为不可忽略量。那么对于PrivK A , Π cpa \text{PrivK}^{\text{cpa}}_{\{A},\Pi} ,Πcpa? 实验，可以先查m 0 , i m_{0,i} m0,i? 和m 1 , i m_{1,i} m1,i? ， i ≤ t ? 1 i \le t - 1 i≤t?1 ，然后输出m 0 , t m_{0,t} m0,t? 和m 1 , t m_{1, t} m1,t? 进行最终的判断。