密码学中数字签名方案的安全模型主要包括两种: 存在性不可伪造(Existential Unforgeability against chosen-message attacks, EU-CMA)和强不可伪造(Strong Unforgeability against chosen-message attacks, SU-CMA), 本文主要对比这两种安全模型.
两种安全模型都是通过敌手(Adversary)和挑战者(Challenger)之间的游戏(Game)来定义的. 首先挑战者生成密钥对 ( p k , s k ) (pk,sk) (pk,sk) 并发送 p k pk pk 给敌手, 自己保存 s k sk sk 用来生成签名. 敌手可以自适应地提交任意消息, 挑战者根据敌手提交的消息生成对应的签名并返回给敌手. 最后, 敌手返回一个伪造的对未查询过的新消息的签名.
EU-CMA存在性不可伪造(EU-CMA)安全模型可以用如下Game描述:
Setup. 假设 S P SP SP 为系统参数. 挑战者执行密钥生成算法, 生成密钥对 ( p k , s k ) (pk,sk) (pk,sk) 并发送 p k pk pk 给敌手. 挑战者保留 s k sk sk 用来回答敌手的签名查询.
Query. 敌手自适应地选取任意消息 m i m_i mi 进行签名查询. 对于敌手提交的消息 m i m_i mi, 挑战者执行签名算法生成 σ m i sigma_{m_i} σmi 并将其发送给敌手.
Forgery. 敌手返回一个伪造的对于某个消息 m ∗ m^* m∗ 签名 σ m ∗ sigma_{m^*} σm∗, 如果:
则敌手在游戏中获胜. 敌手赢得游戏的优势 ε varepsilon ε 就是返回一个合法的伪造签名的概率.
SU-CMA强不可伪造(SU-CMA)安全模型可以用如下Game描述:
Setup. 假设 S P SP SP 为系统参数. 挑战者执行密钥生成算法, 生成密钥对 ( p k , s k ) (pk,sk) (pk,sk) 并发送 p k pk pk 给敌手. 挑战者保留 s k sk sk 用来回答敌手的签名查询.
Query. 敌手自适应地选取任意消息 m i m_i mi 进行签名查询. 对于敌手提交的消息 m i m_i mi, 挑战者执行签名算法生成 σ m i sigma_{m_i} σmi 并将其发送给敌手.
Forgery. 敌手返回一个伪造的对于某个消息 m ∗ m^* m∗ 签名 σ m ∗ sigma_{m^*} σm∗, 如果:
则敌手在游戏中获胜. 敌手赢得游戏的优势 ε varepsilon ε 就是返回一个合法的伪造签名的概率.
对比EU-CMA 和 SU-CMA 的两个游戏的区别仅在于敌手获胜条件的判定上(Forgery-2)
在EU-CMA中的要求是所有关于 m ∗ m^* m∗ 的签名在Query阶段都没有被查询过而在 SU-CMA 中则只要求在之前的查询操作中没有出现过 σ m ∗ sigma_{m^*} σm∗, 也就是说, 如果之前查询过关于 m ∗ m^* m∗ 的签名 σ m ∗ ( 1 ) sigma_{m^*}^{(1)} σm∗(1), 如果敌手可以生成另一个关于 m ∗ m^* m∗ 的签名 σ m ∗ ( 2 ) sigma_{m^*}^{(2)} σm∗(2), 并且 σ m ∗ ( 1 ) sigma_{m^*}^{(1)} σm∗(1) 与 σ m ∗ ( 2 ) sigma_{m^*}^{(2)} σm∗(2) 不同, 也判定为敌手获胜.显然 SU-CMA 中的敌手拥有更强的能力, 因此可以认为 SU-CMA 相比 EU-CMA 是更强的安全模型.