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 generic on-line/off-line (threshold) signatures without key exposure

The “hash–sign–switch” paradigm was firstly proposed by Shamir and Tauman with the aim to design an efficient on-line/off-line signature scheme. Nonetheless, all existing on-line/off-line signature schemes based on this paradigm suffer from the key exposure problem of chameleon hashing. To avoid this problem, the signer should pre-compute and store a plenty of different chameleon hash values and the corresponding signatures on the hash values in the off-line phase, and send the collision and the signature for a certain hash value in the on-line phase. Hence, the computation and storage cost for the off-line phase and the communication cost for the on-line phase in Shamir–Tauman’s signature scheme are still a little more overload. In this paper, we first introduce a special double-trapdoor hash family based on the discrete logarithm assumption and then incorporate it to construct a more efficient generic on-line/off-line signature scheme without key exposure. Furthermore, we also present the first key-exposure-free generic on-line/off-line threshold signature scheme without a trusted dealer. Additionally, we prove that the proposed schemes have achieved the desired security requirements.     

基于双线性对的Chameleon签名方案

Chameleon签名方案是一种利用Hash-and-Sign模式的非交互签名方案,并且具有不可转移性,只有指定的接收者才可以确信签名的有效性.利用双线性对提出了一种新的Chameleon Hash函数,并在此基础上构建了相应的基于身份的Chameleon签名方案.与传统的Chameleon Hash函数相比,该方案中的Hash函数公钥所有者无须获取相应私钥,除非它企图伪造签名.该方案不但具有通常Chameleon签名方案的所有特点,而且具有基于身份密码系统的诸多优点.     

Chameleon Hashes Without Key Exposure Based on Factoring

Chameleon hash is the main primitive to construct a chameleon signature scheme which provides nonrepudiation and non-transferability simultaneously. However, the initial chameleon hash schemes suffer from the key exposure problem： non-transferability is based on an unsound assumption that the designated receiver is willing to abuse his private key regardless of its exposure. Recently, several key-exposure-free chameleon hashes have been constructed based on RSA assumption and SDH （strong Diffie-Hellman） assumption. In this paper, we propose a factoring-based chameleon hash scheme which is proven to enjoy all advantages of the previous schemes. In order to support it, we propose a variant Rabin signature scheme which is proven secure against a new type of attack in the random oracle model.     

Short designated verifier proxy signatures

A proxy signature enables an original signer to delegate its signing capability to a proxy signer and the proxy signer can sign a message on behalf of the original signer. Later, anyone can verify the validity of proxy signatures. The “public-verifiable” property of the proxy signature is not suitable in some applications in which a proxy signed message may be personally or commercially sensitive. A designated verifier proxy signature scheme is suitable for these environments. In this paper, we propose a provably secure short designated verifier proxy signature scheme in the random oracle model under the Bilinear Diffie-Hellman assumption.     

Efficient strong designated verifier signature schemes without random oracle or with non-delegatability

Designated verifier signature (DVS) allows a signer to convince a designated verifier that a signature is generated by the signer without letting the verifier transfer the conviction to others, while the public can still tell that the signature must be generated by one of them. Strong DVS (SDVS) strengthens the latter part by restricting the public from telling whether the signature is generated by one of them or by someone else. In this paper, we propose two new SDVS schemes. Compared with existing SDVS schemes, the first new scheme has almost the same signature size and meanwhile, is proven secure in the standard model, while the existing ones are secure in the random oracle model. It has tight security reduction to the DDH assumption and the security of the underlying pseudorandom functions. Our second new scheme is the first SDVS supporting non-delegatability, the notion of which was introduced by Lipmaa, Wang and Bao in the context of DVS in ICALP 2005. The scheme is efficient and is provably secure in the random oracle model based on the discrete logarithm assumption and Gap Diffie–Hellman assumption.     

一种新的基于身份的变色龙数字签名方案

变色龙签名是一种非交互的数字签名，基于“先哈希后签名”的范式。其中使用的哈希函数是一种特殊的陷门单向哈希函数――变色龙哈希。变色龙签名与普通数字签名的不同之处在于不可传递性。应用双线性对，提出了一个新的基于身份的变色龙签名方案。新方案构造简洁，在随机预言模型下是安全的。     

Contract signature in e-commerce

In this paper, we propose a notion of contract signature used in e-commerce applications. We propose a contract signature scheme based on the discrete logarithm assumption. The contract signature scheme adopts a digital multi-signature scheme in public-key cryptography to facilitate fair signature exchange over network. This proposed solution allows multiple signers of a contract signature to exchange their partial signatures which are fully ambiguous for any third party (i.e., 1 out of ∞ ambiguity) to construct a valid contract signature. In case any signer releases the partial signature to others, the signer does not bind to the contract.     

一种部分盲签名方案

提出一个基于离散对数的部分盲签名方案,分析其安全性和效率。该方案满足部分盲性、不可追踪性和不可伪造性,可以防止消息提供者滥用签名,保证签名者不能侵犯消息提供者的身份隐私。与基于Schnorr签名算法和基于DSA变形签名算法的部分盲签名方案相比,该方案效率较高。     

可追踪签名者身份的匿名代理签名方案

在求解离散对数困难性的基础上,提出一种可追踪签名者身份的匿名代理签名方案。当原始签名人不方便签名时,代理人中的任何一个可进行匿名代理签名。当对某个代理签名发生争议时,原始签名人能找出签署消息的代理人。分析结果表明,该方案运算量小,具有较高的安全性。     

