Elsevier

Information Sciences

Volume 265, 1 May 2014, Pages 198-210
Information Sciences

Identity-based chameleon hashing and signatures without key exposure

https://doi.org/10.1016/j.ins.2013.12.020Get rights and content

Abstract

The notion of chameleon hash function without key exposure plays an important role in designing secure chameleon signatures. However, all of the existing key-exposure free chameleon hash schemes are presented in the setting of certificate-based systems. In 2004, Ateniese and de Medeiros questioned whether there is an efficient construction for identity-based chameleon hashing without key exposure.

In this paper, we propose the first identity-based chameleon hash scheme without key exposure based on the three-trapdoor mechanism, which provides an affirmative answer to the open problem. Moreover, we use the proposed chameleon hash scheme to design an identity-based chameleon signature scheme, which achieves all the desired security properties.

Introduction

Chameleon signatures, introduced by Krawczyk and Rabin [32], are based on well established hash-and-sign paradigm, where a chameleon hash function is used to compute the cryptographic message digest. A chameleon hash function is a trapdoor one-way hash function, which prevents everyone except the holder of the trapdoor information from computing the collisions for a randomly given input. Chameleon signatures simultaneously provide the properties of non-repudiation and non-transferability for the signed message as undeniable signatures [12] do, but the former allows for simpler and more efficient realization than the latter. In particular, chameleon signatures are non-interactive and less complicated. More precisely, the signer can generate the chameleon signature without interacting with the designated recipient, and the recipient will be able to verify the signature without the collaboration of the signer. On the other hand, if presented with a forged signature, the signer can deny its validity by only revealing certain values. That is, the forged-signature denial protocol is also non-interactive. Besides, since the chameleon signatures are based on well established hash-and-sign paradigm, it provides more generic and flexible constructions.

One limitation of the original chameleon signature schemes [32] is that signature forgery (i.e., collision computation) results in the signer recovering the recipient’s trapdoor information, i.e., the private key. This is named as the key exposure problem of chameleon hashing, firstly addressed by Ateniese and de Medeiros [1] in 2004. To illustrate this, we take the chameleon signature scheme employed for the Chaum–Pedersen trapdoor commitment as the chameleon hash function for example. More precisely, a potential recipient chooses and publishes a regular discrete logarithm-based public key y=gx, where g is the generator of a cyclic group G and x is the secret key. Later, a signer with the message m to be signed can compute the chameleon hash value h=gmyr, where r is an auxiliary integer chosen uniformly at random by the signer. Trivially, if the value of m is larger than the order of the group G, we could first hash the message using a cryptographic hash function such as SHA-1. Then the signer can compute the signature σ=SIGN(h), here SIGN is any provable secure signature scheme. Given the triple (m,r,σ), the recipient can verify the validity of the signature. However, any third party could not be convinced of the fact since the recipient is capable of providing any new collision (m,r) such that h=gmyr. Moreover, if the recipient provides the original pair (m,r), the signer cannot repudiate his signature because he cannot compute a new collision under the assumption of discrete logarithm in G is intractable. Therefore, the chameleon signature scheme satisfies the properties of non-repudiation and non-transferability. On the other hand, with the two pairs (m,r) and (m,r), the signer can recover the secret key x of the recipient from the equation h=gmyr=gmyr, giving x=(m-m)(r-r)-1. This is a highly undesirable outcome from the recipient’s viewpoint. If the signer knows the recipient’s trapdoor information, he then can use it to deny other signatures given to the recipient. In the worst case, the signer could collaborate with other individuals to invalidate any signatures which were designated to be verified by the same public key. This will create a strong disincentive for the recipient to compute the hash collisions. Therefore, a third party is more likely to believe claims made by the recipient about presenting an original (non-forged) signature and thus the property of non-transferability of chameleon signature scheme is weakened.

Ateniese and de Medeiros [1] firstly introduced the idea of identity-based chameleon hashing to solve this problem. Due to the distinguishing property of identity-based systems [41], the signer can sign a message to an intended recipient, without having to first retrieve the recipient’s certificate. Moreover, the signer uses a different public key (corresponding to a different private key) for each transaction with a recipient, so that signature forgery only results in the signer recovering the trapdoor information associated to a single transaction. Therefore, the signer will not be capable of denying signatures on any message in other transactions. However, this kind of transaction-specific chameleon hash scheme still suffers from the key exposure problem unless an identity is never reused in the different chameleon signatures, which requires that the public/secret key pair of the recipient must be changed for each transaction. We argue that this idea only provides a partial solution for the key exposure problem of chameleon hashing.1

