现代密码学3.3 |
您所在的位置：网站首页 › 暗影骑士擎是什么系列的 › 现代密码学3.3 |
现代密码学3.3
|
现代密码学3.3--伪随机生成器/PRG
PRG
归约证明
基于PRG构造计算安全（唯密文攻击）的密码方案
构造密码方案 Π \Pi Π
基于PRG，证明密码方案 Π \Pi Π的计算安全
博主正在学习INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些笔记供自己回忆，如有错误请指正。整理成一个系列现代密码学，方便检索。 第二章定义的完美安全是一种理论上的讨论，而第三章需要定义的计算安全是一种更偏向实际需求的讨论。 3.1节讨论了定义计算安全的两种方法，3.2节讨论了什么是计算安全。1.4节介绍了现代密码的三大原则：定义+假设+安全性证明，现在定义了计算安全，还需要有一个假设，才能构造能够进行安全性证明的密码方案， 所以3.3节： 介绍一个常见的假设工具：伪随机生成器/pseudorandom generator/PRG， 如何基于困难问题来构造密码方案 以及基于PRG(困难问题)构造密码方案的实例。 PRG 原因：生成真随机比特是难的且慢的 过程：“短的、均匀的”字符串(seed) 生成 “长的，看起来均匀的”字符串 定义原因：需要进行统计测试确定PRG的合理性，但多少次测试足以保证呢？（不知道多少次，所以需要严格定义定义 l l l是一个多项式， 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满足以下两个性质，则称为PRG。 拓展性： l ( n ) > n , ∀ n l(n)>n,\forall n l(n)>n,∀n（如果 l ( n ) ≤ n l(n)\le n l(n)≤n，则没有用PRG的意义，直接用真随机就可以满足， l l l被称为 G G G的扩张因子） 伪随机性：对于任意PPT敌手 D D D，都有可忽略函数 n e g l negl negl满足 ∣ P r [ D ( G ( s ) ) = 1 ] − P r [ D ( r ) = 1 ] ∣ ≤ n e g l ( n ) , r ∈ { 0 , 1 } l ( n ) |Pr[D(G(s))=1]-Pr[D(r)=1]|\le negl(n),r\in \{0,1\}^{l(n)} ∣Pr[D(G(s))=1]−Pr[D(r)=1]∣≤negl(n),r∈{ 0,1}l(n)均匀随机。暴力破解可以区分伪随机和真随机，但这并不影响伪随机的合理性。不过这告诉我们seed需要足够长，不会被遍历，通常选|seed|=安全参数 归约证明
归约思想：如果存在PPT敌手 A \mathcal{A} A以不可忽略的概率 ϵ \epsilon ϵ攻破密码方案，则构造PPT敌手 A ′ \mathcal{A}' A′调用 A \mathcal{A} A，可以解决困难问题；因为假设问题是困难的，所以推出矛盾。 归约过程 找到PPT敌手 A \mathcal{A} A，尝试攻破密码方案 Π \Pi Π，成功概率为 ϵ ( n ) \epsilon(n) ϵ(n) 构造PPT敌手 A ′ \mathcal{A}' A′，尝试解决困难问题X，调用 A \mathcal{A} A作为子线程。如果 A \mathcal{A} |
【本文地址】
今日新闻 |
推荐新闻 |