第二十九个知识点：什么是UF-CMA数字签名的定义？

第16篇博客给出了DSA，Schnoor和RSA-FDH签名方案的细节，但是签名方案是什么？它应该保证什么样的安全性？

一个签名方案\(S\)是一个算法元组\((KG,Sign,VRFY)\)，满足下面的条件：

• \(KG\)是一个输出密钥\(sk\)和公钥\(pk\)的随机性算法。
• \(Sign\)是要给随机算法，作用于输入\(sk\)和消息\(m\)，然后输出一个签名\(\sigma\)。
• \(VRFY\)是一个确定性的算法，输入是公钥\(pk\)，消息\(m\)，和签名\(\sigma\)。如果\(\sigma\) 是正确的签名输出1，否则输出0。

签名方案用于证明消息的完整性。如果一个消息上有一个被Alice的私钥签名的签名，那么这个消息一定来自于Alice。使用签名而不是使用使用MAC的原因就是签名能被任何人确定，而不需要共享密钥。

如果签名能证明消息的原始性，需要没有密钥的人不能创建一个从未被签名的合法的消息的签名。这叫做UF-CMA安全：

博弈是这样工作的:

• 预先运行\(KG\)得到\((pk,sk)\)。
• 攻击者\(A\)被给\(pk\)。然后攻击者发送消息\(m_i\),能得到对应的签名\(\sigma_i\)。
• \(A\)输出一个元组\((m^*,\sigma^*)\)。

如果\(\sigma^*\)是一个在\(m^*\)上合法的签名，同时\(m^*\)不同于之前的任何一个\(m_i\)，那么就说\(A\)获胜了。在博弈中，对手的优势定义成\(A\)获胜的概率。如果这个优势是非常小的，那么我们就说签名方案 \(S\)是UF-CMA安全的。