数字签名是消息身份验证码的公钥对应物，其语法和安全保证类似。发送方应用于消息的算法在这里表示为Sign（而不是Mac），该算法的输出现在称为签名（而不是标记）。接收方应用于消息和签名以验证有效性的算法仍然表示为Vrfy。

定义 12.1

（数字）签名方案由三种概率多项式时间算法（Gen、Sign、Vrfy）组成，其中：

1. 密钥生成算法Gen将安全参数作为输入，并输出一对密钥（pk，sk）。它们分别称为公钥和私钥。我们假设pk和sk的长度至少为n，并且n可以由pk或sk确定。

2. 签名算法Sign从某些消息空间（可能取决于pk）获取私钥sk和消息m作为输入。它输出一个签名σ，我们把它写成。

3. 确定性验证算法Vrfy将公钥pk、消息m和签名σ作为输入。它输出位b，b=1表示有效，b=0表示无效。我们把它写成 。

要求除输出的（pk，sk）概率可以忽略外，对于每个（合法）消息m，它保持。

如果有一个函数l使得输出的每个（pk，sk）的消息空间是，那么我们说（Gen，Sign，Vrfy）是长度为l（n）的消息的签名方案。

如果，我们称σ为消息m上的有效签名（关于从上下文中理解的某些公钥pk）。

签名方案的使用方式如下。作为发送方的一方S运行以获取密钥（pk、sk）。然后，公开密钥pk属于S；例如，S可以将公钥放在其网页上或放在某个公共目录中。与公钥加密一样，我们假设任何其他方都能够获得S公钥的合法副本（见下文讨论）。当S想要验证消息m时，它计算签名并发送（m，σ）。在收到（m，σ）后，知道pk的接收者可以通过检查来验证m的真实性。这既确定了S发送了m，也确定了m在传输过程中未被修改。但是，与消息身份验证代码的情况一样，它没有说明m是何时发送的，重播攻击仍然是可能的（参见第4.2节）。

各方能够获得S公钥的合法副本的假设意味着S能够以可靠和经过认证的方式传输至少一条消息（即pk本身）。然而，如果我们能够可靠地传输消息，那么为什么我们需要一个签名方案呢？答案是pk的可靠分发是一项困难且昂贵的任务，但使用签名方案意味着只需执行一次，之后就可以可靠地发送无限数量的消息。此外，正如我们将在第12.7节中讨论的，签名方案本身用于确保其他公钥的可靠分发。因此，它们是建立“公钥基础设施”以解决密钥分发问题的中心工具。

签名方案的安全性 Security of signature schemes

对于签名者S生成的固定公钥pk，伪造是消息m和有效签名σ，其中m以前没有被S签名。签名方案的安全性意味着对手即使在其选择的许多其他消息上获得签名，也不能输出伪造。这与消息身份验证代码的安全性定义直接类似，我们请读者参考第4.2节，了解动机和进一步讨论。

我们现在给出了安全性的正式定义，它与定义4.2基本相同。让Vrfy =（Gen，Stand，Vrfy）是一个签名方案，并考虑下面的实验，对手A和参数n：

签名实验 The signature experiment

签名实验 ：

1. 运行以获取密钥（pk、sk）。

2. 对手A被授予pk和访问oracle 的权限。然后对手输出（m，σ）。让Q表示A询问其oracle的所有查询的集合。

3. 当且仅当（1）和（2）。在这种情况下，实验的输出定义为1。

定义 12.2

签名方案∏=（Gen，Sign，Vrfy）在自适应选择消息攻击下是存在不可伪造的，或者只是安全的，如果对于所有概率多项式时间对手A，存在一个可忽略的函数negl，从而：