An efficient secure proxy verifiably encrypted signature scheme

Verifiably encrypted signature is an important cryptographic primitive, it can convince a verifier that a given ciphertext is an encryption of signature on a given message. It is often used as a building block to construct an optimistic fair exchange. In this paper, we propose a new concept: a proxy verifiably encrypted signature scheme, by combining proxy signature with a verifiably encrypted signature. And we formalize security model of proxy verifiably encrypted signature. After a detail construction is given, we show that the proposed scheme is provably secure in the random oracle model. The security of the scheme is related to the computational Diffie–Hellman problem.     

基于离散对数问题的一般盲签名方案

盲签名是一种所签的消息对签名者不可知的数字签名。从１９８３年 Ｄａｖｉｄ Ｃｈａｕｍ首先提出了盲签名的概念以来,许多实现方案相继推出。文章提出了基于离散对数问题的一般盲签名方案,对其完备性、不可伪造性、安全性以及盲性进行了分析,并给出了用该方案设计一个有效的盲签名协议应该满足的参数规则。     

Provably secure and pairing-free certificateless digital signature scheme using elliptic curve cryptography

A provably secure certificateless digital signature scheme using elliptic curve cryptography is presented in this paper. Since the certificateless public key cryptosystem removes the complex certificate management procedure and the private key escrow problem of traditional public key cryptography (PKC) and identity-based cryptosystem (IBC), respectively, and as a result, the proposed scheme is more efficient than IBC- and PKC-based signatures. Besides, the bilinear pairing and map-to-point hash function are time-consuming operations, and thus the signatures without these two operations are more attractive in real applications and the present work has been carried out in this direction. Based on the elliptic curve discrete logarithm assumption, it is shown that the proposed scheme is unforgeable under the adaptive chosen message and identity attacks in the random oracle model against variety of adversaries. Finally, our signature scheme is compared with a number of competitive schemes and the satisfactory performance has been achieved.     

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.     

ID-based digital signature scheme on the elliptic curve cryptosystem

The work presents a digital signature scheme on the elliptic curve cryptosystem, which is integrated with the identification scheme by Popescu [C. Popescu, An identification scheme based on the elliptic curve discrete logarithm problem, The 4th International Conference on High-Performance Computing in the Asia-Pacific Region, vol. 2 (2000) 624–625] using a one-way hash function. For making the trade-off of performance and security stand to benefit most, the proposed scheme is constructed on the elliptic curve cryptosystem. The scheme protects the signer from chosen-message attack and also identifies a forged signature.     

多个签名者强指定验证者签名方案

指定验证者签名可以实现签名者选择所期望的验证者验证签名的有效性,从而达到控制数字签名任意传播的目的,基于双线性对构造了一个新的基于身份的多签名者强指定验证者签名方案。新方案中多个签名者将隐藏的私钥以及进行哈希的消息发送给签名收集者,使得签名收集者无法利用签名者的私钥任意伪造签名,也不能对任意的消息进行签名,由签名收集者进行的多签名者强指定验证者签名方案缩短了签名时间和签名长度,并且减小了单个签名者权利过大的可能性。该签名体制可以用于多人联名上书的情况。新方案在BDH问题和DLP问题的困难性假设下,在基于身份的多签名者强指定验证者签名的不可伪造性和不可转发性概念下是安全的。     

对Wu-Wang盲签名方案的攻击与改进

分析了Wu-Wang提出的基于离散对数问题的盲签名方案的安全性,给出了一个攻击,即签名请求者仅执行一次方案可以同时得到两则不同消息的有效签名。针对该攻击提出一种改进方案,通过在签名阶段引入一个随机数来抵抗此种攻击,使得方案安全性能提高。     

新的代理多签名体制

首先对椭圆曲线数字签名算法(ECDSA)进行了改进，方法是避免其签名生成和签名验证过程中费时的求逆运算。然后在此改进的椭圆曲线数字签名算法基础上，设计了一个代理签名体制，该体制满足代理签名的所有安全要求。所谓代理签名体制是指原始签名人把自己的签名权利委托给代理签名人，然后代理签名人代表原始签名人产生代理签名的体制。允许代理签名人代表多个原始签名人产生代理签名的体制称为代理多签名体制，目前所提出的代理多签名体制都基于一般群上的离散对数问题。在此首次提出基于椭圆曲线离散对数问题的代理多签名体制，极大地提高了代理多签名生成和验证的效率并缩短了代理多签名的长度。     

对一个基于离散对数代理盲签名的密码分析

顾名思义,代理签名让原始签名者可以将其数字签名权力委托给代理签名者,使其能够代理原始签名者签发指定的数字消息;盲签名使用户能将给定的消息让别人签发,而又不泄漏任何有关的信息给签名者.在Schorr盲签名的基础上,谭作文等结合代理签名和盲签名提出了一个基于离散对数的代理盲签名方案.研究表明该方案是不安全的.它既受到广泛伪造攻击,又是可连接的.我们还进一步说明,原文安全性定理的证明是不正确的.     

具有消息恢复的指定接收者的盲签名方案

基于离散对数问题,提出了一个具有消息恢复的指定接收者的盲签名方案,并对方案的安全性和效率性进行了详细的分析讨论。方案不仅能满足消息恢复盲签名所要求的性质,而且只有指定的接收者才能验证签名的有效性,具有不可追踪性,即签名者无法将盲签名的行为与去盲后得到的真实文件签名联系起来。新方案实现了电子商务中的盲性和不可链接性且具有增强信息保密性的作用,其效率也优于已有方案。