Digital Signature

私钥签名，公钥验证。

数字签名应满足的要求

1. id of the signer, 能让发送方知道是签名方而不是其他人的签名
2. (Non-repudiation) 签名方不能否认他们的签名，i.e., the signer cannot repudiate.
3. 其他人无法伪造签名

给一串消息 m，签名方用私钥 sk 签名，设签名算法为 Sig 函数：

$$\sigma = Sig_{sk}(m)
$$

任何拥有公钥的接收方都可以使用公钥算法进行验证，验证结果应为永真：
$$Verify_{pk}(m,\sigma) = 1
$$

而对于攻击者，既无法进行选择性伪造，即在得到m的情况下，无法计算出一个签名 $\sigma’$，使得 $Verify_{pk}(m, \sigma’)=1$；也无法进行存在性伪造，即计算出一对 m’ 和 $\sigma’$，使得 $Verify_{pk}(m,\sigma’)=1$.