流密码的语义安全性与PRG的安全性 | 您所在的位置:网站首页 › 酷学途密码是啥 › 流密码的语义安全性与PRG的安全性 |
PRG的安全性
PRG(Pseudo-random generators)即伪随机生成器。直观来说,PRG是一个高效的确定性算法,它以一个比特串作为输入,输出一个比特串,并且为了实用性一般情况下满足。那么PRG的安全性是什么含义呢?其实从PRG的名字就可以看得出来,PRG的安全性指的就是其输出具有伪随机性,即对于来说,和是计算不可区分的。形式化描述如下: 现在有一个PRG记为,一个挑战者,一个敌手,两个experiment记为和分别如下工作: : 以作为的输入得到一个比特长的输出并发送给; 向返回一个比特; 输出 : 随机选取并发送给; 向返回一个比特; 输出 定义experiment的方式在密码学中非常常见,通俗的来说,这里的experiment可以理解为两个平行宇宙中的房间,这两个房间所有的参数都是相同的,只有接受的输入可能不同。敌手从房间的窗户中接受输入串以后,根据输入来判断它现在处于哪个宇宙即在接受哪个experiment的考验。那么在这儿的话,向返回的代表认为它收到的串是一个PRG的输出(0)还是一个真正的随机串(1)。为了衡量PRG的安全性,我们需要定义什么情况下PRG可以被认为是安全的,而显然,PRG的安全性和敌手的能力是相关的。从上面的两个experiment我们就可以看出,PRG是安全的当且仅当无法高效识别它收到的串是PRG生成的还是一个真正的随机串,因此我们可以定义的优势如下:
其中代表事件中敌手输出1,代表事件中敌手输出1。因此PRG是安全的当且仅当 |
CopyRight 2018-2019 实验室设备网 版权所有 |