On the Key Exposure Problem in Chameleon Hashes

Giuseppe Ateniese, Breno de Medeiros

TL;DR

This paper tackles the "key exposure problem" in chameleon signatures, a type of digital signature that offers non-transferability but can be compromised if a secret key is revealed. The authors propose new constructions for "key-exposure-free" chameleon hash functions, which are essential building blocks for secure chameleon signatures, based on standard cryptographic assumptions like RSA and the discrete logarithm problem.

What Problem Does This Paper Address?

Chameleon signatures, introduced by Krawczyk and Rabin, are designed to provide non-transferability. This means a signature given to one recipient cannot be easily used by that recipient to authenticate a message to a third party. The core idea is to use a "chameleon hash" function, which allows a signer to create a collision (two different messages hashing to the same value) if they know a secret "trapdoor." This trapdoor is typically given to the intended recipient.

However, the original construction of chameleon hashes suffered from a "key exposure problem." If the recipient's secret trapdoor key was exposed, an attacker could compute collisions for all signatures issued to that recipient's public key. This undermines the non-transferability and even the security of the system, as it invalidates all past signatures and makes future ones suspect. Previous work has addressed this by using identity-based schemes or constructions based on pairings (a more advanced cryptographic primitive), but the authors here aim to provide key-exposure-free solutions based on more common cryptographic assumptions and to explore more efficient schemes.

Methods

The paper introduces a formal security model for key-exposure-free chameleon hash functions, defining requirements like collision-resistance, semantic security (hiding the message content), and message hiding. They then present several constructions:

  • Key-Exposure Freeness Without Message Hiding: This section describes a scheme based on the discrete logarithm problem (specifically, a variant of the Nyberg-Rueppel signature scheme). It relies on a single trapdoor and is key-exposure free, but it doesn't hide the message content perfectly.
  • Key Exposure Freeness with Message Hiding: This section presents constructions that achieve both key-exposure freeness and message hiding.
  • RSA and Factoring: One scheme is based on the RSA cryptosystem and factoring, utilizing two trapdoors. This construction is shown to be secure under the assumption that breaking the RSA signature scheme is hard.
  • RSA[n,n] and Factoring: Another scheme uses a trapdoor permutation based on RSA and factoring, also relying on two trapdoors.
  • SDH and DL: A third scheme is based on the Strong Diffie-Hellman (SDH) assumption in gap-DDH groups, which is related to the discrete logarithm problem. This scheme also uses two trapdoors.

The paper also discusses how these constructions can be adapted for identity-based chameleon hashing, where a trusted third party manages keys for different users.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Double-Trapdoor Necessity: The paper argues that constructing key-exposure-free chameleon hashes that are also identity-based or message-hiding generally requires a "double-trapdoor" mechanism. This means there are two distinct secret keys or trapdoors involved in the system.
  • RSA for Key-Exposure Freeness: A significant contribution is showing that standard RSA-based schemes can be adapted to provide key-exposure-free chameleon hashes, without needing more complex primitives like pairings.
  • Single-Trapdoor Scheme: The construction that offers key-exposure freeness but not message hiding is notable for relying on only a single trapdoor, which is a novel result according to the authors.
  • Identity Customization: The paper highlights how "identity customization" can be used in identity-based chameleon hashing to mitigate key exposure risks by creating unique, transaction-specific identities.

Key Results

The paper provides three constructions of chameleon hash functions that satisfy the full security model (key-exposure freeness and message hiding), two based on RSA and one based on pairings. It also presents a single-trapdoor construction that is key-exposure free but not message hiding. These constructions significantly expand the set of available tools for building secure chameleon signature schemes.

Limitations and Future Work

The authors pose an open question: "Are there efficient schemes that are simultaneously identity-based and key-exposure free, perhaps based on a construction with multiple (more than two) consecutive trapdoors?" This suggests that while they've made progress, there might be more efficient or unified solutions to explore. They also note that their constructions are based on standard cryptographic assumptions, implying that their security is tied to the hardness of problems like factoring and discrete logarithms.

Summary updated

Abstract

Chameleon signatures were introduced by Krawczyk and Rabin, being non-interactive signature schemes that provide non-transferability. However, that first construction employs a chameleon hash that suffers from a key exposure problem: The non-transferability property requires willingness of the recipient in consequentially exposing a secret key, and therefore invalidating all signatures issued to the same recipient’s public key. To address this key-revocation issue, and its attending problems of key redistribution, storage of state information, and greater need for interaction, an identity-based scheme was proposed in [1], while a fully key-exposure free construction, based on the elliptic curves with pairings, appeared later in [7]. Herein we provide several constructions of exposure-free chameleon hash functions based on different cryptographic assumptions, such as the RSA and the discrete logarithm assumptions. One of the schemes is a novel construction that relies on a single trapdoor and therefore may potentially be realized over a large set of cryptographic groups (where the discrete logarithm is hard).
BibTeX
@article{ateniese2004key,
  author = {Giuseppe Ateniese and Breno de Medeiros},
  title = {{On the Key Exposure Problem in Chameleon Hashes}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2004},
}
Figure