Certificateless signature and proxy signature schemes from bilinear pairings

Due to avoiding the inherent escrow of identity-based cryptography and yet not requiring certificates to guarantee the authenticity of public keys, certificateless public key cryptography has received a significant attention. Due to various applications of bilinear pairings in cryptography, numerous pairing-based encryption schemes, signature schemes, and other cryptographic primitives have been proposed. In this paper, a new certificateless signature scheme based on bilinear pairings is presented. The signing algorithm of the proposed scheme is very simple and does not require any pairing computation. Combining our signature scheme with certificateless public key cryptography yields a complete solution of certificateless public key system. As an application of the proposed signature scheme, a certificateless proxy signature scheme is also presented. We analyze both schemes from security point of view.__________Published in Lietuvos Matematikos Rinkinys, Vol. 45, No. 1, pp. 95–103, January–March, 2005.     

一种无证书的环签名方案和一个基于身份的多重签名方案

在这篇文章里,我们用双线性对构造了一种无证书的环签名方案,并证明它是无条件匿名的,且在随机预言模型中,计算性Diffie-Hellman问题是难解的,我们方案在适应性选择消息攻击下是存在性不可伪造的,它的安全性比在基于身份的公钥密码体制下高.本文首次用多线性形式构造了一个基于身份的广播多重签名方案,它的安全性是基于计算性Diffie-Hellman困难问题.     

一种灵活的基于身份的签名方案

在基于身份的密钥提取过程中,使密钥生成器在私钥中嵌入随机数,从而使得密钥提取具有较好的灵活性,使得用户对一个身份可具备多个私钥,这无疑会增加密钥使用的安全性;基于这种新的密钥提取思路,给出一个基于身份的签名体制,新的密钥提取方式使得它具有更好的安全性和灵活性;新的基于身份的签名体制中具有最少对运算,因此,与类似的方案相比,其具备较好的计算效率;新签名体制的安全性依赖于k-合谋攻击问题(k-CAAP)的困难性,其在适应性选择消息和ID攻击下具备强不可伪造性,并且其安全性证明具有紧规约性.     

基于MSP秘密共享的（t，n）门限群签名方案

门限群签名是群签名中重要的—类,它是秘钥共享与群签名的有机结合．本文通过文献[5]中的MSP方案（Monotone Span Program）,提出了一种新的门限群签名方案．在本签名方案建立后,只有达到门限的群成员的联合才能生成—个有效的群签名,并且可以方便的加入或删除成员．一旦发生争议,只有群管理员才能确定签名人的身份．该方案能够抵抗合谋攻击：即群中任意一组成员合谋都无法恢复群秘钥k．本方案的安全性基于Gap Diffie-Hellman群上的计算Diffie-Hellmanl可题难解上,因此在计算上是最安全的．     

ID-based cryptography using symmetric primitives

A general method for deriving an identity-based public key cryptosystem from a one-way function is described. We construct both ID-based signature schemes and ID-based encryption schemes. We use a general technique which is applied to multi-signature versions of the one-time signature scheme of Lamport and to a public key encryption scheme based on a symmetric block cipher which we present. We make use of one-way functions and block designs with properties related to cover-free families to optimise the efficiency of our schemes.      

Efficient Undeniable Signature Schemes Based on Ideal Arithmetic in Quadratic Orders

In undeniable signature schemes the correctness or incorrectness of a signature of some message cannot be checked without the agreement of and the interaction with the signer. This is a favorable property for some applications. Well-known undeniable signature schemes presented in the literature will cause operations for the signer which take cubic running time. For a real world implementation, e.g., on a chip card or a web server this might be too inefficient.In this paper, we present new efficient undeniable signature schemes which are constructed over an imaginary quadratic field. We compare our schemes to the only really competitive scheme so far, which is based on RSA. In all signature protocols presented here the signer's part involving the secret key is always of quadratic complexity, which is much faster in practice than the signer's part in the RSA-based undeniable signature protocol.     

Comments on ID-based multi-signature with distinguished signing authorities

A multi-signature scheme with distinguished signing authorities is a multi-signature scheme where the signed document is divided into several parts and each signer signs only on the part which he is responsible for. This article shows the security weakness of Wu–Hsu’s ID-based multi-signature scheme with distinguished signing authorities.     

Comparing two pairing-based aggregate signature schemes

