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.     

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.     

Security of meta-He digital signature scheme based on factoring and discrete logarithms

To enhance the security of signature schemes, Pon et al., recently, investigated all eight variants of the He’s digital signature scheme. The security of the proposed schemes is based on the difficulties of simultaneously solving the factoring and discrete logarithm problems with almost the same sizes of arithmetic modulus. This paper shows that the all eight variants of the He’s digital signature scheme, as well as two more variants, are not secure if attackers can solve discrete logarithm problems. Moreover, the attackers can easily forge signatures of the most optimal signature schemes of the generalized He’ signature schemes even though they can solve neither discrete logarithm problems nor factoring.     

How (Not) to design strong-RSA signatures

This paper considers strong-RSA signature schemes built from the scheme of Cramer and Shoup. We present a basic scheme encompassing the main features of the Cramer-Shoup scheme. We analyze its security in both the random oracle model and the standard model. This helps us to spot potential security flaws. As a result, we show that a seemingly secure signature scheme (Tan in Int J Security Netw 1(3/4): 237?C242, 2006) is universally forgeable under a known-message attack. In a second step, we discuss how to turn the basic scheme into a fully secure signature scheme. Doing so, we rediscover several known schemes (or slight variants thereof).     

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

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

Efficient Rabin-type Digital Signature Scheme

Rabin's cryptosystem was proved to be as hard as factorization. However, Rabin's digital signature schemes is probabilistic. This paper shows two efficient Rabin type digital signature schemes, a basic scheme and an improved scheme. Both schemes run much faster than Rabin's scheme. They are deterministic and the size of a signature is much smaller than that of a signature in Rabin's scheme. Furthermore, it is proved that, by applying the technique of Bellare and Rogaway, the proposed scheme is secure against chosen plaintext attack. More precisely, breaking the proposed digital signature scheme by chosen plaintext attack is as hard as factoring N.     

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.     

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.      

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

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

Signcryption schemes with threshold unsigncryption,and applications

The goal of a signcryption scheme is to achieve the same functionalities as encryption and signature together, but in a more efficient way than encrypting and signing separately. To increase security and reliability in some applications, the unsigncryption phase can be distributed among a group of users, through a (t, n)-threshold process. In this work we consider this task of threshold unsigncryption, which has received very few attention from the cryptographic literature up to now (maybe surprisingly, due to its potential applications). First we describe in detail the security requirements that a scheme for such a task should satisfy: existential unforgeability and indistinguishability, under insider chosen message/ciphertext attacks, in a multi-user setting. Then we show that generic constructions of signcryption schemes (by combining encryption and signature schemes) do not offer this level of security in the scenario of threshold unsigncryption. For this reason, we propose two new protocols for threshold unsigncryption, which we prove to be secure, one in the random oracle model and one in the standard model. The two proposed schemes enjoy an additional property that can be very useful. Namely, the unsigncryption protocol can be divided in two phases: a first one where the authenticity of the ciphertext is verified, maybe by a single party; and a second one where the ciphertext is decrypted by a subset of t receivers, without using the identity of the sender. As a consequence, the schemes can be used in applications requiring some level of anonymity, such as electronic auctions.     

Provable certificateless generalized signcryption scheme

Generalized signcryption can adaptively work as an encryption scheme, a signature scheme or a signcryption scheme with only one algorithm. It is very suitable for storage-constrained environments. In this paper, we introduce a formal security model for certificateless generalized signcryption schemes secure against the malicious-but-passive key generation center attacks and propose a novel scheme. Our scheme is proved to be IND-CCA2 secure under the GBDH assumption and CDH assumption and existentially unforgeable under the GDH’ assumption and CDH assumption in random oracle model. Furthermore, performance analysis shows the proposed scheme is efficient and practical.     

Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem

