FDH签名方案可证明安全分析

RSA密码系统如下：

FDH签名方案如下：

可证明安全分析大致如下：
角色：仿真器I，攻击者F。
仿真器I拥有公钥（n,e）随机选择y，仿真器需要利用攻击者的能力解决RSA求逆问题，即需计算出

仿真器I执行hash询问如下（仿真器将y嵌入到自己的hash询问应答中）：

签名询问如下：

最后攻击者给出签名挑战（即敌手给出消息mi的有效签名即x=h(mi)^d ，这里我们假设敌手已经进行过hash询问即列表中存储的hi=h(mi)）：

我们假设攻击者已经询问过关于mi的hash询问（如果没有，则仿真器进行hash询问，敌手只能对挑战的mi进行hash询问，不能进行签名询问）。即，列表中一定有关于mi的信息（mi,hi,ri）。
如果说mi的hash询问为hi=y ri^e，则x=hi^d=yi^d ri，则yi^d =x / ri.
假设敌手在执行了q^s 次签名询问后终止，成功伪造签名的概率为a，则RSA求逆问题的优势为
Adv=p^qs (1-p) a，即表示在qs次没有失败的签名询问后，敌手以概率a伪造签名，且此时以（1-p）的概率对应的是hi=y ri^e

PS:签名询问过程中之所以要终止的原因是因为仿真器需要保证每一个询问的签名值=hi^d，符合FDH签名约束。
参考文献：Jean-Sébastien Coron. On the Exact Security of Full Domain Hash[C]// Advances in Cryptology - CRYPTO 2000, 20th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2000, Proceedings. 2000.