Practical Generic Construction of Fully Collision Resistant Chameleon Hash and Instantiations

A chameleon hash (CH) function is a trapdoor hash defined over a public hash key and a related secret trapdoor key. With the trapdoor, it is possible to find collisions between two different messages sharing the same hash value, while without it, the function acts like a normal hash that is collision-resistant. Full collision resistance (F-CollRes) is the strongest known definition of collision resistance, which can provide a high level of security assurance, even after collisions are publicly known. Existing constructions that satisfy this strong notion use non-interactive zero-knowledge (NIZK) proofs for AND or OR relations as underlying building blocks.
In this paper, we present a novel generic construction for F-CollRes CHs which only requires NIZKs for single relations, without involving relatively complex AND or OR relations. The core of our approach is to require the underlying CH, which only satisfies a weaker collision resistance, to possess a property named preimage computability, which is easily achievable in certain mathematical structures like RSA and lattices.
Furthermore, we provide two concrete instantiations for our generic construction in the random oracle model, based on RSA and lattices. This further demonstrates the practicality and conceptual simplicity of our generic method.