International Association
for Cryptologic Research

Chameleon hash (CH) is a trapdoor hash function. Generally it is hard to find collisions, but with the help of trapdoor, finding collisions becomes easy. CH plays an important role in converting a conventional blockchain to a redactable one. However, most of the existing CH schemes are too weak to support redactable blockchain. The currently known CH schemes serving for redactable blockchain have the best security of so-called “full collision resistance (f-CR)”, but they are built either on random oracle model or rely on heavy tools like the simulation-sound extractable non-interactive zero-knowledge (SSE-NIZK) proof system. Moreover, up to now there is no CH scheme with post-quantum f-CR security in the standard model. Therefore, no CH can support redactable blockchain in a post-quantum way without relying on random oracles.

In this paper, we introduce a variant of CH, namely tagged chameleon hash (tCH). Tagged chameleon hash takes a tag into hash evaluations and collision finding algorithms. We define two security notions for tCH, collision resistance (CR) and full collision resistance (f-CR), and prove the equivalence between CR and f-CR when tCH works in the one-time tag mode. We propose a tCH scheme from lattice without using any NIZK proof, and prove that its collision resistance is (almost) tightly reduced to the Short Integer Solution (SIS) assumption in the standard model. We also show how to apply tCH to a blockchain in one-time tag mode so that the blockchain can be compiled to a redactable one. Our tCH scheme provides the first post-quantum solution for redactable blockchains, without resorting to random oracles or NIZK proofs. Besides, we also construct a more efficient tCH scheme with CR tightly reduced to SIS in the random oracle model, which may be of independent interest.