Discrete logarithm based chameleon hashing and signatures without key exposure

Chameleon signatures simultaneously provide the properties of non-repudiation and non-transferability for the signed message. However, the initial constructions of chameleon signatures suffer from the key exposure problem of chameleon hashing. This creates a strong disincentive for the recipient to compute hash collisions, partially undermining the concept of non-transferability. Recently, some constructions of discrete logarithm based chameleon hashing and signatures without key exposure are presented, while in the setting of gap Diffie–Hellman groups with pairings.In this paper, we propose the first key-exposure free chameleon hash and signature scheme based on discrete logarithm systems, without using the gap Diffie–Hellman groups. This provides more flexible constructions of efficient key-exposure free chameleon hash and signature schemes. Moreover, one distinguishing advantage of the resulting chameleon signature scheme is that the property of “message hiding” or “message recovery” can be achieved freely by the signer, i.e., the signer can efficiently prove which message was the original one if he desires.     

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.     

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.     

Chameleon hash without key exposure based on Schnorr signature

Based on the famous Schnorr signature scheme, we propose a new chameleon hash scheme which enjoys all advantages of the previous schemes: collision-resistant, message-hiding, semantic security, and key-exposure-freeness.     

强不可伪造的在线/离线签名方案

针对标准模型下签名方案效率低的问题,利用目标抗碰撞杂凑函数和变色龙哈希函数,提出了一种在线/离线签名方案。在签名消息到来之前,离线阶段进行重签名的大部分计算,并将这些运算结果保存起来;在签名消息到来时,利用离线阶段保存的数据能在很短的时间内生成消息的在线重签名。在标准模型下,证明了新方案在适应性选择消息攻击下满足强不可伪造性。分析结果表明,新方案在效率上优于已有的标准模型下签名方案,在线签名算法仅需要1次模减法运算和1次模乘法运算,适合于计算能力较弱的低端计算设备。     

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

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

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.     

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

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

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.     

Sakai–Ohgishi–Kasahara identity-based non-interactive key exchange revisited and more

Identity-based non-interactive key exchange (IB-NIKE) is a powerful but a bit overlooked primitive in identity-based cryptography. While identity-based encryption and signature have been extensively investigated over the past three decades, IB-NIKE has remained largely unstudied. So far, there are only few IB-NIKE schemes in the literature. Among them, Sakai–Ohgishi–Kasahara (SOK) scheme is the first efficient and secure two-party IB-NIKE scheme, which has great influence on follow-up works. However, the SOK scheme required its identity mapping function to be modeled as a random oracle to prove security. Moreover, its existing security proof heavily relies on the ability of programming the random oracle. It is unknown whether such reliance is inherent. In this work, we intensively revisit the SOK IB-NIKE scheme and present a series of possible and impossible results in the random oracle model and the standard model. In the random oracle model, we first improve previous security analysis for the SOK IB-NIKE scheme by giving a tighter reduction. We then use meta-reduction technique to show that the SOK scheme is unlikely proven to be secure based on the computational bilinear Diffie–Hellman assumption without programming the random oracle. In the standard model, we show how to instantiate the random oracle in the SOK scheme with a concrete hash function from admissible hash functions (AHFs) and indistinguishability obfuscation. The resulting scheme is adaptively secure based on the decisional bilinear Diffie–Hellman inversion assumption. To the best of our knowledge, this is the first adaptively secure IB-NIKE scheme in the standard model that does not explicitly require multilinear maps. Previous schemes in the standard model either have merely selective security or require programmable hash functions from multilinear maps. At the technical heart of our scheme, we generalize the definition of AHFs and propose a generic construction which enables AHFs with previously unachieved parameters. This might be of independent interest. In addition, we present some new results about IB-NIKE. Firstly, we propose a generic construction of multiparty IB-NIKE from extractable witness PRFs and existentially unforgeable signatures. Secondly, we investigate the relation between semi-adaptive security and adaptive security of IB-NIKE. Somewhat surprisingly, we show that these two notions are polynomially equivalent.     

一种基于身份的不可传递性环签名

网络环境中的某些应用(如匿名电子举报)要求数字签名同时具备签名者身份模糊性和签名不可传递性,而现存的签名方案都不能完全满足此类需求.为此,提出了一种新的签名方案即基于身份的不可传递性环签名方案,设计了一个基于双线性对的特殊哈希函数,并将该哈希函数引入到环签名中,使方案很好地满足了上述需求.形式化分析表明,方案生成的签名在随机预言模型(Random Oracle Model,ROM)下具有不可伪造性.     

A pairing-free certificateless digital multisignature scheme using elliptic curve cryptography

