Efficient forward secure identity-based shorter signature from lattice

All regular cryptographic schemes rely on the security of the secret key. However, with the explosive use of some relatively insecure mobile devices, the key exposure problem has become more aggravated. In this paper, we propose an efficient forward secure identity-based signature (FSIBS) scheme from lattice assumption, with its security based on the small integer solution problem (SIS) in the random oracle model. Our scheme can guarantee the unforgeability of the past signatures even if the current signing secret key is revealed. Moreover, the signature size and the secret key size of our scheme are unchanged and much shorter. To the best of our knowledge, our construction is the first FSIBS scheme based on lattice which can resist quantum attack. Furthermore, we extend our FSIBS scheme to a forward secure identity-based signature scheme in the standard model.     

Provably secure server-aided verification signatures

A server-aided verification signature scheme consists of a digital signature scheme and a server-aided verification protocol. With the server-aided verification protocol, some computational tasks for a signature verification are carried out by a server, which is generally untrusted; therefore, it is very useful for low-power computational devices. In this paper, we first define three security notions for server-aided verification signatures, i.e., existential unforgeability, security against collusion attacks and security against strong collusion attacks. The definition of existential unforgeability includes the existing security requirements in server-aided verification signatures. We then present, on the basis of existing signature schemes, two novel existentially unforgeable server-aided verification signature schemes. The existential unforgeability of our schemes can be formally proved both without the random oracle model and using the random oracle model. We also consider the security of server-aided verification signatures under collusion attacks and strong collusion attacks. For the first time, we formally define security models for capturing (strong) collusion attacks, and propose concrete server-aided verification signature schemes that are secure against such attacks.     

Security of the design of time-stamped signatures

To ensure integrity and originality of digital information, digital signatures were proposed to provide both authority and non-repudiation. However, without an authenticated time-stamp, we can neither trust signed documents when the signers' signature key was lost, stolen, or accidentally compromised, nor solve the cases when the signer himself repudiates the signing, claiming that has accidentally lost his signature key. To withstand forward forgery suffered by linking schemes and to reduce verification cost, Sun et al. proposed four time-stamped signature schemes that are based on absolute temporal authentication. Though Sun et al. claimed that these schemes are quite secure against the forward forgery, we find that they suffered from substitution attacks, by which the signer can backward/forward forge signatures and the time-stamping service can also forge signatures. Finally, we also propose four time-stamped signature schemes to overcome these security flaws. Moreover, the proposed new schemes are more efficient than the Sun et al. schemes.     

Enhanced short signature scheme with hybrid problems

Short digital signatures are always desirable; for instance, when a human is asked to key in the signature manually or it is necessary to work effectively in low-bandwidth communication, low-storage and low-computation environments. We propose a short signature scheme based on knapsack and Gap Diffie-Hellman (GDH) groups whose security is closely related to the discrete logarithm assumption in the random oracle model. Our new scheme offers a better security guarantee than existing signature schemes. Furthermore, our scheme upholds all desirable properties of previous ID-based signature schemes, and requires general cryptographic hash functions instead of MapToPoint hash function that is inefficient and probabilistic.     

Intrusion-resilient identity-based signature: Security definition and construction

Traditional identity-based signatures depend on the assumption that secret keys are absolutely secure. Once a secret key is exposed, all signatures associated with this secret key have to be reissued. Therefore, limiting the impact of key exposure in identity-based signature is an important task. In this paper, we propose to integrate the intrusion-resilient security into identity-based signatures to deal with their key exposure problem. Compared with forward-secure identity-based signatures and key-insulated identity-based signatures, our proposal can achieve higher security. The proposed scheme satisfies that signatures in any other time periods are secure even after arbitrarily many compromises of base and signer, as long as the compromises do not happen simultaneously. Furthermore, the intruder cannot generate signatures pertaining to previous time periods, even if she compromises base and signer simultaneously to get all their secret information. The scheme enjoys nice average performance. There are no cost parameters including key setup time, key extract time, base (signer) key update time, base (signer) key refresh time, signing time, verifying time, and signature size, public parameter size, base (signer) storage size having complexity more than O(log T) in terms of the total number of time periods T in this scheme. We also give the security definition of intrusion-resilient identity-based signature scheme and prove that our scheme is secure based on this security definition in the random oracle model assuming CDH problem is hard.     