In 2003, Boneh, Gentry, Lynn and Shacham (BGLS) devised the first provably-secure aggregate signature scheme. Their scheme uses bilinear pairings and their security proof is in the random oracle model. The first pairing-based aggregate signature scheme which has a security proof that does not make the random oracle assumption was proposed in 2006 by Lu, Ostrovsky, Sahai, Shacham and Waters (LOSSW). In this paper, we compare the security and efficiency of the BGLS and LOSSW schemes when asymmetric pairings derived from Barreto–Naehrig (BN) elliptic curves are employed.     

Improvement on Hwang et al.’s generalization of proxy signature schemes based on elliptic curves

Hwang et al. proposed their generalization of proxy signature schemes based on elliptic curves. However, two attacks are proposed to show that their schemes have serious security flaws. By the first attack, an adversary can forge an illegal proxy signature that verifiers cannot actually find out the original signers of proxy signatures. The second attack is used to change proxy signatures into multi-signatures belonging to the group that actually generates the proxy signatures. To overcome these flaws, our improvement on Hwang et al.’s scheme is also proposed.     

Fine-grained forward-secure signature schemes without random oracles

We propose the concept of fine-grained forward-secure signature schemes. Such signature schemes not only provide non-repudiation w.r.t. past time periods the way ordinary forward-secure signature schemes do but, in addition, allow the signer to specify which signatures of the current time period remain valid when revoking the public key. This is an important advantage if the signer produces many signatures per time period as otherwise the signer would have to re-issue those signatures (and possibly re-negotiate the respective messages) with a new key.Apart from a formal model for fine-grained forward-secure signature schemes, we present practical schemes and prove them secure under the strong RSA assumption only, i.e., we do not resort to the random oracle model to prove security. As a side-result, we provide an ordinary forward-secure scheme whose key-update time is significantly smaller than that of known schemes which are secure without assuming random oracles.     

Comment on traceability on RSA-based partially signature with low computation

Recently, Chien et al. proposed RSA-based partially blind signature with low computation for mobile and smart-card applications. Hwang et al. claimed that Chien et al.’s scheme cannot meet the untraceability property of the blind signature later. In this paper, we show that Hwang et al.’s claim is incorrect and Chien et al.’s scheme is still satisfy the untraceability property.     

前向安全的指定验证人代理多重签名方案

基于有限域上离散对数难解问题和强RSA假设,提出了一个前向安全的指定验证人代理多重签名方案.在方案中,代理签名人不仅可以代表多个原始签名人生成指定验证人的代理多重签名,确保只有原始签名人指定的验证人可以验证代理多重签名的有效性;而且在该方案中,代理多重签名是前向安全的,即使代理签名人当前时段的代理多重签名密钥被泄漏,敌手也不能伪造此时段之前的代理多重签名,以前所产生的代理多重签名依然有效.     

Weakness and improvement on Wang–Li–Tie’s user-friendly remote authentication scheme

In an open network environment, the remote authentication scheme using smart cards is a very practical solution to validate the legitimacy of a remote user. In 2003, Wu and Chieu presented a user-friendly remote authentication scheme using smart cards. Recently, Wang, Li, and Tie found that Wu–Chieu’s scheme is vulnerable to the forged login attack, and then presented an improvement to eliminate this vulnerability. In our opinion, the smart card plays an important role in those schemes. Therefore, we demonstrate that Wang–Li–Tie’s scheme is not secure under the smart card loss assumption. If an adversary obtains a legal user’s smart card even without the user’s corresponding password, he can easily use it to impersonate the user to pass the server’s authentication. We further propose an improved scheme to overcome this abuse of the smart card.     

有指定秘书的(t,n)门限群签名体制

设计了一类只有指定的秘书才能发布有效群签名的可追查签名者身份的(t,n)门限群签名体制．该体制的优点是：(1)验证的简单性;(2)系统更新时无须更改每个成员的子密钥;(3)成员的增加或删除不影响群中其他的成员;(4)群中成员的子密钥可以无限制的使用;(5)t个成员合谋无法假冒其他成员生成有效的群签名．     

Certificateless signature: a new security model and an improved generic construction

