Paper 2023/774

Tagged Chameleon Hash from Lattice and Application to Redactable Blockchain

Yiming Li
Shengli Liu, Shanghai Jiao Tong University

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.

Available format(s)
Public-key cryptography
Publication info
Tagged Chameleon HashLatticeRedactable blockchain
Contact author(s)
lym_sjtu @ sjtu edu cn
slliu @ sjtu edu cn
2023-05-30: approved
2023-05-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yiming Li and Shengli Liu},
      title = {Tagged Chameleon Hash from Lattice and Application to Redactable Blockchain},
      howpublished = {Cryptology ePrint Archive, Paper 2023/774},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.