Identity-based aggregate signcryption in the standard model from multilinear maps

Signcryption is a public key cryptographic method that achieves unforgeability and confidentiality simultaneously with significantly smaller overhead than that required by “digital signature followed by public key encryption”. It does this by signing and encrypting a message in a single step. An aggregate signcryption scheme allows individual signcryption ciphertexts intended for the same recipient to be aggregated into a single (shorter) combined ciphertext without losing any of the security guarantees.We present an aggregate signcryption scheme in the identity-based setting using multilinear maps, and provide a proof of security in the standard model. To the best of our knowledge, our new scheme is the first aggregate signcryption scheme that is secure in the standard model.     

Off-line/on-line signatures revisited: a general unifying paradigm, efficient threshold variants and experimental results

The notion of off-line/on-line digital signature scheme was introduced by Even, Goldreich and Micali. Informally such signatures schemes are used to reduce the time required to compute a signature using some kind of preprocessing. Even, Goldreich and Micali show how to realize off-line/on-line digital signature schemes by combining regular digital signatures with efficient one-time signatures. Later, Shamir and Tauman presented an alternative construction (which produces shorter signatures) obtained by combining regular signatures with chameleon hash functions. In this paper, we study off-line/on-line digital signature schemes both from a theoretic and a practical perspective. More precisely, our contribution is threefold. First, we unify the Shamir–Tauman and Even et al. approaches by showing that they can be seen as different instantiations of the same paradigm. We do this by showing that the one-time signatures needed in the Even et al. approach only need to satisfy a weak notion of security. We then show that chameleon hashing is basically a one-time signature which satisfies such a weaker security notion. As a by-product of this result, we study the relationship between one-time signatures and chameleon hashing, and we prove that a special type of chameleon hashing (which we call double-trapdoor) is actually a fully secure one-time signature. Next, we consider the task of building, in a generic fashion, threshold variants of known schemes: Crutchfield et al. proposed a generic way to construct a threshold off-line/on-line signature scheme given a threshold regular one. They applied known threshold techniques to the Shamir–Tauman construction using a specific chameleon hash function. Their solution introduces additional computational assumptions which turn out to be implied by the so-called one-more discrete logarithm assumption. Here, we propose two generic constructions that can be based on any threshold signature scheme, combined with a specific (double-trapdoor) chameleon hash function. Our constructions are efficient and can be proven secure in the standard model using only the traditional discrete logarithm assumption. Finally, we ran experimental tests to measure the difference between the real efficiency of the two known constructions for non-threshold off-line/on-line signatures. Interestingly, we show that, using some optimizations, the two approaches are comparable in efficiency and signature length.     

Efficient key insulated attribute based signature without bilinear pairings for mobile communications

Attribute based signature (ABS) is a significant cryptographic notion providing secure authentication during data sharing. A signer can sign a message using the private keys he processes. However, user’s private key exposure may happen from time to time and this will bring potential threat to the whole system. Thus, key evolving mechanism should be introduced into ABS schemes. Besides, the efficiency of existing ABS schemes can be further improved since the process of signing and verification require massive bilinear pairings, which occupies costly computing resources on mobile terminal devices. To better tackle the above problems and provides a more secure data authentication method in mobile communication systems, in this paper, we firstly propose a key insulated attribute based signature scheme without pairings (KI-ABS-WP). Then we give the formalized definition as well as the concreted constructions of our scheme. In our KI-ABS-WP, uses needn’t run any bilinear pairings, thus the total computation cost has been reduced to a large extent. If key exposure occurs, key insulation mechanism guarantees system’s both backward and forward security. Finally, by security proof and efficiency comparison, our KI-ABS-WP is shown to be more superior for data authentication in mobile communication systems.     

