Fully Collision-Resistant Chameleon-Hashes from Simpler and Post-Quantum Assumptions

David Derler; Stephan Krenn; Kai Samelin; Daniel Slamanig

Paper 2020/1084

Fully Collision-Resistant Chameleon-Hashes from Simpler and Post-Quantum Assumptions

David Derler, Stephan Krenn, Kai Samelin, and Daniel Slamanig

Abstract

Chameleon-hashes are collision-resistant hash-functions parametrized by a public key. If the corresponding secret key is known, arbitrary collisions for the hash can be found. Recently, Derler et al. (PKC '20) introduced the notion of fully collision-resistant chameleon-hashes. Full collision-resistance requires the intractability of finding collisions, even with full-adaptive access to a collision-finding oracle. Their construction combines simulation-sound extractable (SSE) NIZKs with perfectly correct IND-CPA secure public-key encryption (PKE) schemes. We show that, instead of perfectly correct PKE, non-interactive commitment schemes are sufficient. For the first time, this gives rise to efficient instantiations from plausible post-quantum assumptions and thus candidates of chameleon-hashes with strong collision-resistance guarantees and long-term security guarantees. On the more theoretical side, our results relax the requirement to not being dependent on public-key encryption.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Major revision. SCN 2020
DOI: 10.1007/978-3-030-57990-6_21
Keywords: Chameleon-hash
Contact author(s): david @ dfinity org
stephan krenn @ ait ac at
kaispapers @ gmail com
daniel slamanig @ ait ac at
History: 2020-09-10: received
Short URL: https://ia.cr/2020/1084
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1084,
      author = {David Derler and Stephan Krenn and Kai Samelin and Daniel Slamanig},
      title = {Fully Collision-Resistant Chameleon-Hashes from Simpler and Post-Quantum Assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1084},
      year = {2020},
      doi = {10.1007/978-3-030-57990-6_21},
      url = {https://eprint.iacr.org/2020/1084}
}