negl 可忽视函数定义

一个定义在自然数集上的非负函数 是可忽视的当且仅当对任意的正多项式 都存在一个自然数 使得对于任意的大于 的整数，满足

一个等价的定义：

如果对任意一个 满足 那么就是可忽视的

计算安全

The Adeversarial indistinguishable experiment (计算安全实验)

对于模式 实验

  1. 首先输入参数 攻击者 给出两个等长的明文 然后输出给加密算法
  2. 加密算法随机依据安全参数调用生成器 Gen 随机生成密钥 key 然后随机采样 加密 并把密文给到
  3. 输出一个
  4. 如果 那么 赢得这个实验，即 否则为0

计算安全定义

如果上面的实验满足对于任意的PPT时间内的敌手，都有

那么这个加密方式是满足 eav 不可区分的。

CPA 安全

CPA安全实验

  1. 首先运行密钥生成器 Gen 生成一个密钥 key
  2. 攻击者有向加密器 Enc 加密长度为 神谕机访问权限，并且可以根据访问得到的明文-密文对决定输出一对消息 ，长度也是 的
  3. 加密算法随机生成一个bit，即随机采样 然后输出密文 给到
  4. 攻击者 还有访问加密神谕机的机会，并最终给出一个
  5. 如果 就认为攻击者 赢得这次实验，整体输出1，否则输出0

CPA 安全定义

如果上面的实验满足对于任意的PPT时间内的敌手，都有

那么这个加密方式是满足 cpa 不可区分的。

关于如何构造 CPA 安全的加密算法，详见 ![[PRG and PRF#加密流程]]

CCA 安全

CCA安全其实和CPA安全比较像，只是此时攻击者拥有的神谕机访问权限不同

CCA安全实验

  1. 首先运行密钥生成器 Gen 生成一个密钥 key
  2. 攻击者有向加密器 加密长度为 神谕机访问权限 和 解密神谕机的访问权限 ，并且可以根据访问得到的明文-密文对决定输出一对消息 ，长度也是 的
  3. 加密算法随机生成一个bit，即随机采样 然后输出密文 给到
  4. 攻击者 还有访问加密神谕机和解密神谕机的机会，但是不能查询自己前面输出的两个明文和收到的密文，并最终给出一个
  5. 如果 就认为攻击者 赢得这次实验，整体输出1，否则输出0

CCA安全定义

如果上面的实验满足对于任意的PPT时间内的敌手，都有

那么这个加密方式是满足 cca 不可区分的。

CCA安全只是比CPA安全多了一个解密神谕机的访问权限，但是就是因为多出来的这一点，让之前的基于 PRF 的加密方式不可靠了，因为攻击者可以通过解密另一串明文-密文对，得到 PRF 的相关信息，从而推断出原来的明文是什么

可拓展性（malleability）与CCA安全

可拓展性 (malleability) 是指一个加密算法可以基于一个从 m 加密而来的密文重新加密出一个新的密文，并且新的密文和最原始的明文之前存在一个函数映射 ，其中的 是一个可以被知晓的函数

例如：
在给出密文对 的时候，攻击者可以构造出一个新的密文对 这样在解密之后得到的就是 由于攻击者是知道 的，所以可以解密出 是什么

所以如果一个算法要求满足 cca 不可区分，就意味着，这个算法在加密的时候是不具有可拓展性的。

这玩意看起来很绕，实际上就是你无法通过两次加密绕过随机性