Protocols useful on the Internet from distributed signature schemes

Distributed cryptography deals with scenarios where a cryptographic operation is performed by a collective of persons. In a distributed signature scheme, a group of players share some secret information in such a way that only authorized subsets of players can compute valid signatures. We propose methods to construct some computationally secure protocols from distributed signature schemes, namely, we construct metering schemes from distributed noninteractive signature schemes. We also show that distributed deterministic signature schemes can be used to design distributed key distribution schemes. In particular, we construct the first metering and distributed key distribution schemes based on the RSA primitive.     

Performance study of online batch-based digital signature schemes

A digital signature is an important type of authentication in a public-key (or asymmetric) cryptographic system, and it is widely used in many digital government applications. We, however, note that the performance of an Internet server computing digital signatures online is limited by the high cost of modular arithmetic. One simple way to improve the performance of the server is to reduce the number of computed digital signatures by combining a set of documents into a batch in a smart way and signing each batch only once. This approach could reduce the demand on the CPU but require more network bandwidth of sending extra information to clients.In this paper, we investigate performance of different online digital signature batching schemes. That is, we provide a framework for studying as well as analyzing performance of a variety of such schemes. The results show that substantial computational benefits can be obtained from batching without significant increases in the amount of additional information that needs to be sent to the clients. Furthermore, we explore the potential benefits of considering more sophisticated batching schemes. The proposed analytical framework uses a semi-Markov model of a batch-based digital signature server. Through the emulation and the simulation, the results show the accuracy and effectiveness of our proposed analytic framework.     

一种高效的指定验证人的代理签名方案

代理签名与指定验证人签名都是非常有用的密码学工具，在实际生活中有着广泛的应用。在代理签名中，原始签名人能将数字签名的权力委托给代理签名人；而在指定验证人签名方案中，对于验证人是有所限制的。该文结合二者的优点，利用基于离散对数的Schnorr数字签名方案构造了一个指定验证人的代理签名方案。新提出的方案能够满足代理签名和指定验证人签名的安全性质。分析显示，新方案不仅是安全的，而且在通信和计算方面是高效的。     

Signature schemes with a fuzzy private key

In this paper, we introduce a new concept of digital signature that we call fuzzy signature, which is a signature scheme that uses a noisy string such as biometric data as a private key, but does not require user-specific auxiliary data (which is also called a helper string in the context of fuzzy extractors), for generating a signature. Our technical contributions are threefold: (1) we first give the formal definition of fuzzy signature, together with a formal definition of a “setting” that specifies some necessary information for fuzzy data. (2) We give a generic construction of a fuzzy signature scheme based on a signature scheme that has certain homomorphic properties regarding keys and satisfies a kind of related key attack security with respect to addition, and a new tool that we call linear sketch. (3) We specify two concrete settings for fuzzy data, and for each of the settings give a concrete instantiation of these building blocks for our generic construction, leading to two concrete fuzzy signature schemes. We also discuss how fuzzy signature schemes can be used to realize a biometric-based PKI that uses biometric data itself as a cryptographic key, which we call the public biometric infrastructure.

     

可传递签名研究综述

可传递签名是由Micali和Rivest在2002年首先提出的，主要用于对二元传递关系进行签名。本文综述了可传递签名的研究现状，描述了可传递签名的定义、模型及其安全性，概括了现有的可传递签名方案，包括无向传递签名方案和有向传递签名方案。最后对可传递签名的研究前景进行了展望。     

标准模型下高效的代理签名方案