The new signature scheme presented by the authors in [13] is the first signature scheme based on the discrete logarithm problem that gives message recovery. The purpose of this paper is to show that the message recovery feature is independent of the choice of the signature equation and that all ElGamal-type schemes have variants giving message recovery. For each of the six basic ElGamal-type signature equations five variants are presented with different properties regarding message recovery, length of commitment and strong equivalence. Moreover, the six basic signature schemes have different properties regarding security and implementation. It turns out that the scheme proposed in [13] is the only inversionless scheme whereas the message recovery variant of the DSA requires computing of inverses in both generation and verification of signatures. In general, message recovery variants can be given for ElGamal-type signature schemes over any group with large cyclic subgroup as the multiplicative group of GF(2n) or elliptic curve over a finite field.The present paper also shows how to integrate the DLP-based message recovery schemes with secret session key establishment and ElGamal encryption. In particular, it is shown that with DLP-based schemes the same functionality as with RSA can be obtained. However, the schemes are not as elegant as RSA in the sense that the signature (verification) function cannot at the same time be used as the decipherment (encipherment) function.     

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.     

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.     

Distributed Ring Signatures from General Dual Access Structures

In a distributed ring signature scheme, a subset of users cooperate to compute a distributed anonymous signature on a message, on behalf of a family of possible signing subsets. The receiver can verify that the signature comes from a subset of the ring, but he cannot know which subset has actually signed. In this work we use the concept of dual access structures to construct a distributed ring signature scheme which works with vector space families of possible signing subsets. The length of each signature is linear on the number of involved users, which is desirable for some families with many possible signing subsets. The scheme achieves the desired properties of correctness, anonymity and unforgeability. We analyze in detail the case in which our scheme runs in an identity-based scenario, where public keys of the users can be derived from their identities. This fact avoids the necessity of digital certificates, and therefore allows more efficient implementations of such systems. But our scheme can be extended to work in more general scenarios, where users can have different types of keys. Javier Herranz: The work of this author was carried out during the tenure of an ERCIM fellowship. Germán Sáez: The work of this author is partially supported by Spanish Ministerio de Educacíon y Ciencia under project TIC 2003-00866     

可证明安全的基于证书聚合签名方案

对刘云芳等人提出的基于证书聚合签名方案进行安全性分析,指出方案不能抵抗类型Ⅱ敌手攻击,并给出两种攻击方法,在此基础上提出了一个新的可证安全的基于证书聚合签名方案,利用Diffie-Hellman困难问题,在随机预言模型下证明了新方案是存在性不可伪造的.另外,新方案的聚合签名长度是固定常数,与签名者的数量无关,在签名验证中只需要4个对运算和n个标量乘运算,因此,新方案的签名验证效率得到很大提高.     

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].     

Security of Signature Schemes in a Multi-User Setting

This paper initiates the study of the security of signature schemes in the multi-user setting. We argue that the well-accepted notion of security for signature schemes, namely existential unforgeability against adaptive chosen-message attacks, is not adequate for the multi-user setting. We propose an extension of this security notion to the multi-user setting and show that signature schemes proven secure in the single-user setting can, under reasonable constraints, also be proven secure in the multi-user setting.     

Cryptanalysis of RGB,a mixed multivariate signature scheme

Public-Key Cryptography (PKC) based on multivariate quadratic equations is one of the most promising alternatives for classical PKC after the eventual coming of quantum computers. Recently, Shen and Tang proposed a new MQ-signature scheme, RGB, based on three types of variables, Red(r), Green(g) and Blue(b). They claimed that signing for RGB is faster than that of UOV and Rainbow. At ACISP 2016, Tang et al. implemented RGB on S5PV210 and MT6582 microprocessors at 64, 80, 96, 118 and 128-bit security levels for practical use. Their results are much more efficient than other MQ-signature schemes, so RGB is very appealing for resource-limited devices. We show that RGB with their suggested parameters at 64, 80, 96, 118 and 128 security levels are entirely broken by key recovery attacks using good keys. From a practical point of view, we are able to break their parameters at 64, 80, 96, 118 and 128 security levels in less than 0.48 seconds, 1.7 seconds, 90.68 seconds, 11 minutes and 6.82 hours, respectively. Consequently, we show that signing and the key sizes for RGB with secure parameter sets are much slower and larger than those of UOV and Rainbow.     

A multivariate cryptosystem inspired by random linear codes

We introduce a new multivariate encryption scheme inspired by random linear codes. The construction is similar to that of UOV, one of the oldest and most trusted multivariate signature schemes, but with a parameterization nothing like that of UOV. The structure of the scheme admits many generic modifications providing an array of security and performance properties. The scheme also supports an embedding modifier which allows any efficiently invertible multivariate system to be incorporated into the scheme. The product of this methodology is the fastest secure multivariate encryption scheme targeting CCA security at the 128-bit level.