Certificateless cryptography involves a Key Generation Center (KGC) which issues a partial key to a user and the user also independently generates an additional public/secret key pair in such a way that the KGC who knows only the partial key but not the additional secret key is not able to do any cryptographic operation on behalf of the user; and a third party who replaces the public/secret key pair but does not know the partial key cannot do any cryptographic operation as the user either. We call this attack launched by the third party as the key replacement attack. In ACISP 2004, Yum and Lee proposed a generic construction of digital signature schemes under the framework of certificateless cryptography. In this paper, we show that their generic construction is insecure against key replacement attack. In particular, we give some concrete examples to show that the security requirements of some building blocks they specified are insufficient to support some of their security claims. We then propose a modification of their scheme and show its security in a new and simplified security model. We show that our simplified definition and adversarial model not only capture all the distinct features of certificateless signature but are also more versatile when compared with all the comparable ones. We believe that the model itself is of independent interest.A conventional certificateless signature scheme only achieves Girault’s Level 2 security. For achieving Level 3 security, that a conventional signature scheme in Public Key Infrastructure does, we propose an extension to our definition of certificateless signature scheme and introduce an additional security model for this extension. We show that our generic construction satisfies Level 3 security after some appropriate and simple modification. A preliminary version of the extended abstract of partial results appeared in ACISP 2006 [9].     

An improved signature scheme without using one-way Hash functions

Recently, Chang et al. give a digital signature scheme, where neither one-way hash function nor message redundancy schemes are used, but Zhang et al. has shown that the scheme was forgeable, namely, any one can forge a new signature by the signer’s signature, and give two forgery attacks. To the above attacks, we give an improved signature scheme based on Chang signature scheme and analyze the security of the improved scheme.     

Efficient discrete logarithm based multi-signature scheme in the plain public key model

In this paper, we provide a new multi-signature scheme that is proven secure in the plain public key model. Our scheme is practical and efficient according to computational costs, signature size and security assumptions. At first, our scheme matches the single ordinary discrete logarithm based signature scheme in terms of signing time, verification time and signature size. Secondly, our scheme requires only two rounds of interactions and each signer needs nothing more than a certified public key to produce the signature, meaning that our scheme is compatible with existing PKIs. Thirdly, our scheme has been proven secure in the random oracle model under standard discrete logarithm (DL) assumption. It outperforms a newly proposed multi-signature scheme by Bagherzandi, Cheon and Jarecki (BCJ scheme) in terms of both computational costs and signature size.     

List signature schemes

A group signature scheme allows group members to issue signatures on behalf of the group, while hiding for each signature which group member actually issued it. Such scheme also involves a group manager, who is able to open any group signature by showing which group member issued it.We introduce the concept of list signatures as a variant of group signatures which sets a limit on the number of signatures each group member may issue. These limits must be enforced without having the group manager open signatures of honest group members—which excludes the trivial solution in which the group manager opens every signature to see whether some group members exceed their limits. Furthermore, we consider the problem of publicly identifying group members who exceed their limits, also without involving the group manager.     

Comment: A new blind signature based on the discrete logarithm problem for untraceability

In 2004, Lee et al. [C.C. Lee, M.S. Hwang, W.P. Yang, A new blind signature based on the discrete logarithm problem for untraceability, Appl. Math. Comput., in press] proposed a new untraceable blind signature based on DLP in order to overcome the “security limits” of Carmenisch et al.’s scheme. However, we show there are two mistakes in [C.C. Lee, M.S. Hwang, W.P. Yang, A new blind signature based on the discrete logarithm problem for untraceability, Appl. Math. Comput., in press]: 1. The Carmenisch et al.’s scheme does meet the requirement of untraceability and the cryptanalysis proposed by Lee et al. is not correct; 2. Though Lee et al.’s scheme is untraceable, the proof of its untraceability in [C.C. Lee, M.S. Hwang, W.P. Yang, A new blind signature based on the discrete logarithm problem for untraceability, Appl. Math. Comput., in press] is wrong (in this paper we also give the correct proof of its untraceability). So Lee et al.’s scheme does not have any advantage and it is unpractical since the cost of the scheme is higher compared with Carmenisch et al.’s scheme.     

一种基于矩阵法秘密分享协议的门限数字签名方案

本文研究了门限数字签名.根据一种矩阵法町验证秘密分享协议,构造出一种新的有指定接收者的、基于椭圆曲线密码机制(ECC)的门限数字群签名方案.方案计算简单、实用,具有较好的安全性.