像EUF-CMA这样的签名安全性缩写是什么意思？

#1 楼

（表示法。集合用书法字体表示，算法用直字体表示。在整个过程中，$ \ Sigma：=（\ mathsf {K}，\ mathsf {S}，\ mathsf {V}）$表示a上的签名方案。密钥空间$ \ mathcal {K} $，消息空间$ \ mathcal {M} $和签名空间$ \ mathcal {S} $。
由于讨论只涉及一个密钥对，为避免混乱，我们在调用$ \ mathsf {S} $时删除安全参数，公共密钥和私钥；类似地，在调用$ \ mathsf {V} $时删除安全参数和公共密钥。 ：
$ \ mathsf {S}：\ mathcal {M} \ rightarrow \ mathcal {S} $和
$ \ mathsf {V}：\ mathcal {S} \ times \ mathcal {M} \ rightarrow \ {0,1 \} $。）

和加密方案一样，使用挑战者和对手$ \ mathsf之间的游戏为签名方案$ \ Sigma $建模安全性{A} $（多项式时间概率机器）。游戏模拟了一个可能的情况，即当挑战者使用方案$ \ Sigma $时，$ \ mathsf {A} $试图通过攻击来破坏$ \ Sigma $。如果$ \ mathtt {break} $-$ \ mathtt {attack} $模型（即$ \ mathtt {break} $-$ \ mathtt {attack} $-secure）被认为是安全的，因此，对于$ \ mathtt {attack} $下的$ \ mathttf {A} $到$ \ mathtt {break} $ $ \ Sigma $来说，这是很难的（精确的定义在最后给出）。 $ \ mathtt {break} \ in $ {UF，SF，EF}和$ \ mathtt {attack} \ in $ {KOA，CMA，KMA}签名方案的情况下-可以考虑将它们组合使用。

为了便于说明，让我们从“最弱”模型的描述开始，该模型称为“仅密钥攻击（KOA）下的通用伪造（UF）”。


1：UF-KOA $ ^ {\ mathsf {A}} _ \ Sigma（1 ^ n）$



示例键$（sk，pk）\ leftarrow \ mathsf {K}（1 ^ n）$并运行对手$ \ mathsf {A}（1 ^ n，pk）$

a。在任意消息$ m ^ * \ in \ mathcal {M} $

b。收到伪造品$（m ^ *，\ sigma ^ *）$作为对挑战的回应：$ \ mathsf {A} $如果$ \ mathsf {V}（\ sigma ^ *，m ^ *）= 1则获胜$


也就是说，在UF-KOA模型中，对手仅根据公钥（即密码）就伪造了挑战者选择的消息（即通用伪造）。仅密钥攻击）。在此模型中，对手要完成的任务最困难：仅给伪造者提供伪造所需的最低限度（即，公钥），而对伪造的消息则没有选择。

在实践中，对手可能有能力获得更多的信息，例如，它可以通过某种渠道获得签名人发布的签名。 UF-KOA模型没有捕捉到这一点，因此认为它很弱的原因。有两种方法可以增强它：一种，我们可以使对手的任务变得更容易（例如，让它根据自己选择的信息来伪造）；和/或两个，我们可以为其提供更多信息（例如，在其选择的消息上为其签名）。现在，让我们看一个称为UF的已知消息攻击（KMA）模型，后者可以做到。


2：UF-KMA $ ^ {\ mathsf {A} } _ \ Sigma（1 ^ n）$




a。示例键$（sk，pk）\ leftarrow \ mathsf {K}（1 ^ n）$，然后运行对手$ \ mathsf {A}（1 ^ n，pk）$

b。样本$ q = q（n）$任意消息$ m_1，...，m_q \ in \ mathcal {M} $，并生成签名$ \ sigma_i \ leftarrow \ mathsf {S}（m_i）$，$ 1 \ le i \ le q $


a。将集合$ \ {（m_1，\ sigma_1），...，（m_q，\ sigma_q）\} $发送到$ \ mathsf {A}（1 ^ n）$，然后在任意消息$ m ^上质询* \ not \在\ {m_1，...，m_q \} $

b中。从$ \ mathsf {A} $收到伪造$（m ^ *，\ sigma ^ *）$作为响应：$ \ mathsf {A} $如果$ \ mathsf {V}（\ sigma ^ *，m ^ * ）= 1 $


尽管$ \ mathsf {A} $必须仍然产生普遍的伪造，但它现在得到了-与UF-KOA模型不同的是-在它知道的消息上有很多签名（已知消息攻击）。通过允许$ \ mathsf {A} $查询和获取其选择的消息的签名，可以进一步增强该模型。这将产生以下给出的模型，该模型在选择消息攻击（CMA）下称为UF。


3：UF-CMA $ ^ {\ mathsf {A}} _ \ Sigma（1 ^ n）$




a。示例键$（sk，pk）\ leftarrow \ mathsf {K}（1 ^ n）$，然后运行对手$ \ mathsf {A}（1 ^ n，pk）$

b。初始化集合$ \ mathcal {M}'= \ emptyset $。

如果$ \ mathsf {A} $查询消息$ m \ in \ mathcal {M} $的签名，则返回$ \ mathsf {S}（m）$，然后将$ m $添加到$ \ mathcal {M}'$

a。在任意消息$ m ^ * \ not \ in \ mathcal {M}'$

