数字签名的定义

数字签名概述（Overview of Digital Signature） 🔗

Bob向Alice发送消息时，Alice需要确认消息是否来自Bob。

\rightarrow

使用

数字签名

。

没有Bob的私钥，其他人就无法生成Bob的签名。

这从来源（Bob）和数据完整性（消息）两个方面提供认证。

数字签名方案由以下三个多项式时间算法组成。

KeyGen
( $\lambda$ $λ$ ) $\rightarrow$ $\to$ (pk, sk)：密钥生成算法。
- 输入安全参数 $\lambda$ ，生成公钥pk与私钥sk。
Sign
(sk, m) $\rightarrow$ $\to$ $\sigma$ $σ$ ：签名算法。
- 输入私钥sk与消息m，生成数字签名 $\sigma$ 。
Verify
(pk, m, $\sigma$ $σ$ ) $\rightarrow$ $\to$ {0, 1}：验证算法。
- 输入公钥pk、消息m和数字签名 $\sigma$ ，验证签名是否有效。
- 有效则返回1，否则返回0。

正确性

：验证算法应满足以下条件。

考虑挑战者

C

与攻击者

A

之间的游戏。

Setup： $C$ 执行KeyGen( $\lambda$ )，生成 $(pk, sk)$ ，并将公钥 $pk$ 交给 $A$ 。
Signing Queries： $A$ $A$ 针对消息 $M_i$ $M_{i}$ 提出多项式次数的签名查询。
- 对每个 $M_i$ ， $C$ 执行 $\text{Sign}(sk, M_i) → \sigma_i$ ，生成签名 $\sigma_i$ 并返回给 $A$ 。
Output： $A$ $A$ 返回 $(M, \sigma)$ $(M, σ)$ 。
- $M$ 是 $C$ 没有签名过的消息，与 $A$ 曾请求签名的消息不同。
- 如果 $A$ 为 $M$ 生成了有效签名 $\sigma$ ，则视为 $A$ 成功。

A

的成功概率定义如下。

签名方案对于自适应选择消息攻击（Adaptive Chosen Message Attack）应当具有强不可伪造性。

如果任意多项式时间攻击者

A

在上述游戏中成功的概率都可以忽略，则这个签名方案具有强

不可伪造性

。