GMR notation

from A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
SIAM Journal on Computing, 1988,by S. Goldwasser, S. Micali, R. Rivest .

在允许的攻击模型下，攻击者成功的概率有多大？

现代密码学中将安全性通过形式化的安全实验来定义，GMR就是用于描述的一套标准化记号体系。

建模

在GMR体系中，所有实体都会被形式化被建模为概率多项式时间算法（PPT）:

对象

1.系统算法：

  • KeyGen（密钥生成）,如：
    $$
    (pk,sk)\gets KeyGen(1^\lambda),1^\lambda为公共参数
    $$

  • Sign（签名）
    $$
    \sigma \gets Sign(sk,m)，m即消息明文
    $$

  • Verify（验证，作为确定性布尔函数，返回1代表通过，返回0代表失败）
    $$
    b:=Verify(pk,m,\sigma)
    $$

  • Setup(初始化)等；

2.攻击者算法A;

​ 作为可执行程序，可接受公钥或系统参数，在实验定义下有的也可调用oracle，最终输出一个攻击结果。

3.辅助过程，如Oracle,Challenger等。

算法（PPT）

Probabilistic：允许在算法内加入随机数

Polynomial-Time：多项式时间内，计算资源现实可行

赋值

（一）随机赋值，如
$$
x \gets \mathcal{D}
$$
用于随机选一个群元素/指数/运行KeyGen

（二）确定性赋值（不引入随机性），如
$$
y:=f(x)
$$
用于在安全性证明中精确追踪随机性来源，对于给定的输入，总能得到相同的输出（比如Hash）

安全实验

$$
常写作：Exp_{\amalg}^{\mathcal{A}}(\lambda)
$$

(以下均为示例)

  • 系统初始化
    $$
    (pk,sk)\gets KeyGen(1^\lambda)
    $$

  • 攻击者交互
    $$
    \mathcal{A}^{Sign(sk,·)}(pk)
    $$
    攻击者可获取公钥，并可多次请求签名但不能获取目标攻击消息

  • 攻击者输出
    $$
    (m^*,\sigma^*)
    $$
    输出一个新的消息-签名对，用于检测是否能通过验证

  • 成功条件判断
    $$
    if Verify(pk,m^*,\sigma^*) = 1\space and\space m^*未被查询过
    $$
    成功：输出1；失败：输出0.

定义安全？

对任意PPT攻击者，其在安全实验中成功的概率是可忽略的。

形式化写做：
$$
\forall \mathcal{A}\in PPT,\Pr [Exp_{\amalg}^{\mathcal{A}}(\lambda)=1]\le \mu(\lambda)，其中\mu(\lambda)为可忽略函数
$$

意义

GMR notation 是现代密码学中定义安全性的基础形式语言，被广泛用于描述数字签名、公钥加密和消息认证码等原语的安全模型。其以安全实验和攻击成功概率为核心，使不同安全目标能够在统一框架下进行刻画，并可通过修改实验规则自然扩展为更强的攻击模型（如从 CPA 到 CCA，或从 EUF-CMA 到强不可伪造）。这一结构同时为 reduction-based 安全证明和 game-hopping 技巧提供了标准接口，并能够支撑复杂、多阶段密码系统的安全分析，因此成为当代密码学研究与教学中的事实标准。【说白了就是规定了一套密码符号的定义】