International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Bringing Order to Chaos: The Case of Collision-Resistant Chameleon-Hashes

Authors:
David Derler
Kai Samelin
Daniel Slamanig
Download:
DOI: 10.1007/s00145-024-09510-9
Search ePrint
Search Google
Abstract: AbstractChameleon-hash functions, introduced by Krawczyk and Rabin (NDSS’00), are trapdoor collision-resistant hash functions parametrized by a public key. If the corresponding secret key is known, arbitrary collisions for the hash function can be found efficiently. Chameleon-hash functions have prominent applications in the design of cryptographic primitives, such as lifting non-adaptively secure signatures to adaptively secure ones. Recently, this primitive also received a lot of attention as a building block in more complex cryptographic applications, ranging from editable blockchains to advanced signature and encryption schemes. We observe that, in latter applications, various different notions of collision-resistance are used, and it is not always clear if the respective notion really covers what seems intuitively required by the application. Therefore, we revisit existing collision-resistance notions in the literature, study their relations, and by means of selected applications discuss which practical impact different notions of collision-resistance might have. Moreover, we provide a stronger, and arguably more desirable, notion of collision-resistance than what is known from the literature (which we call full collision-resistance). Finally, we present a surprisingly simple, and efficient, black-box construction of chameleon-hash functions achieving this strong notion of full collision-resistance.
BibTeX
@article{jofc-2024-34425,
  title={Bringing Order to Chaos: The Case of Collision-Resistant Chameleon-Hashes},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={37},
  pages={29},
  doi={10.1007/s00145-024-09510-9},
  author={David Derler and Kai Samelin and Daniel Slamanig},
  year=2024
}