【作者】 王志伟；

【导师】 胡正名；

【作者基本信息】 北京邮电大学 ， 密码学， 2009， 博士

【摘要】 随着计算机网络通信技术和软件技术的迅猛发展,如何保证及加强信息安全性和完整性已成为国际社会普遍关心的重大问题。数字签名应运而生。数字签名是公钥密码学领域最重要的发展方向之一。在公钥密码学中,密钥是由公开密钥和私有密钥组成的密钥对。签名者用私有密钥进行加密,接收方用公开密钥进行解密。由于从公开密钥不能推算出私有密钥,所以公开密钥不会损害私有密钥的安全。公开密钥无需保密可以公开的传播,而私有密钥必须保密。因此当某人用其私有密钥加密消息,能够用他的公开密钥正确解密,就可以肯定该消息是某人签的字,这就是数字签名的基本原理。低端计算设备包括智能卡,无线传感器,RFID设备,电子钥匙等等。这些设备的使用正在全球方兴未,它们的共同特点是计算能力非常弱,能源供应有限（决定于电池的容量）,或者反应时间极短。因此,应用于低端计算设备的签名方案必须优先考虑计算量。目前适用于低端计算设备的签名体制,有新型快速公钥密码体制中的多变量签名体制,辫群签名体制,基于格的签名体制等等,还有特殊属性签名体制中的在线/离线签名体制,服务器辅助验证签名体制等等。本论文受国家973计划（No.2007CB31074）、国家自然科学基金项目（No.90718001,60821001）、111项目（No.B08004）和索尼（中国）研究院资助。论文对研究过程中取得的主要创新成果进行了详细阐述。这些创新工作简要归纳如下:1.设计了一个高效且安全的多变量签名方案。我们的构造利用了这样一个事实,即在F₂的扩域上进行平方运算很快,仅仅是线性运算。新设计的签名方案能够抵御目前针对多变量密码体制的四种攻击,即线性化方程攻击,秩攻击,XL/Grobner基攻击和差分攻击。2.改进了概率化扰动方法,使其公钥长度大大减少。并依据概率化扰动方法的特点,重新设计了一个合适的中心映射。对新中心映射和改进的概率化方法组合成的概率多变量签名方案作了安全性分析。3.研究了最优的在线离线签名。改进和设计了2个具体的方案。其特点是在线部分计算量为零,离线部分的计算效率也较高,适用于低端计算设备。我们对这两个方案都给出了安全性证明。4.改进了服务器辅助验证签名的安全模型。在新安全模型下,分析了Wu等人提出的两个基于短签名的服务器辅助验证签名方案。基于Paillier签名构造了一个新的服务器辅助验证签名方案。新方案利用了Paillier原签名的验证函数的同态性。在我们的方案中,验证者通过与服务器共同执行服务器辅助验证协议,对签名的验证只需363次模乘,便可达到安全级别2⁸⁰,而原Paillier签名的验证需要2049次模乘。计算量降低了约80%。此外,我们还提出了服务器辅助验证签名的一种通用构造。5.设计了一个高效的代理签名方案,和其他已提出的代理签名方案相比,它的签名算法没有计算量较重的模指数运算和配对运算,比较适合计算能力较弱的低端计算设备。在随机预言模型下,我们证明了该方案是安全的。此外,我们还对代理签名作了一些扩展,提出了一种新型的特殊代理签名体制——极小代理签名。6.研究了三次剩余的特殊性质,并利用其构造了一个高效的基于身份的签名方案。该方案的签名阶段仅需161次模乘运算,便可达到安全级别2⁸⁰,与其他方案相比,计算效率比较高,更适用于低端计算设备。我们证明了该方案是抵抗选择消息和ID攻击安全的。更多还原

【Abstract】 With the rapid development of computer network communication technology and software technology, how to ensure and strengthen information security and integrity has become the major issue in the international community. Digital signature came into being. Digital signature is one of the most important directions of public key cryptography. In public key cryptography, key is a key pair composed by a public key and a private key. Signer uses the private key for encryption, while receiver uses the public key for decryption. Because it is difficult to compute the private key from the public key, the public key would not jeopardize the security of the private key. The public key can be publicly disseminated without being kept secret, while the private key should be preserved confidentially. Thus, if some one uses his private key to encrypt a message, which can be corretly decrypted, it can be sure the message is a signature of that person. This is the basic principle of digital signatures.The devices with limited computing capability includes smart card, wireless sensor, RFID, electronic key etc.. Now, using of these devices is very popular all over the world. However, they tend to have a feather in common: limited computational capability and equally limited power （at most operate on batteries）, very limited response time. Thus, the designing of signature schemes applicable for these devices should mainly focus on the computational efficiency. Now, many kinds of signature systems been suitable for the devices with limited computing capability, includes multivariate signature systems, braid group based signature systems, and lattice based signature systems which belongs to the new fast public key cryptosystems; and online/offline signature systems, server-aided verification signature systems which belongs to the signature with special properties systems.This thesis is jointly supported by National Basic Research Program of China（973 Program）（No. 2007CB310704）, National Natrual Science Foundation of China （No. 90718001 and No. 60821001）, the 111 Project（No. B08004） and Sony （China） research laboratory supportedThe principal contributions of the work presented in this thesis are:1. We designed an efficient and secure multivariate signature scheme. For our construction, we utilized this fact that squaring is a linear operation on an extension field of F₂. The newly designed multivariate signature scheme can resist the known attacks on multivariate public key cryptosystems, including linearization equation attack, Rank attack, XL/Grobner basis algorithm attack, and differential attack.2. We improved the probabilistic perturbed method, and made the public key length of it be greatly reduced. We redesigned a proper central map according to the characteristics of the probabilistic perturbed method. We analysized the security of the signature scheme composed by the new central map and the improved probabilistic perturbed method.3. We researched the optimal online/offline signature, and improved and designed two concrete schemes which have the feathers in common: no computational cost is needed in the online phase; the offline phase is also efficient. They are especially suitable for the devices with limited computing capability.4. We improved the security model of server-aided verification signature, and analysis the two short signature based schemes proposed by Wu et al. under the new security model. We constructed a new server-aided verification signature scheme based on Paillier signature by using the homomorphic property. In our scheme, by executing the server-aided verification protocol with the server, the verifier only need perform 362 modular multiplications, while he should execute 2049 modular multiplications in the original scheme. The computational cost of verification is decreased by 80%. Furthermore, we proposed a generic construction of server-aided verification signature scheme. 5. We designed a highly efficient proxy signature scheme. Compared with other scheme, it needs no modular exponentiation and pairing in the signing algorithm. Thus, it is suitable for the low end devices. We proved that it is secure under the random oracles. Finally, we extended proxy signature scheme, and proposed a new kind of proxy signature scheme - Infinitesimal proxy signature.6. We research some properties of cubic residues, and based on which, we constructed an efficient ID-based signature scheme. Compared with other scheme, it has a very efficient signing algorithm, which only needs 161 modular multiplications at security level of 2⁸⁰. We proved that it is secure against the adaptively chosen messages and ID attack.更多还原