Paper 2020/403

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

David Derler, DFINITY
Kai Samelin
Daniel Slamanig, Research Institute CODE, Universität der Bundeswehr München
Abstract

Chameleon-hash functions, introduced by Krawczyk and Rabin at NDSS 2000, 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 efficiently found. 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 does really cover what seems intuitively required by the application. Therefore, we revisit existing collision-resistance notions in the literature, study their relations, and - using the example of the recent redactable blockchain proposals - 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. Finally, we present a surprisingly simple and efficient black-box construction of chameleon-hash functions achieving this strong notion.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in JOC 2024
DOI
https://doi.org/10.1007/s00145-024-09510-9
Keywords
Chameleon-hash
Contact author(s)
david @ dfinity org
kaispapers @ gmail com
daniel slamanig @ unibw de
History
2024-07-08: revised
2020-04-13: received
See all versions
Short URL
https://ia.cr/2020/403
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/403,
      author = {David Derler and Kai Samelin and Daniel Slamanig},
      title = {Bringing Order to Chaos: The Case of Collision-Resistant Chameleon-Hashes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/403},
      year = {2020},
      doi = {https://doi.org/10.1007/s00145-024-09510-9},
      url = {https://eprint.iacr.org/2020/403}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.