In a digital multisignature scheme, two or more signers are allowed to produce a single signature on a common message, which can be verified by anyone. In the literature, many schemes are available based on the public key infrastructure or identity-based cryptosystem with bilinear pairing and map-to-point (MTP) hash function. The bilinear pairing and the MTP function are time-consuming operations and they need a large super-singular elliptic curve group. Moreover, the cryptosystems based on them are difficult to implement and less efficient for practical use. To the best of our knowledge, certificateless digital multisignature scheme without pairing and MTP hash function has not yet been devised and the same objective has been fulfilled in this paper. Furthermore, we formally prove the security of our scheme in the random oracle model under the assumption that ECDLP is hard.     

基于变色龙hash的区块链可扩展存储方案

区块链中的节点以副本形式保存数据,随着时间的推移,区块链中的区块数不断增加,导致节点承受的存储压力随之增大,存储压力成为区块链应用落地的瓶颈之一。为了解决区块链中存储压力问题,提出了基于变色龙hash的区块链可扩展存储方案,该方案利用节点被攻击成功的概率和改进的温度模型,将区块分为高低安全性的冷热区块;基于变色龙hash算法和改进的Merkle tree,对高安全性的冷区块进行部分节点存储。在存储过程中,除高安全性冷区块的区块体信息被重构外,其余数据保持不变。仿真实验表明,在不改变区块链结构和安全性能的情况下,所提出的方案可减少区块链中数据的存储总量,减少存储节点的存储压力;且区块数量越多,其优势越明显。     

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.     

基于身份不可授权的强指定验证者签名方案

针对目前基于身份的强指定验证者签名方案可授权及效率不高的问题,提出一种基于身份的强指定验证者签名方案。对基于双线性对的签名方案进行安全性证明以及效率分析。性能分析结果证明,与已有方案相比,该方案满足不可传递性、不可伪造性及不可授权性,双线性对运算和模乘运算相应减少,签名效率更高。     

Keyed hash function based on a chaotic map

Secure hash functions play a fundamental role in cryptographic and Web applications. They are mainly used, within digital signature schemes, to verify the integrity and authenticity of information. In this paper, we propose a simple and efficient keyed hash function based on a single chaotic map. Theoretical and simulation results demonstrate that the suggested scheme satisfies all cryptographic requirements of secure keyed hash functions such as strong confusion and diffusion capability, good collision resistance, high sensitivity to message and secret key, etc. Furthermore, it is fast and can be easily implemented through software or hardware. Moreover, the length of the hash value is flexible without any impact on the algorithm. This function is shown to have better statistical performance than many existing hash functions. Thus, the suggested hash function seems to be a good candidate as a secure keyed hash function for use in cryptographic applications.     

标准模型下可证安全的基于身份的高效签名方案

基于身份的公钥密码体制克服了传统公钥密码体制所带来的公钥证书存储和管理开销问题;目前大多数基于身份的数字签名方案的安全性足基于随机预言模型进行证明,但随机预言机的实现方式可能会导致方案的不安全,如Hash函数,往往返回的结果并小是随机的.文中提出一种安全、高效的基于身份的签名方案,并且在标准模型下证明该方案对自适应选择消息攻击是存在不可伪造的,方案的安全性可规约为CDH困难假定.与现有的标准模型下安全的基于身份的签名方案相比,方案的通信代价更小,执行效率更高.     

一种有效的无证书环签密方案

环签密是一个重要的密码学术语,它结合了加密和环签名的功能,具有保密性、可认证性和匿名性等安全属性。目前已有的无证书环签密方案大都是在随机预言模型下提出的,然而在该模型下可证安全的方案在哈希函数实例化后有时却并不安全。针对这一问题,设计了一个标准模型下可证安全的无证书环签密方案,并通过计算DiffieHellman(CDH)困难问题假设和判定性Diffie-Hellman(DBDH)困难问题假设,证明了方案满足适应性选择密文攻击下的不可区分性以及适应性选择消息攻击下存在的不可伪造性,因而方案是安全有效的。     

强前向安全的代理签名方案

前向安全代理签名方案无法保证代理者密钥泄漏后未来时段代理签名的安全性。基于单向散列链,对王天银等提出的前向安全代理签名方案进行了改进,使该方案的代理签名具有强前向安全性：即使代理密钥被泄露,攻击者也无法伪造过去和未来时段的代理签名,并且具有密钥泄露检测功能。     

Forward-secure identity-based signature with efficient revocation

The security of traditional identity-based signature (IBS) is totally built upon the assumption that the private key is absolutely secure. However, with the increasing use of mobile and unprotected devices in today's cryptosystems, the threat of key exposure represents a more serious and realistic concern. To mitigate the damage of key exposure in the setting of IBS, we propose to integrate key evolution and user revocation into IBS, and present forward-secure identity-based signature with user revocation (FS-RIBS). Specifically, we formalize the syntax and security definition of FS-RIBS, and give a concrete construction. The proposed scheme is proven secure in the standard model under a q-type complexity assumption. To demonstrate the merits of our scheme, we theoretically analyse its performance by comparing it with other related works. Moreover, we provide an implementation and the corresponding timing results of our scheme to show its practicability.