代理签名方案允许原始签名者将自己的签名权力授权给代理签名者,使得代理签名者能够代表原始签名者对消息进行签名。提出了一个新的标准模型下可证安全的代理签名方案,其安全性基于q-强Diffie-Hellman困难问题,证明了该方案在标准模型下能够抵抗适应性选择消息攻击下的存在性伪造。与已有的方案进行比较,提出的方案需要较少的公共参数,实现了紧凑的安全归约,并且在密钥生成、标准签名、授权生成、代理签名生成等阶段具有较高的效率。     

一个可证明安全的代理签名方案

代理签名是一方将自己签名的能力授权给另一方，是一种很重要的密码协议，目前已知的可证明安全的代理签名还很少。该文利用间隙Diffie—Hellman（GDH）群的特点构造了一个新的代理签名方案，新方案在随机预言模型下是可证明安全的。     

Secret handshakes from ID-based message recovery signatures: A new generic approach

Secret handshake scheme, as a relatively new cryptographic application, allows the members of a certain organization to secretly authenticate each other. In this paper, we present a new generic framework for transforming any ID-based message recovery signature to a secret handshake scheme, whose provability can be determined by the security of underlying signature. Based on our new generic framework, two concrete secret handshake schemes are elaborated, which originate from two different ID-based message recovery signatures and are provably secure against the chosen-message attack in the random oracle model.     

ID-based proxy signature scheme with message recovery

A proxy signature scheme, introduced by Mambo, Usuda and Okamoto, allows an entity to delegate its signing rights to another entity. Identity based public key cryptosystems are a good alternative for a certificate based public key setting, especially when efficient key management and moderate security are required. From inception several ID-based proxy signature schemes have been discussed, but no more attention has been given to proxy signature with message recovery. In this paper, we are proposing provably secure ID-based proxy signature scheme with message recovery and we have proved that our scheme is secure as existential forgery-adaptively chosen message and ID attack. As proposed scheme is efficient in terms of communication overhead and security, it can be a good alternative for certificate based proxy signatures, used in various applications such as wireless e-commerce, mobile agents, mobile communication and distributed shared object systems, etc.     

A new efficient optimistic fair exchange protocol without random oracles

Optimistic fair exchange (OFE) is a kind of protocols to solve the problem of fair exchange between two parties. Most of the previous work on this topic are provably secure in the random oracle model. In this work, we propose a new construction of OFE from another cryptographic primitive, called time capsule signature. The construction is efficient and brings almost no overhead other than the primitive itself. The security of our new construction is based on that of the underlying primitive without relying on the random oracle heuristic. Applying our generic construction to the time capsule signature scheme recently proposed by Libert and Quisquater, we obtain a new concrete and efficient OFE construction secure based on Computational Diffie–Hellman assumption in the standard model.     

标准模型下基于身份代理盲签名方案

由于现有的基于身份代理盲签名方案要么没有得到形式化的安全证明,要么仅在随机预言（Random Oracle,RO）模型下可证明安全,提出一种标准模型下的基于身份代理盲签名方案。该方案的基本签名算法采用了Paterson等人提出的基于身份签名机制。在Paterson等人提出的标准安全模型基础上,引入代理签名敌手模型,并参考盲签名的安全模型,提出基于身份代理盲签名的标准模型。在此安全模型下,该方案被证明满足不可伪造性和盲性,具有可证明安全性。     

Fuzzy identity based signature with applications to biometric authentication

We introduce a new cryptographic primitive which is the signature analog of fuzzy identity based encryption (FIBE). We call it fuzzy identity based signature (FIBS). It possesses similar error-tolerance property as FIBE that allows a user with the private key for identity ω to decrypt a ciphertext encrypted for identity ω′ if and only if ω and ω′ are within a certain distance judged by some metric. We give the definition and security model of FIBS and present the first practical FIBS scheme. We prove that our scheme is existentially unforgeable against adaptively chosen message attack in the standard model. To our best knowledge, this primitive was never considered in the identity based signature before. FIBS is of particular value for biometric authentication, where biometric identifiers such as fingerprints, iris, voice and gait are used in human identification. We demonstrate the applicability of our construction to secure biometric authentication.