论文部分内容阅读
摘 要：本文首先回顾了可证明安全性的发展过程，并在RO模型和标准模型下介绍了几个有代表性的可证明安全的数字签名方案，最后指出了有待进一步研究的问题。
关键词：可证明安全性；归约；归约松紧度；数字签名方案；RO模型；标准模型
中图分类号：TP309.2文献标识码：A
Remark on Provable Security of Digital Signature Schemes
ZHENG Hui
（School of Science， Central University for Nationalities，Beijing 100081）
Key words: provable security； reduction；degree of reduction；digital signature scheme；RO model；standard model
可证明安全性是近几年来较为热门的话题，它简单来说是指可以从数学上证明密码系统能抵抗一些类型的攻击。最早对安全性理论做出贡献的应属C.E.Shannon,他在1949年提出完善保密性（perfectly secret）的概念,之所以称之完善，是因为攻击者不会得到任何密文相对应的明文，也就是它可以抵抗所有的唯密文攻击。Shannon向我们展现的完善保密性的加密方式是，信息的每个比特位都是用密钥中的一个比特加密的，敌手即使有无限的计算能力和时间资源，也得不到任何明文消息，我们可以将之称为无条件安全。然而这也导致了密钥的长度必须和信息的长度相同，显然这是相当不实用的。
而目前所研究的可证明安全性都是具有条件的，1982年Goldwasser 和Micali提出了可证明安全性（provable security）的概念，其实现步骤可以描述如下：（1）确定安全协议的安全目标（如签名方案的安全目标是确保签名的不可伪造性）；（2）在安全协议中使用某个极微本原（lower-level primitive）（本原是指密码的算法或数学难题）；（3）如果原在安全协议中发挥作用则称安全协议的目标达到，即安全性获得证明（此证明通常称为归约（reduction））。
如果说“可证明安全性”这一概念将密码学从艺术转化为科学，那么1993年Bellar和Rogaway 提出的面向实际的可证明安全性(practice-oriented provable security)则是在密码学理论和密码学应用之间搭建了一个桥梁，他们形式化规范了1987年Fiat和Shamir提出了RO（random oracle）模型，具体是：（1）假设这样一个公开的RO模型存在；（2）在RO模型中证明将要设计的协议的安全性；（3）用一个适当选择的杂凑函数来代替此Oracle。这个论点的益处是显然的，因为在模型下证明是安全的总比没有任何可信安全性证明要强。
RO模型大大简化了加密体制的分析过程，对于一些因为太复杂而难以进行安全性证明的体制给出了安全性的“证明”。而对于RO模型和随机选取的杂凑函数之间的差别在于，后者其实给攻击者提供了一个对图灵机的描述的途径，这有可能计算出杂凑函数，而前者则不会提供这样的途径。Canetti等在2004年指出可能存在这样的加密体制，它在RO模型中被证明是安全的，但是用任何杂凑函数来代替都是不安全的，他可以用图灵机的知识计算杂凑函数，强迫加密系统释放敏感信息（例如私钥）。此外，还有一些以Cramer和Shoup在1998年提出的数字签名方案为代表的，它们是在标准假设下（如RSA或离散对数假设），而不是依赖RO模型就可证明是安全的。下面本文将在RO模型和标准模型两种情况下分别介绍几个可证明安全的数字签名方案。
1 基本概念
归约：是可证明安全性的重要工具，它可以从以下三个方面去理解：（1）攻破方案的算法F和解决数学难题的算法I，攻击者可以在多项式时间t内以概率ε完成F，可以将此问题归约为在多项式时间t’内以概率ε’完成I。（2）若在时间t’内不能以超过ε’的概率解决I，则在时间t内就不能以超过ε的概率解决F。（3）若△t=t’-t是多项式时间的，我们把△ε叫作归约松紧度，在攻击目标是密文不可区分性时△ε=ε-ε’，否则，△ε=ε-1/2-ε’。
可证明安全性定义的内容[1]：包括安全目标和攻击模型两个重要部分，安全目标一般包括语义安全性(SS)，不可区分性（IND)，不可展性(NM)和明文可意识（PA)和在签名方案中的不可伪造等，而攻击模型包括选择明文攻击(CPA)，非适应性选择消息攻击(CCA1)和适应性选择消息攻击(CCA2)。
2 RO模型中的可证明性安全的几个数字签名方案
归约是设计和分析实际的密码体制的很重要的工具，归约松紧度在证明过程中起着至关重要的作用，归约越松，说明攻破方案的难度与困难问题的难度差距越大，归约越紧，说明攻破方案的难度越接近困难问题的难度。下面就归约松紧度这个角度上给出几个在RO模型中已证明安全的数字签名方案。
（1）1996年Bellar和,Rogaway给出了FDH(Full-Domain-Hash)签名方案的安全性证明，但是该证明的归约很松。
（2）同一篇文献中他们还提出概率签名方案PSS(Probabilistic Signature Scheme)和PSS－R。PSS方案的建立需要一个陷门置换f:D→D，DU{0，1}*一个伪随机序列发生器G和一个杂凑函数h。
PSS方案的安全性是依赖于单向函数的单向性的，证明中假设杂凑函数与伪随机序列发生器像是真正的随机函数，这些函数的随机性假设基于RO模型，PSS方案将存在性不可伪造作为安全目标，而选择消息攻击作为攻击模型，将方案的安全性归约为RSA求逆问题。它的安全性证明相应的归约达到最紧，攻击者伪造签名的能力和对RSA求逆能力相当，被认为是最安全的。PSS-R方案是PSS方案的一个简单修改，目的是为了缩短被签消息的长度。
（3）同年，Pointcheval和Stern提出了以Forklore引理为工具的安全性论断，该引理使用了"问答器重放攻击"，即以相同的随机数和不同的问答器，在多项式时间内重放攻击，将得到关于某一形式的两个有效签名，对攻破签名所基于的难题的时间和效率进行研究，从而对签名的安全程度有了一个量上的比较，这对现实中使用签名有很大的帮助。在该文献中，他们利用Forklore引理给出了对Fiat-shamir签名方案及一个ElGamal变形签名方案的证明，但是归约不够紧。
（4）2003年，E Goh和 S Jarecki i给出了一个基于CDH(Computational Diffie-Hellman)问题的签名方案EDL的归约很紧的证明，它的安全性等价于CDH问题的难度。
（5）同年，Jonathan K和Nan W提出了基于DDH（Decisional Diffie?Hellman Problem）问题的签名方案，并证明它的安全性近似等价于解决DDH问题的难度。
其实由于在RO模型中的安全性证明与安全目标，攻击模型，及归约有效性有很大关系，所以方案的安全性也并不是由其中的个别因素就可以决定，文献[2]认为，攻击模型越难，攻击目标越简单，困难问题越难，归约越紧的方案越安全。
3标准模型下的可证明安全性的数字签名方案
（1）1988年Goldwasser ,Micali和 Rivest提出的签名方案（记作GMR方案）可以说是第一个可证明抵抗适应性选择消息攻击的数字签名方案，它是基于无爪对构造的，而不是依赖于RO模型。下面给出GMR方案中的几个重要概念和定理：
定义1： 令f0:D→D和f2:D→D是同一个定义域D上的置换，如果f0(x)=f1(y)，则称一对(x,y)是f0与f1的一个爪（claw）.
定义2： 称(f0 , f1)为一个无爪单向置换对，如果计算出爪是不可行的，即对于任意的概率多项式算法A，其输入为i，输出为两个不同的元素x,y∈Di，并且对于任意的正多项式P，存在一个k0∈N，使得对于所有的k≥k0，有：
prob(f,i(x)=f,i(y):i←K（1）,{x,y}←A(i))≤
很多数字签名方案，被签名消息总是先用抗碰撞杂凑函数进行杂凑的，GMR方案中，通过对每个消息使用新的随机参考值，克服了都用一个参考值带来的安全隐患，他们设计了基于认证树的签名，通过多个无爪置换对构造节点之间的串接，签名时，签名方对认证树上的叶子进行签名，验证签名时，通过显然的路径从叶子节点向上追溯，最终计算出正确的根而接受签名。
引理1若无爪置换对存在，则抗碰撞的杂凑函数也存在。
定理1[3] GMR签名方案对于适应性选择消息攻击是安全的。
但遗憾的是GMR方案的效率很低，没有太大的实用价值。
（2）1998年Cramer和Shoup提出了在标准数论假设下，而不是依赖于RO模型的数字签名方案（记作CS98方案），该方案具有实用价值，有很重要的意义，所以被广泛应用。CS98方案的安全性基于DDH问题，是IND－CCA2安全的。相对于RO模型中基于DDH问题的IND－CCA2方案，加，解密速度，以及密钥长度都大约是它们的两倍，也就是说RO模型中的方案有效率高的优势，但标准模型中的方案不需假设的杂凑函数是理想的 。
（3）2000年，Shoup等人对CS98方案进行了改进（记作CS00），一方面，当DDH假设成立，该方案在标准模型下依然是IND－CCA2安全的，另一方面，当DDH假设不成立，该方案在RO模型中，在CDH假设下是IND－CCA2安全的，而且效率较CS98高。在强RSA假设下，该方案对适应性选择消息攻击是安全的。
定理2 如果强RSA假设成立，“许多”Sophie Germain素数存在，且H是抗碰撞的，那么CS00方案对适应性选择消息攻击是安全的。
4 进一步研究
虽然许多研究者仍在研究RO模型的弊端，特别是它在复杂情况下的不适当性，但是RO模型的发展前景并不灰暗，它更积极方面的研究已经开始。RO模型与标准模型的不同本质在于确定的难题是否与零知识证明相关联。RO模型的研究不会停止，除非我们所构造出的密码体制可以简单而有效的在标准模型中就可证明是安全的。
抛开RO模型建立简单而有效的可证明安全密码系统最大的障碍在于对那些琐细的谕示询问（oracle queries）的反应。在完全淘汰RO模型的过程中，解决这些琐细的谕示询问将是向前迈出的一大步。研究者们在这一领域相当活跃，特别是和2004年由Bellare和Palacio提出的明文可意识性(plaintext awareness)相联系起来而进行的研究。将回应谕示询问和分析零知识协议这二者联系起来是非常有可能的。
5结束语
本文简单介绍了可证明安全性的发展过程，并介绍了在两种模型下几个比较有代表性的可证明安全的数字签名方案，最后给出可证明安全这一理论的有待进一步研究的问题。
参考文献:
[1]张文政.公钥密码体制可证明安全性的几点注记［J］.信息安全与通信保密,2005，7:125-127.
[2]任艳丽，谷大武.公钥密码方案的可证明安全性注记［J］.计算机应用研究,2008，4：1130－1133.
[3]Hans Delfs,Helmut Knebl著.肖国镇,张宁等译.密码学导引：原理与应用[M].北京：清华大学出版社,2008.
[4]梅其祥,唐小虎,何大可.抗选择密文攻击公钥密码体制的研究［J］计算机应用研究,2006，2:19-21 .
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
关键词：可证明安全性；归约；归约松紧度；数字签名方案；RO模型；标准模型
中图分类号：TP309.2文献标识码：A
Remark on Provable Security of Digital Signature Schemes
ZHENG Hui
（School of Science， Central University for Nationalities，Beijing 100081）
Key words: provable security； reduction；degree of reduction；digital signature scheme；RO model；standard model
可证明安全性是近几年来较为热门的话题，它简单来说是指可以从数学上证明密码系统能抵抗一些类型的攻击。最早对安全性理论做出贡献的应属C.E.Shannon,他在1949年提出完善保密性（perfectly secret）的概念,之所以称之完善，是因为攻击者不会得到任何密文相对应的明文，也就是它可以抵抗所有的唯密文攻击。Shannon向我们展现的完善保密性的加密方式是，信息的每个比特位都是用密钥中的一个比特加密的，敌手即使有无限的计算能力和时间资源，也得不到任何明文消息，我们可以将之称为无条件安全。然而这也导致了密钥的长度必须和信息的长度相同，显然这是相当不实用的。
而目前所研究的可证明安全性都是具有条件的，1982年Goldwasser 和Micali提出了可证明安全性（provable security）的概念，其实现步骤可以描述如下：（1）确定安全协议的安全目标（如签名方案的安全目标是确保签名的不可伪造性）；（2）在安全协议中使用某个极微本原（lower-level primitive）（本原是指密码的算法或数学难题）；（3）如果原在安全协议中发挥作用则称安全协议的目标达到，即安全性获得证明（此证明通常称为归约（reduction））。
如果说“可证明安全性”这一概念将密码学从艺术转化为科学，那么1993年Bellar和Rogaway 提出的面向实际的可证明安全性(practice-oriented provable security)则是在密码学理论和密码学应用之间搭建了一个桥梁，他们形式化规范了1987年Fiat和Shamir提出了RO（random oracle）模型，具体是：（1）假设这样一个公开的RO模型存在；（2）在RO模型中证明将要设计的协议的安全性；（3）用一个适当选择的杂凑函数来代替此Oracle。这个论点的益处是显然的，因为在模型下证明是安全的总比没有任何可信安全性证明要强。
RO模型大大简化了加密体制的分析过程，对于一些因为太复杂而难以进行安全性证明的体制给出了安全性的“证明”。而对于RO模型和随机选取的杂凑函数之间的差别在于，后者其实给攻击者提供了一个对图灵机的描述的途径，这有可能计算出杂凑函数，而前者则不会提供这样的途径。Canetti等在2004年指出可能存在这样的加密体制，它在RO模型中被证明是安全的，但是用任何杂凑函数来代替都是不安全的，他可以用图灵机的知识计算杂凑函数，强迫加密系统释放敏感信息（例如私钥）。此外，还有一些以Cramer和Shoup在1998年提出的数字签名方案为代表的，它们是在标准假设下（如RSA或离散对数假设），而不是依赖RO模型就可证明是安全的。下面本文将在RO模型和标准模型两种情况下分别介绍几个可证明安全的数字签名方案。
1 基本概念
归约：是可证明安全性的重要工具，它可以从以下三个方面去理解：（1）攻破方案的算法F和解决数学难题的算法I，攻击者可以在多项式时间t内以概率ε完成F，可以将此问题归约为在多项式时间t’内以概率ε’完成I。（2）若在时间t’内不能以超过ε’的概率解决I，则在时间t内就不能以超过ε的概率解决F。（3）若△t=t’-t是多项式时间的，我们把△ε叫作归约松紧度，在攻击目标是密文不可区分性时△ε=ε-ε’，否则，△ε=ε-1/2-ε’。
可证明安全性定义的内容[1]：包括安全目标和攻击模型两个重要部分，安全目标一般包括语义安全性(SS)，不可区分性（IND)，不可展性(NM)和明文可意识（PA)和在签名方案中的不可伪造等，而攻击模型包括选择明文攻击(CPA)，非适应性选择消息攻击(CCA1)和适应性选择消息攻击(CCA2)。
2 RO模型中的可证明性安全的几个数字签名方案
归约是设计和分析实际的密码体制的很重要的工具，归约松紧度在证明过程中起着至关重要的作用，归约越松，说明攻破方案的难度与困难问题的难度差距越大，归约越紧，说明攻破方案的难度越接近困难问题的难度。下面就归约松紧度这个角度上给出几个在RO模型中已证明安全的数字签名方案。
（1）1996年Bellar和,Rogaway给出了FDH(Full-Domain-Hash)签名方案的安全性证明，但是该证明的归约很松。
（2）同一篇文献中他们还提出概率签名方案PSS(Probabilistic Signature Scheme)和PSS－R。PSS方案的建立需要一个陷门置换f:D→D，DU{0，1}*一个伪随机序列发生器G和一个杂凑函数h。
PSS方案的安全性是依赖于单向函数的单向性的，证明中假设杂凑函数与伪随机序列发生器像是真正的随机函数，这些函数的随机性假设基于RO模型，PSS方案将存在性不可伪造作为安全目标，而选择消息攻击作为攻击模型，将方案的安全性归约为RSA求逆问题。它的安全性证明相应的归约达到最紧，攻击者伪造签名的能力和对RSA求逆能力相当，被认为是最安全的。PSS-R方案是PSS方案的一个简单修改，目的是为了缩短被签消息的长度。
（3）同年，Pointcheval和Stern提出了以Forklore引理为工具的安全性论断，该引理使用了"问答器重放攻击"，即以相同的随机数和不同的问答器，在多项式时间内重放攻击，将得到关于某一形式的两个有效签名，对攻破签名所基于的难题的时间和效率进行研究，从而对签名的安全程度有了一个量上的比较，这对现实中使用签名有很大的帮助。在该文献中，他们利用Forklore引理给出了对Fiat-shamir签名方案及一个ElGamal变形签名方案的证明，但是归约不够紧。
（4）2003年，E Goh和 S Jarecki i给出了一个基于CDH(Computational Diffie-Hellman)问题的签名方案EDL的归约很紧的证明，它的安全性等价于CDH问题的难度。
（5）同年，Jonathan K和Nan W提出了基于DDH（Decisional Diffie?Hellman Problem）问题的签名方案，并证明它的安全性近似等价于解决DDH问题的难度。
其实由于在RO模型中的安全性证明与安全目标，攻击模型，及归约有效性有很大关系，所以方案的安全性也并不是由其中的个别因素就可以决定，文献[2]认为，攻击模型越难，攻击目标越简单，困难问题越难，归约越紧的方案越安全。
3标准模型下的可证明安全性的数字签名方案
（1）1988年Goldwasser ,Micali和 Rivest提出的签名方案（记作GMR方案）可以说是第一个可证明抵抗适应性选择消息攻击的数字签名方案，它是基于无爪对构造的，而不是依赖于RO模型。下面给出GMR方案中的几个重要概念和定理：
定义1： 令f0:D→D和f2:D→D是同一个定义域D上的置换，如果f0(x)=f1(y)，则称一对(x,y)是f0与f1的一个爪（claw）.
定义2： 称(f0 , f1)为一个无爪单向置换对，如果计算出爪是不可行的，即对于任意的概率多项式算法A，其输入为i，输出为两个不同的元素x,y∈Di，并且对于任意的正多项式P，存在一个k0∈N，使得对于所有的k≥k0，有：
prob(f,i(x)=f,i(y):i←K（1）,{x,y}←A(i))≤
很多数字签名方案，被签名消息总是先用抗碰撞杂凑函数进行杂凑的，GMR方案中，通过对每个消息使用新的随机参考值，克服了都用一个参考值带来的安全隐患，他们设计了基于认证树的签名，通过多个无爪置换对构造节点之间的串接，签名时，签名方对认证树上的叶子进行签名，验证签名时，通过显然的路径从叶子节点向上追溯，最终计算出正确的根而接受签名。
引理1若无爪置换对存在，则抗碰撞的杂凑函数也存在。
定理1[3] GMR签名方案对于适应性选择消息攻击是安全的。
但遗憾的是GMR方案的效率很低，没有太大的实用价值。
（2）1998年Cramer和Shoup提出了在标准数论假设下，而不是依赖于RO模型的数字签名方案（记作CS98方案），该方案具有实用价值，有很重要的意义，所以被广泛应用。CS98方案的安全性基于DDH问题，是IND－CCA2安全的。相对于RO模型中基于DDH问题的IND－CCA2方案，加，解密速度，以及密钥长度都大约是它们的两倍，也就是说RO模型中的方案有效率高的优势，但标准模型中的方案不需假设的杂凑函数是理想的 。
（3）2000年，Shoup等人对CS98方案进行了改进（记作CS00），一方面，当DDH假设成立，该方案在标准模型下依然是IND－CCA2安全的，另一方面，当DDH假设不成立，该方案在RO模型中，在CDH假设下是IND－CCA2安全的，而且效率较CS98高。在强RSA假设下，该方案对适应性选择消息攻击是安全的。
定理2 如果强RSA假设成立，“许多”Sophie Germain素数存在，且H是抗碰撞的，那么CS00方案对适应性选择消息攻击是安全的。
4 进一步研究
虽然许多研究者仍在研究RO模型的弊端，特别是它在复杂情况下的不适当性，但是RO模型的发展前景并不灰暗，它更积极方面的研究已经开始。RO模型与标准模型的不同本质在于确定的难题是否与零知识证明相关联。RO模型的研究不会停止，除非我们所构造出的密码体制可以简单而有效的在标准模型中就可证明是安全的。
抛开RO模型建立简单而有效的可证明安全密码系统最大的障碍在于对那些琐细的谕示询问（oracle queries）的反应。在完全淘汰RO模型的过程中，解决这些琐细的谕示询问将是向前迈出的一大步。研究者们在这一领域相当活跃，特别是和2004年由Bellare和Palacio提出的明文可意识性(plaintext awareness)相联系起来而进行的研究。将回应谕示询问和分析零知识协议这二者联系起来是非常有可能的。
5结束语
本文简单介绍了可证明安全性的发展过程，并介绍了在两种模型下几个比较有代表性的可证明安全的数字签名方案，最后给出可证明安全这一理论的有待进一步研究的问题。
参考文献:
[1]张文政.公钥密码体制可证明安全性的几点注记［J］.信息安全与通信保密,2005，7:125-127.
[2]任艳丽，谷大武.公钥密码方案的可证明安全性注记［J］.计算机应用研究,2008，4：1130－1133.
[3]Hans Delfs,Helmut Knebl著.肖国镇,张宁等译.密码学导引：原理与应用[M].北京：清华大学出版社,2008.
[4]梅其祥,唐小虎,何大可.抗选择密文攻击公钥密码体制的研究［J］计算机应用研究,2006，2:19-21 .
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文