密码学系列2-安全模型(CPA,CCA,selective,adaptive)

本章介绍了安全模型中的CPA,selective/adaptive CCA, EUF-CMA

加密的安全性模型定义：

一、选择明文攻击下的不可区分性（IND-CPA）

初始化：挑战者$\mathcal{C}$运行初始化算法算法来获取系统参数。

阶段1：敌手$\mathcal{A}$产生明文，加密的到对应的密文（多项式有界次数）。

挑战：对手将输出两条相同长度的消息$m_0$和$m_1$。

挑战者$\mathcal{C}$随机选择比特 b ∈ { 0 , 1 } b\in \{0,1\} b∈{0,1}，并加密消息$m_b$以获得挑战密文。然后，$\mathcal{C}$将挑战密文发送给对手。

猜测：最后，$\mathcal{A}$输出一个猜测 b ′ ∈ { 0 , 1 } b'\in \{0,1\} b′∈{0,1}。

如果$b=b^{\prime }$，$\mathcal{A}$赢得游戏，优势定义为：

$Ad{v}_{\mathcal{A}}=|Pr(b^{\prime }=b)-1/2|$

思考：阶段一敌手需要和挑战者交互吗？

概率和优势的区别：比如有一个丢一枚硬币的赌局。我们猜测正面朝上，那么我们猜测正确的概率为$1/2$。如果我们知道硬币密度，丢硬币的方式会对结果有影响。那么丢一次硬币后，经过我们精密的分析，我们猜对的概率可能就是$1/2+r$，那么此时就说我们有$r$的优势来正确猜硬币。
如果这个优势不可忽略，比如等于$r=1/2$，那么我们猜对的概率就是1！！如果这个概率无敌小到可以忽略，比如$r=1/2^{1亿}$，那么我们知道硬币密度，丢硬币的方式会对结果几乎没有影响。那么我们的能力对猜硬币的赌局没有任何作用。

二、适应性选择密文攻击下的不可区分性（adaptive IND-CCA2）

初始化：挑战者$\mathcal{C}$运行初始化算法算法来获取系统参数。

阶段1：

1.加密问询：敌手$\mathcal{A}$产生明文，加密的到对应的密文（多项式有界次数）。
2.解密问询：敌手$\mathcal{A}$产生密文，挑战者解密后，将解密得到的明文返给敌手（多项式有界次数）。

挑战：对手将输出两条相同长度的消息$m_0$和$m_1$。

挑战者$\mathcal{C}$随机选择比特 b ∈ { 0 , 1 } b\in \{0,1\} b∈{0,1}，并加密消息$m_b$以获得挑战密文。然后，$\mathcal{C}$将挑战密文发送给对手。

阶段2：

1.加密问询：敌手$\mathcal{A}$产生明文，加密的到对应的密文（多项式有界次数）。
2.解密问询：敌手$\mathcal{A}$产生密文，挑战者解密后，将解密得到的明文返给敌手（多项式有界次数，且敌手不能对挑战密文进行解密问询）。

猜测：最后，$\mathcal{A}$输出一个猜测 b ′ ∈ { 0 , 1 } b'\in \{0,1\} b′∈{0,1}。

如果$b=b^{\prime }$，$\mathcal{A}$赢得游戏，优势定义为：

$Ad{v}_{\mathcal{A}}=|Pr(b^{\prime }=b)-1/2|$

三、选择性选择密文攻击下的不可区分性（selective IND-CCA2）

对手将输出两条相同长度的消息$m_0$和$m_1$并发送给挑战者。

初始化：挑战者$\mathcal{C}$运行初始化算法算法来获取系统参数。

阶段1：

1.加密问询：敌手$\mathcal{A}$产生明文，加密的到对应的密文（多项式有界次数）。
2.解密问询：敌手$\mathcal{A}$产生密文，挑战者解密后，将解密得到的明文返给敌手（多项式有界次数）。

挑战者$\mathcal{C}$随机选择比特 b ∈ { 0 , 1 } b\in \{0,1\} b∈{0,1}，并加密消息$m_b$以获得挑战密文。然后，$\mathcal{C}$将挑战密文发送给对手。

阶段2：

1.加密问询：敌手$\mathcal{A}$产生明文，加密的到对应的密文（多项式有界次数）。
2.解密问询：敌手$\mathcal{A}$产生密文，挑战者解密后，将解密得到的明文返给敌手（多项式有界次数，且敌手不能对挑战密文进行解密问询）。

猜测：最后，$\mathcal{A}$输出一个猜测 b ′ ∈ { 0 , 1 } b'\in \{0,1\} b′∈{0,1}。

如果$b=b^{\prime }$，$\mathcal{A}$赢得游戏，优势定义为：

$Ad{v}_{\mathcal{A}}=|Pr(b^{\prime }=b)-1/2|$

selective是在系统生成前产生挑战密文，再系统初始化时，挑战者可能会根据挑战密文生成相应的系统参数。
思考：selective和adaptive哪个安全性更强

四、（非自适应）选择密文攻击下的不可区分性（IND-CCA1）

初始化：挑战者$\mathcal{C}$运行初始化算法算法来获取系统参数。

阶段1：
1.加密问询：敌手$\mathcal{A}$产生明文，加密的到对应的密文（多项式有界次数）。
2.解密问询：敌手$\mathcal{A}$产生密文，挑战者解密后，将解密得到的明文返给敌手（多项式有界次数）。

挑战：对手将输出两条相同长度的消息$m_0$和$m_1$。

挑战者$\mathcal{C}$随机选择比特 b ∈ { 0 , 1 } b\in \{0,1\} b∈{0,1}，并加密消息$m_b$以获得挑战密文。然后，$\mathcal{C}$将挑战密文发送给对手。

猜测：最后，$\mathcal{A}$输出一个猜测 b ′ ∈ { 0 , 1 } b'\in \{0,1\} b′∈{0,1}。

如果$b=b^{\prime }$，$\mathcal{A}$赢得游戏，优势定义为：

$Ad{v}_{\mathcal{A}}=|Pr(b^{\prime }=b)-1/2|$

现在论文中定义的IND-CCA即指IND-CCA2，CCA1很少见了。
CCA1即在敌手获得挑战密文前可以进行解密问询。敌手获得挑战密文后，便不能再根据挑战密文生成其他密文来进行解密问询了。

签名安全性模型：

五、适应性选择消息的存在不可伪造性（EUF-CMA）

初始化：挑战者$\mathcal{C}$运行初始化算法算法来获取系统参数。

阶段1：
1.签名问询：敌手$\mathcal{F}$产生消息，敌手为消息产生签名并返回给敌手（多项式有界次数）。

伪造：敌手$\mathcal{F}$伪造出一个签名。

如果伪造的签名满足以下条件，则敌手赢得这个游戏：
1.这个签名不是签名问询产生的。
2.签名能通过验证算法。

上面的五个模型都是最基础的定义，不同的方案会由不同的变化。后续文章将给出实例化安全性证明。