Efficient chameleon hash functions in the enhanced collision resistant model
Chameleon hash functions are collision resistant when only the hashing keys of the functions are known. In particular, without the knowledge of the secret information, the chameleon hash function is merely like a regular cryptographic hash function, where it is hard to find collisions. However anyone who has trapdoor keys can efficiently generate pre-images for the chameleon hash function. In some applications, such as redactable blockchains, unfortunately the existing properties do not suffice and we need more features. Actually, it is required that without knowing the trapdoor keys, nobody can compute collisions, even if he can see collisions for arbitrary hash functions. In 2017, Ateniese et al. introduced the notion of chameleon hash functions in the enhanced collision resistant model and proposed a construction in the standard model satifying the features. To date, efficient constructions of this kind of chameleon hash functions remain as an open research problem. In this paper, we answer this problem affirmatively by presenting efficient constructions of the chameleon hash function satisfying the enhanced collision resistance. The contributions of this work are twofold. First, we show the weakness of previous work. Then, we proceed with proposing new schemes with more efficiency. Technically, we present a new chameleon hash function in the basic model and based on simple assumptions. This chameleon hash function is well compatible with Groth-Sahai proof systems and the Cramer-Shoup encryption schemes, and can be used as a stepping stone to construct an efficient chameleon hash function in the enhanced collision resistant model. Moreover, we show our basic chameleon hash can be combined with optimal ZK-SNARKs of Groth and Maller that leads to shorter sizes for chameleon hash function in the enhanced collision resistant model.