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

相比 EAV- ， CPA- 的敌手不需要一次性给出所有的明文，可以一点点查询。这样的好处是后面的查询可以根据此前的查询进行调整。
多次加密 CPA-
简单来说，对于敌手需要猜测的b b b ，敌手可以无限构造等长的m 0 m_0 m0? ， m 1 m_1 m1? ，查询Enc k ( m b ) \text{Enc}_k(m_b) Enck?(mb?) 。
一个结论是 CPA- 与多次加密 CPA- 等价。对此的直观理解是，多次加密的好处是能多次获得b b b 的信息，而不能多获得任何关于Π \Pi Π 的信息。破解密码的本质是通过各种手段，对明文的分布的认识发生了变化。那么多获得b b b 的信息是无法实现的。
CCA-
CCA- 是在选择密文的情况下保证安全

文章插图
针对加密方案Π = ( Gen,Enc,Dec ) \Pi = (\text{Gen, Enc, Dec}) Π=(Gen,Enc,Dec) 和敌手A \{A} A ，定义实验PrivK A , Π cca ( n ) \text{PrivK}^{\text{cca}}_{\{A},\Pi}(n) ,Πcca?(n)：
感觉 CCA- 主要是有理论价值，使用价值可能不太大。
伪随机
现实中生成长度为n n n 的随机数，复杂度远超生成长度为1 1 1 的随机数的n n n 倍。因为生成随机数需要足够的随机源。通常来讲，这样的随机源是有限的。这时就需要伪随机了。
伪随机生成器
G G G 是一个确定性多项式时间算法，且对于任意输入s ∈ { 0 , 1 } n s \in \{0,1\}^n s∈{0,1}n ， G ( s ) G(s) G(s) 为长度为l ( n ) l(n) l(n) 的字符串。
G G G 是伪随机生成器当且仅当：
【可证明安全——对称加密】相比此前定义安全等级的实验，敌手可以选择明文，判断伪随机生成器的算法是不能指定s s s 的，甚至它不能知道输入的s s s 。每次调用伪随机生成器，都只是从中获取一个结果。
伪随机函数
F : { 0 , 1 } ? × { 0 , 1 } ? → { 0 , 1 } ? F :\{0,1\}^* \times \{0,1\}^* \ \{0,1\}^* F:{0,1}?×{0,1}?→{0,1}? ，是一个高效算法。输入的第一个参数是秘钥，第二个参数是自变量，输出与自变量等长。
F F F 是伪随机函数当且仅当：
同理可定义伪随机排列
CPA- 构造固定长度
F F F 是一个伪随机函数。定义加密长度为n n n 的加密方案如下：
任意长度
最常用的是 CBC 模型：
其中I V IV IV 是长度为n n n 的初始化向量。最终的密文是< I V , c 1 , c 2 , . . . , c l >