ASIA CCS '24: Proceedings of the 19th ACM Asia Conference on Computer and Communications Security Pages 1066 - 1081 https://doi.org/10.1145/3634737.3656291 ABSTRACT Chameleon hash (CH) function differs from a classical hash function in a way that a collision can be found with the knowledge of a trapdoor secret key. CH schemes have been used in various cryptographic applications such as sanitizable signatures and redactable blockchains. In this work, we reconstruct CH to ensure advanced security and usability. Our contributions are four-fold. First, we propose the first CH scheme, which supports full security, meaning the inclusion of both full indistinguishability and full collision-resistance. These two properties are required in the strongest CH security model in the literature. We achieve this by our innovative design of removing the CH public key during the computation of the hash value. Second, we investigate the security of CH in the multi-party setting and introduce the new properties of claimability and deniability under this setting. Third, we present and implement two instantiations of our CH scheme: an ECC-based one and a post-quantum lattice-based one. Our implementation demonstrates their practicality. Finally, we discuss the possible use cases in the blockchain. AUTHORS Kwan Yin Chan kychan@cs.hku.hk The University of Hong Kong Pokfulam, Hong Kong Liqun Chen liqun.chen@surrey.ac.uk University of Surrey Guildford, United Kingdom Yangguang Tian yangguang.tian@surrey.ac.uk University of Surrey Guildford, United Kingdom Tsz Hon Yuen∗ john.tszhonyuen@monash.edu Monash University Clayton, Australia