Waters签名方案的研究.doc

第11A期王少辉等：Waters签名方案的研究185Waters签名方案的研究王少辉, 张国艳, 展涛（山东大学 数学与系统科学学院，山东 济南 250100）摘 要：基于Waters提出的标准模型下基于决策Diffie-Hellman问题的(弱)不可伪造签名方案, 首先利用Shamir和Tauman模型, 分别提出了满足适应消息攻击下强(弱)不可伪造性的无随机预示的online/ offline签名; 然后, 以基于身份的通用指定接收人签名为例, 阐述了Waters签名在基于身份的签名方案中的应用; 最后提出了无hash函数的满足强不可伪造性的Waters签名。关键词：签名；Online/offline签名；Diffie-Hellman问题；基于身份签名；强(弱)不可伪造性中图分类号：TP309 文献标识码：A 文章编号：1000-436X(2007)11A-0181-05Research on waters signature WANG Shao-hui, ZHANG Guo-yan, ZHAN Tao(School of Mathematics and System Sciences, Shandong University, Jinan 250100, China)Abstract: Based on the signature scheme provably secure under the standard model proposed by Waters, first the schemes (strongly and weakly unforgeable versions) were turned into online/offline signatures schemes; then taken ID-based universal designated verifier signatures as an example, a generic method was given to explain how to apply Waters signature in ID-based system; at last, a strongly unforgeable Waters signature without hash function was proposed.Key words: signature; Online/offline signature, Diffie-Hellman assumption, ID-based signature; strongly(weakly) unforgeable1 引言数字签名是现代密码学的最基本概念之一，其保证了数据通信中的认证性、完整性和不可否认性。为了满足在电子商务、电子选举等应用的需求，一些具有附加性质的签名概念被提出，如盲签名、群签名、环签名等。收稿日期：2007-09-29基金项目：国家自然科学基金资助项目（90604036）；国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB807902）Foundation Items: The National Natural Science Foundation of China(90604036);The National Basic Research Program of China (973Program)(2007CB807902)1999年之前，所有可证明安全的数字签名都是基于随机预示模型(ROM, random oracle model)1。在ROM中，假设所有的参与者(合法的或非法的)都可以访问一个随机预言机，而这种假设在现实中并不存在，通常用Hash函数作为预言机的替代。虽然基于随机预示模型可以设计高效的算法，但是Hash函数设计的缺陷会带来对协议的攻击。而且，目前也有许多结果设计了在ROM中安全，但是任何的替代都是不安全的协议2。所以，设计标准模型下可证明安全的算法协议是目前的研究热点。1999年，Cramer等3提出了基于强RSA问题的标准模型下可证明安全的数字签名方案。从此，众多基于不同数学难题的方案被提出。2005年，Waters4提出了基于决策Diffie-Hellman问题的标准模型下的签名方案(Waters签名)。基于该方案，许多其他的非ROM模型下的签名方案59被提出。Waters方案存在以下不足：一是公钥过长，文献10在安全性和密钥长度方面给出了折衷方案; 二是其只满足弱不可伪造性，文献11给出了将一类弱不可伪造性方案转化成强不可伪造的方法，其中需要抗碰撞攻击的Hash函数存在这一假设。本文进一步研究了Waters签名方案。下文分为4个部分: 首先在第2节介绍了基础知识; 然后基于Shamir和Tauman的方法12，提出了标准模型下的Online/offline数字签名；第4节阐述了Waters签名在基于身份的数字签名的应用；最后提出了不利用Hash函数的满足强不可伪造性的Waters签名。2 预备知识称函数是可忽略的，如果对于任意的正多项式，当k足够大时，都有; 如果满足，则称其为不可忽略的。表示从集合S中随机选择元素x。2.1 双线性对设和分别是阶为素数的循环乘法群，g是的生成元。a、b、c是随机数，假定所取随机数属于，假设离散对数问题在和中都是难解的。定义1 称映射:为一个双线性对，如果满足: 双线性:，有; 非退化性: ; 可计算性: 存在有效的算法计算,。在群上，可以定义以下几个密码学问题: 计算Diffie-Hellman(CDH)问题: 给定，计算; 决策Diffie-Hellman(DDH)问题: 给定，判断是否满足; Gap Diffie-Hellman (GDH)问题: 一类CDH问题困难而DDH问题容易的问题。2.2 数字签名一个签名方案可以表示为(Gen，Sign，Verify)。其中Gen是概率多项式算法，输入安全参数，输出签名和认证密钥(pk，sk); Sign是概率多项式算法，输入m和sk，输出签名; Verify是确定时间算法，验证是否是某消息的签名: Verify(vk，m,)=valid是否成立。如果确实是Sign(m，sk)的输出，那么上式应成立。下边简单介绍适应性选择消息攻击下的强不可伪造性13和弱不可伪造性14。不可伪造性是通过如下攻击定义的: 运行Gen算法获得(pk，sk)对，将pk送攻击者; 然后攻击者适应性选择多项式个签名请求()，签名者给出相应的签名()送给攻击者; 最后攻击者输出()。定义2 (强(弱)不可伪造性) 签名方案称为适应性选择消息攻击下强不可伪造的，如果不存在t时间的攻击者，经s个签名询问后，Verify(，vk)=valid ()成立的概率至少是; 如果只是要求，则方案称为弱不可伪造的。2.3 Waters签名先简单回顾满足弱不可伪造性的Waters签名方案4。固定k，消息m被编码为。给定参数(,)。选择随机元。定义函数。Gen: 选择随机数，计算，则pk为()，sk为。Sign: 选择随机数，计算，签名。Verify: 验证关系式 是否成立，如果成立，则签名合法，否则是非法签名。比较显然，Waters签名不满足强不可伪造性，已知消息m的签名，很容易伪造m的其他合法签名。为此文献11给出了满足强不可伪造性的Waters签名。这里主要描述2个方案的不同之处：Gen: pk除了外，还有随机选择的和Hash函数H，sk不变。Sign: 随机选择，计算，计算，并用文献4的方案对m签名得到。Verify: 首先由计算m，然后验证是否有Verify的公式成立。3 无ROM的online/offline签名方案Online/offline签名方案由Even等15在1990年提出，思想是将签名方案分成2个阶段: offline阶段(待签消息未给定)和online阶段(待签消息给定)。当签名时间有限时，签名者可以在offline阶段做完大部分的计算工作，而在online阶段只要从事很少的计算，从而提高了效率。2001年，Shamir和Tauman12利用陷门Hash函数16，提出了一种新的签名模式“hash-sign-switch”。该模式中，普通的Hash函数被陷门Hash函数取代，从而提供了一种将普通的签名方案转化成高效online/offline签名的方法。利用该模式，Crutchfield等17提出了通用online/offline门限签名; Kurosawa，Samoa18提出了标准模型下基于强RSA的online/offline签名。本节依据“hash-sign-switch”模式，分别就弱(强)Waters签名提出了标准模型下的online/offline签名方案，设计关键在对参数的处理上，方案保持原方案的弱(强)不可伪造性。弱不可伪造性的online/offline签名:Gen: 随机选择，计算，则pk为()，sk为。Sign: Offline阶段: 随机选择消息m和随机数，计算,存储; Online阶段: 对给定的消息m，利用扩展Euclid算法计算r，满足 ,并计算。签名。Verify: 验证过程同原方案。原方案签名过程需要2个指数运算，平均需要大约个上的群运算。最差的情况要运行个上的运算，这里通常取160，从而运算比较繁杂; 在online/offline方案中，online阶段需要1个指数运算，并且将G1中的运算转化到Zp中，从而效率大大提高。强不可伪造性的online/offline签名:Gen: 选择随机数，计算，则pk为()，sk为。Sign: Offline阶段: 随机选择消息m 和随机数，按原签名方案得到,存储; Online阶段: 对给定的消息m，计算，然后求解s满足，签名。 Verify: 验证过程同原方案。原方案签名过程需要4个指数运算，平均需要大约k/2个G1上的群运算; 在online/offline方案中，online阶段不需要指数运算，只需要一个Hash运算和一个Zp运算，从而效率大大提高。4 Waters签名在基于身份签名中的应用Waters签名在具有附加性质的签名方案的设计中有比较灵活的应用5,6,9。基于Waters签名的群签名和环签名的设计采用两级分层签名: 第一级是针对签名者的身份，而第二级则针对需要签署的消息。然后利用Groth、Ostrovsky和Sahai19的非交互零知识证明系统将用户的身份信息隐藏，以克服认证的时候需要用户身份信息。具体方案不作介绍。1984年，Shamir提出了基于身份密码系统的概念1。该系统中，用户的公钥是与其身份紧密相关的字符串，如电子邮件地址。该系统解决了传统PKI系统耗费大量时间管理和认证公钥证书的问题。在基于身份的密码体制下，有一个称为PKG (private key generator)的可信中心负责给每个用户发放与其身份相对应的私钥。Waters签名算法本身是从基于身份的加密方案中演化而来，从其方案设计来看，其易于转化为基于身份的签名方案。只要将上述Waters签名中的私钥换成PKG给用户的私钥即可。以基于身份的通用指定接收人签名(UDVS, universal designated verifier signature)为例说明。这对于基于身份的盲签名，基于身份的多重签名等都适用。UDVS由Steinfeld等20提出，签名者可以通过UDVS的Designate算法将一般的签名转化成指定接收人验证的签名，方案只是满足弱不可伪造性，我们容易利用文献11的方法设计满足强不可伪造性的签名方案。给定参数()和Hash函数，PKG选择随机数s作为主私钥，计算为主公钥。Gen: 给定身份ID，其公钥，PKG计算为用户私钥并通过安全信道送用户。Sign: 对给定的消息m，随机选择，计算，签名。Verify: 验证关系式是否成立: ，如果成立为合法签名，否则是非法的。对于特定的用户，签名者可以用如下方法把上述签名转化成只有可以验证合法性的签名：Designate: 签名者计算 ，签名。DVerify: 验证关系式 是否成立来判断签名的合法性。下边简单讨论方案满足的一些性质:不可伪造性: 在Sign算法中，由于攻击者不知道签名者的私钥信息，伪造出合法签名的概率是可以忽略的，从而在能够通过DVerify的合法指定接收人的签名的概率也是可忽略的，具体的讨论可以参考文献4,7。信息隐藏性: 指定验证算法需要指定用户的私钥，从而杜绝了非指定用户对签名的认证。而且，容易看出指定签名对于签名者和指定接收人而言是不可区分的。签名者隐藏性: 对于由不同签名者针对同一接收用户的签名，由于攻击者无法正确的进行DVerify算法，从而正确判断签名来自哪一个签名者的概率是可以忽略的。5 强不可伪造性的Waters签名文献11提出的满足强不可伪造的Waters签名，需要抗碰撞攻击Hash函数存在这一假设，否则容易构造2个消息具有相同的合法签名。本节提出不依靠Hash函数的满足强不可伪造性的Waters签名方案。Waters签名分为2个独立的部分，一部分包含供给者无法控制的私钥，另一部分包含签名消息和随机数。由于和S2的指数都采用线性的形式，可通过对随机数进行同步变化伪造同一消息的不同签名。新方案避免了这个问题，限制了攻击者对随机数控制和更改的能力。Gen: 随机选择，计算，则pk为，sk为。Sign: 随机选择，计算 ，签名。Verify: 验证关系式: 和是否成立。新方案签名需要3个指数运算，少于文献11中的4个指数运算，但比文献11多一个认证公式。由离散对数问题的难解性，如果没有，攻击者不能知道的值，从而伪造一个新消息m的合法签名的概率是可忽略的，而且给定消息m的一个合法签名，不可能构造另一个合法签名。攻击者存在如下2个攻击。虽然对任意的，存在，满足，但从并不能计算或。因为的指数采用非线性的形式，指数的变化与并不一致，从而攻击者对签名的第二部分进行控制时，必然引入涉及到第一部分的项，而攻击者并不能控制签名的第一部分。例如，如果攻击者选择随机数s，构造，指数为，容易计算满足。此时的指数应该为，但是攻击者并不知道，无法添加，不同项指数变化的不一致导致攻击者难以伪造m的另一个合法签名。参考文献：1BELLARE M, ROGAWAY P. Random oracles are practical: a paradigm for designing efficient protocolsA. Proceedings of CCS 1993C. 1993.62-73.2CANETTI R, GOLDREICH O, HALEVI S. The random oracle methodology, revisitedJ. J ACM, 2004,51(4):557-594.3CRAMER R, SHOUP V. Signature schemes based on the strong RSA assumptionA. ACM Conference on Computer and Communications Security 99C. 1999. 46-51.4WATERS B. Efficient identity-based encryption without random oraclesA. EUROCRYPT 2005C. 2005.114-127.5BOYEN X, WATERS B. Compact group signatures without random oraclesA. EUROCRYPT 2006C. 2006. 427-444.6BOYEN X, WATERS B. Full-domain subgroup hiding and constant-size group signatureA. PKC 2007, LNCS 4450C. 2007.1-15.7LAGUILLAUMIE F, LIBERT B, QUISQUATER J J. Universal designated verifier signatures without random oracles or non-black box AssumptionsA. SCN 2006C.2006.63-77.8OKAMOTO T. Efficient blind and partially blind signatures without random oraclesA. Theory of Cryptography (TCC 2006)C. 2006. 80-99.9SHACHAM H, WATERS B. Efficient Ring Signatures Without Random OraclesR. Cryptology ePrint Archive: Report 2006/289. 10NACCACHE D. Secure and Practical Identity-Based EncryptionR. Cryptology ePrint Archive: Report 2005/369(2005).11BONEH D, SHEN E, WATERS B. Strongly unforgeable signatures based on computational diffie-hellmanA. PKC 2006C. 2006. 229- 240.12SHAMIR A, TAUMAN Y. Improved online/offline signature schemesA. CRYPTO 2001C. 2001. 355-367. 13STERN J, POINTCHEVAL D, LEE J M, et al. Flaws in applying proof methodologies to signature schemesA. CRYPTO 2002C. 2002. 93-110.14GOLDWASSER S, MICALI S, RIVEST R. A digital signature scheme secure against adaptive chosen-message attacksJ. SIAM J Computing, 1988, 17(2): 281-308.15EVEN S, GOLDREICH O, MICALI S. Online/offline digital signatureJ. Journal o