b中挑战$ \ mathsf {A} $。收到$ \ mathsf {A} $的伪造$（m ^ *，\ sigma ^ *）$作为响应：$ \ mathsf {A} $如果$ \ mathsf {V}（\ sigma ^ *，m ^ * ）= 1 $


接下来，让我们从第二个方面着眼于增强模型，即通过削弱对手破坏签名方案意味着什么的概念。从在第一个实验中讨论过的普遍伪造，到有选择性伪造（SF），最后到KOA设置中的存在伪造（EF）。


4：SF- KOA $ ^ {\ mathsf {A}} _ \ Sigma（1 ^ n）$



从$ \ mathcal {A} $收到承诺$ m ^ * \ in \ mathcal {M} $：$ \ mathsf {A} $必须最终在$ m ^ * $上伪造
样本键$（sk，pk）\ leftarrow \ mathsf {K}（1 ^ n）$并运行对手$ \ mathsf {A}（1 ^ n，pk）$
从$ \ mathsf {A} $接收作为伪造品$（m ^ *，\ sigma ^ *）$ ：如果$ \ mathsf {V}（\ sigma ^ *，m ^ *）= 1 $

，则$ \ mathsf {A} $获胜，请注意，尽管$ \ mathcal {A} $必须



5：EF EF-KOA的先验承诺致力于传播它所传递的信息，它仍然比UF-KOA游戏具有更大的自由度。 -KOA $ ^ {\ mathsf {A}} _ \ Sigma（1 ^ n）$



示例键$（sk，pk）\ leftarrow \ mathsf {K}（1 ^ n）$并运行对手$ \ mathsf {A}（1 ^ n，pk）$
作为$ \ mathsf的响应接收{A} $伪造$（m ^ *，\ sigma ^ *）$：$ \ mathsf {A} $如果$ \ mathsf {V}（\ sigma ^ *，m ^ *）= 1 $

类似地，可以为$ \ mathtt {break} \ in $ {SF，EF}和$ \定义模型$ \ mathtt {break} $-$ \ mathtt {attack} $ mathtt {attack} \ in $ {KMA，CMA}。下面定义了最强大的模型-即EF-CMA-，因为它被认为是签名方案安全性的模型。


6：EF-CMA $ ^ {\ mathsf {A}} _ \ Sigma（1 ^ n）$




a。示例键$（sk，pk）\ leftarrow \ mathsf {K}（1 ^ n）$，然后运行对手$ \ mathsf {A}（1 ^ n，pk）$

b。初始化一组$ \ mathcal {M}'= \ emptyset $。

如果$ \ mathsf {A} $查询消息$ m \ in \ mathcal {M} $的签名，请回答$ \ mathsf {S}（m）$，然后将$ m $添加到$ \ mathcal {M}'$
从$ \ mathsf {A} $的输出中接收伪造品$（m ^ *，\ sigma ^ *）$：如果$ \ mathsf {V}（\ sigma ^ *，m ^ *）= 1 $和$ m ^ * \ not \ in \ mathcal {M}'$

也就是说，在EF-CMA模型中，对手可以在它自适应选择的消息上获得一堆签名，最后可以伪造任何新消息。也认为此定义的更强版本-称为强EF-CMA（sEF-CMA）-。


7：sEF-CMA $ ^ {\ mathsf {A}} _ \ Sigma（1 ^ n）$




a。示例键$（sk，pk）\ leftarrow \ mathsf {K}（1 ^ n）$，然后运行对手$ \ mathsf {A}（1 ^ n，pk）$

b。初始化一组$ \ mathcal {M}'= \ emptyset $。

如果$ \ mathsf {A} $查询消息$ m \ in \ mathcal {M} $的签名，请回答$ \ sigma = \ mathsf {S}（m）$，然后将$（m，\ sigma）$添加到$ \ mathcal {M}'$
从$ \ mathsf {A} $接收作为伪造品$（m ^ *，\ sigma ^ *）$：如果$ \ mathsf {V}（\ sigma ^ *，m ^ *）= 1 $和$（m ^ *，\ sigma，则$ \ mathsf {A} $获胜^ *）\ not \ in \ mathcal {M}'$

就是说，只要伪造品与响应查询所收到的伪造品不同（即强烈的存在性伪造品），对手就可以伪造在其上查询签名的消息。 > PS


定义。如果对所有概率多项式时间的对手$ \ mathsf {A} $
$$ \ Pr [\ mathsf，则签名方案被称为$ \ mathtt {break} $-$ \ mathtt {attack} $-secure {A} \ wins \ \ mathtt {break}-\ mathtt {attack} _ \ Sigma ^ {\ mathsf {A}}（1 ^ n）] = negl（n）。$$
其中$ \ mathtt {break} \ in $ {UF，SF，EF}和$ \ mathtt {attack} \ in $ {KOA，CMA，KMA}。

尽管只讨论了签名方案，但定义可以易于适应消息验证码（MAC）。特别是：


由于密钥生成算法仅生成对称密钥$ k $，因此在安全模型的步骤1中，没有密钥要移交给$ \ mathsf {A } $。结果，从信息论的角度来说，UF-KOA是困难的。 />攻击和破坏还有其他变体-例如，请参见[GMR]。

参考文献：
[GMR]：Goldwasser，Micali和Rivest。一种数字签名方案可防止自适应选择消息攻击。 （PDF）