摘要：
在这篇文章中，我们解决提供安全证明的签名方案中所谓的随机预言模型[1]的问题。

特别的是，它可以对抗适应性选择明文攻击。

我们的主要应用实现了一种变体的Gamal 签名算法（摘要与明文在一起）。

这是一个相当吃惊的结果，因为原来的Gamal 如RSA ，存在伪造性。

1 介绍
自从公钥密码的出现，许多的研究想要提供“可证明的”安全加密协议。

在可计算安全证明中，证明在复杂性理论中有渐近的框架。

然而，这些都不是绝对的证明，因为加密最终依赖单向函数和P 与NP 问题。

2.架构
2.1一般的签名方案
在一个签名方案中，一个用户会公开他的公钥，保存他的私钥。

使用者对消息m 的签名值依赖于消息m 和用户的公钥和私钥，通过这种方式任何人都可以使用公钥检查其有效性。

然而，不知道他的密钥就很难伪造用户的签名。

在这个部分，我们将会给出一个更加精确的一个数字签名的定义以及可能对抗的攻击。

这些定义以文献6为基础。

定义 1.一个数字签名方案如下定义：
——密钥生成算法G ，对于输入k 1，k 是安全参数，产生了一对公钥和私钥
()S P K K ,。

生成算法G 必须为概率算法。

——签名算法∑，给定消息m 以及一对公钥和私钥()S P K K ,，生成一个签名。

这个签
名算法必须是概率算法，在一些方案中它可能收到其它的输入。

——验证算法V ，给定一个签名
σ，消息m 以及公钥p K ，检验σ是否是m 的对应于公钥p K 的合法签名。

通常情况，这个验证算法不需要是概率算法，是确定性算法。

签名方案经常用到一个哈希函数f 。

在这篇文章中，我们将只考虑，输入消息m ，输出三个()21,,σσh ，独立于以前的签名。

在这三个输出中，h 是()1,σm 的哈希值，2σ依赖于1σ，消息m 和h 。

这个覆盖了
在某些方
案中，1σ和h 可以被省略，但是，我们将会保持他们更多的一般性。

2.2攻击
我们只考虑两种不同的情节，包括了概率的多项式时间的图灵机，无消息攻击以及适应性选择明文攻击。

引理2（forking 引理）。

使A是一个概率的多项式时间的图灵机，只输入公共数据。

如果A能找到，有不可忽视的概率，
我们假定有一个无消息攻击者A，是一个概率多项式时间的图灵机有随机消息w。

在攻击期间，它向随机预示f询问一系列的多项式的问题。

我们假定这些问题是可以区分的，比如，A能储存问题并且在一张表上回答。

Q1……Q q是Q的不同问题，Q是一个多项式，。