流密码的语义安全性与PRG的安全性

2024-07-07 09:35| 来源: 网络整理| 查看: 265

PRG的安全性

PRG(Pseudo-random generators)即伪随机生成器。直观来说，PRG是一个高效的确定性算法，它以一个比特串 $s$ 作为输入，输出一个比特串 $r$ ，并且为了实用性一般情况下满足 $|s|\ll|r|$ 。那么PRG的安全性是什么含义呢？其实从PRG的名字就可以看得出来，PRG的安全性指的就是其输出具有伪随机性，即对于 $r$ 来说， $r$ 和 $r^\prime\xleftarrow{R}\{0,1\}^{|r|}$ 是计算不可区分的。形式化描述如下：

现在有一个PRG记为 $\mathcal{G}$ ，一个挑战者 $\mathcal{C}$ ，一个敌手 $\mathcal{A}$ ，两个experiment记为 $PrgExp_{0}^{\mathcal{G},\mathcal{A}}$ 和 $PrgExp_{1}^{\mathcal{G},\mathcal{A}}$ 分别如下工作：

$PrgExp_{0}^{\mathcal{G},\mathcal{A}}$ :

$\mathcal{C}$ 以 $s$ 作为 $\mathcal{G}$ 的输入得到一个 $L$ 比特长的输出 $r$ 并发送给 $\mathcal{A}$ ;

$\mathcal{A}$ 向 $\mathcal{C}$ 返回一个比特 $b^\prime$ $\in\{0,1\}$ ；

输出 $b^\prime$

$PrgExp_{1}^{\mathcal{G},\mathcal{A}}$ :

$\mathcal{C}$ 随机选取 $r$ $\in\{0,1\}^L$ 并发送给 $\mathcal{A}$ ;

$\mathcal{A}$ 向 $\mathcal{C}$ 返回一个比特 $b^\prime$ $\in\{0,1\}$ ；

输出 $b^\prime$

定义experiment的方式在密码学中非常常见，通俗的来说，这里的experiment可以理解为两个平行宇宙中的房间，这两个房间所有的参数都是相同的，只有接受的输入可能不同。敌手从房间的窗户中接受输入串以后，根据输入来判断它现在处于哪个宇宙即在接受哪个experiment的考验。那么在这儿的话， $\mathcal{A}$ 向 $\mathcal{C}$ 返回的 $b^\prime$ 代表 $\mathcal{A}$ 认为它收到的串 $r$ 是一个PRG的输出（0）还是一个真正的随机串（1）。为了衡量PRG的安全性，我们需要定义什么情况下PRG可以被认为是安全的，而显然，PRG的安全性和敌手 $\mathcal{A}$ 的能力是相关的。从上面的两个experiment我们就可以看出，PRG是安全的当且仅当 $\mathcal{A}$ 无法高效识别它收到的串 $r$ 是PRG生成的还是一个真正的随机串，因此我们可以定义 $\mathcal{A}$ 的优势如下：

$PRGadv[\mathcal{A},\mathcal{G}]:=|P(W_0)-P(W_1)|$

其中 $W_0$ 代表事件 $PrgExp_{0}^{\mathcal{G},\mathcal{A}}$ 中敌手输出1， $W_1$ 代表事件 $PrgExp_{1}^{\mathcal{G},\mathcal{A}}$ 中敌手输出1。因此PRG是安全的当且仅当

【本文地址】

公司简介

联系我们