Chen et al. [17] proposed the first full construction of a key-exposure free chameleon hash function in the gap Diffie–Hellman (GDH) groups with bilinear pairings. Ateniese and de Medeiros [2] then presented three key-exposure free chameleon hash functions, two based on the RSA assumption, as well as a new construction based on bilinear pairings. Gao et al. [21] proposed a factoring-based chameleon hash scheme without key exposure. However, Chen et al. [20] presented some security flaws of the scheme and proposed an improved chameleon hash scheme without key exposure based on factoring. Recently, Gao et al. [22] also claimed to present a key-exposure free chameleon hash scheme based on the Schnorr signature. Nevertheless, it requires an interactive protocol between the signer and the recipient and thus violates the basic definition of chameleon hashing and signatures. Besides, Chen et al. [18] propose the first discrete logarithm based key-exposure free chameleon hash scheme without using the GDH groups. However, we argue that all of the above constructions are presented in the setting of certificate-based systems where the public key infrastructure (PKI) is required.

Identity-based systems [41] can be an alternative for certificate-based public key systems in some occasions, especially when efficient key management and moderate security are required. Ateniese and de Medeiros [1] proposed the first identity-based chameleon hashing and used it to design a sealed-bid auction scheme. Zhang et al. [42] presented two identity-based chameleon hash schemes from bilinear pairings. However, none of them is key-exposure free. As pointed out by Ateniese and de Medeiros, the single-trapdoor commitment schemes are not sufficient for the construction of key-exposure free chameleon hashing and the double-trapdoor mechanism [26] can be used to construct either an identity-based chameleon hash scheme or a key-exposure free one, but not both. Therefore, an interesting open problem is whether there is an efficient construction for identity-based chameleon hashing without key exposure [2].

Our Contribution. In this paper, we propose the first construction for identity-based chameleon hashing without key exposure, which provides an affirmative answer to the open problem introduced by Ateniese and de Medeiros in 2004. Moreover, the proposed chameleon hash scheme is proved to achieve all the desired security notions in the random oracle model. We then use the proposed chameleon hash scheme to design an identity-based chameleon signature scheme without key exposure.

Digital signature is arguably one of the most significant applications of public key cryptography. The ordinary digital signatures can be verified by any intended recipient with the signer’s public key, i.e., universal verifiability. However, it may be undesirable in many business situations that a signature can be verified universally. In the past two decades, there are plenty of researches on the conflict between authenticity and privacy in the digital signatures. The notion of undeniable signatures, introduced by Chaum and van Antwerpen [12], is such a kind of digital signature which enables the signer to decide when his/her signature can be verified. An extended notion is designated confirmer signatures [11], where a designated confirmer, instead of the signer, can be involved in the verification of the signature when the signer is inconvenient to cooperate. In some applications, it is also important for the signer to decide not only when but also by whom her signature can be verified. This is the motivation of the concept of designated verifier signatures [28]. The designated verifier will trust the signer indeed signed a message with a proof of the signer. However, he cannot present the proof to convince any third party because he is fully capable of generating the same proof by himself (non-transferability). Obviously, the two-party ring signatures [38] can provide an alternative solution for designated verifier signatures. However, we argue that the designated verifier signatures (and two-party ring signatures) do not satisfy the property of non-repudiation, which is different from undeniable signatures and chameleon signatures. Steinfeld et al. [40] introduced an extended notion named universal designated verifier signatures. Universal designated verifier signatures allow any holder of the signature (not necessarily the signer) to designate the signature to any desired designated verifier. Similarly, the verifier can be convinced that the signer indeed generated the signature, but cannot transfer the proof to convince any third party.

After initial work of Chaum and van Antwerpen [12], plenty of constructions [3], [10], [11], [14], [16], [23], [24], [25], [28], [30], [31], [35] for undeniable signatures based on various assumptions have been proposed. Libert and Quisquater [33] proposed the first provable secure undeniable signatures in the identity-based setting. Trivially, identity-based chameleon signatures could provide more alternative solutions for identity-based undeniable signatures. Unfortunately, both of the constructions for identity-based chameleon signatures [1], [42] suffer from the problem of key exposure. Ateniese and de Medeiros [2] thus questioned whether there is an efficient construction for identity-based chameleon hashing without key exposure in 2004.

