第二十九個知識點：什麼是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安全的。