伪随机函数用于构建CPA-secure private key encryption scheme

CPA不可区分实验PrivK_{\Alpha, \Pi}^{cpa}(n)

定义

生成密钥k \leftarrow Gen(1^n)
将1^n提供给Alpha，在其访问能力下能够使用预言机对任何消息进行加密，并获取一对等长的消息m_0, m_1
从\{0, 1\}中随机选取一个比特位b并计算c \leftarrow Enc_k(m_b)传递给Alpha
Alpha仍然拥有访问预言机的能力，在多项式时间内能够对任意消息进行加密，并返回一个比特b'
如果比较结果为b' = b则实验成功并输出结果为1；否则输出结果为0；若PrivK_{\Alpha, \Pi}^{cpa}(n) = 1，则表示Alpha成功完成了任务

理解

在该实验中，Alpha获得了增强的能力：具有加密任意一条预期的信息。

在本实验中，生成密钥被视为第一步；为此Alpha准备了；基于Alpha^{Enc_k(⋅)}可以选择输出消息m0和m1。

值得注意的是，在本研究中我们发现：所有确定性加密方案都无法在该实验中实现；其核心原因在于该实验仅依赖于预言机即可识别加密的消息。

CPA不可区分性

定义

基于对称密钥机制的设计方案Π=(Gen, Enc, Dec)，对于每一个概率多项式攻击者Alpha而言，则满足：P