The rest of the paper is organized as follows: Some preliminaries are given in Section 2. The definitions associated with identity-based chameleon hashing are introduced in Section 3. The proposed identity-based key-exposure free chameleon hash scheme and its security analysis are given in Section 4. The resulting identity-based chameleon signature scheme is given in Section 5. Finally, conclusions will be made in Section 6.

Section snippets

Preliminaries

In this section, we first introduce the basic definition and properties of bilinear pairings and some well-known number-theoretic problems in the gap Diffie–Hellman groups. We then present some proof systems for knowledge of discrete logarithms.

Definitions

In this section, we introduce the formal definitions and security requirements of identity-based chameleon hashing [1], [2].

Identity-based key-exposure free chameleon hashing

All of the existing identity-based chameleon hash schemes [1], [42] are based on the double-trapdoor mechanism and suffer from the key exposure problem. In more detail, there are two trapdoors in these chameleon hash schemes: One is the master key x of PKG, and the other is the secret key SID of the user with identity information ID (In identity-based systems, SID is actually a signature of PKG on message ID with the secret key x). Given a collision of the chameleon hash function, the trapdoor

Identity-based chameleon signature scheme

Chameleon signatures are based on well established hash-and-sign paradigm, and thus we can construct an identity-based chameleon signature scheme without key exposure by incorporating the proposed identity-based chameleon hash scheme Hash and any provable secure identity-based signature scheme SIGN against existential forgery on adaptively chosen message and ID attacks such as [9], [27]. There are two users, a signer S and a recipient R, in the identity-based chameleon signature scheme. When

Conclusions

Chameleon signatures simultaneously provide the properties of non-repudiation and non-transferability for the signed message, thus can be used to solve the conflict between authenticity and privacy in the digital signatures. However, the original constructions suffer from the so-called key exposure problem of chameleon hashing. Recently, some constructions of key-exposure free chameleon hash schemes [2], [17] are presented using the idea of “Customized Identities” while in the setting of

Acknowledgements

We are grateful to the anonymous referees for their invaluable suggestions. This work is supported by the National Natural Science Foundation of China (Nos. 61272455 and 61100224), China 111 Project (No. B08038), the Fundamental Research Funds for the Central Universities (Nos. K50511010001 and JY10000901034), and ARC Future Fellowship (FT0991397).

References (42)

  • X. Chen et al.

    Discrete logarithm based chameleon hashing and signatures without key exposure

    Comput. Electr. Eng.

    (2011)
  • W. Gao et al.

    Chameleon hash without key exposure based on Schnorr signature

    Comput. Stand. Interf.

    (2009)
  • G. Ateniese et al.

    Identity-based chameleon hash and applications

  • G. Ateniese et al.

    On the key exposure problem in chameleon hashes

  • D. Boyar et al.

    Convertible undeniable signatures

  • P. Barreto et al.

    Efficient algorithms for pairing-based cryptosystems

  • D. Boneh et al.

    Short signatures from the Weil pairings

  • D. Boneh et al.

    Identity-based encryption from the Weil pairing

  • M. Bellare et al.

    The exact security of digital signatures-How to sign with RSA and Rabin

  • J. Baek et al.

    Identity-based threshold decryption

  • J. Cha et al.

    An identity-based signature from gap Diffie–Hellman groups

  • D. Chaum

    Zero-knowledge undeniable signatures

  • D. Chaum

    Designated confirmer signatures

  • D. Chaum et al.

    Undeniable signatures

  • J. Coron

    On the exact security of full domain hash

  • D. Chaum et al.

    Cryptographically strong undeniable signatures, unconditionally secure for the signer

  • D. Chaum et al.

    Wallet databases with observers

  • J. Camenisch et al.

    Confirmer signature schemes secure against adaptive adversaries

  • X. Chen et al.

    Chameleon hashing without key exposure

  • X. Chen et al.

    Identity-based chameleon hash scheme without key exposure

  • X. Chen et al.

    Comments and improvements on key-exposure free chameleon hashing based on factoring

  • Cited by (0)

    An extended abstract of this paper has been presented at the 15th Australasian Conference on Information Security and Privacy (ACISP), LNCS 6168, Springer, pp. 200–215, 2010 [19].

    View full text