Registered Policy-Based Chameleon Hash for Practical and Secure Blockchain Rewriting

Abstract

Redactable blockchains support legitimate on-chain data modifications for regulatory compliance and controlled data management. Existing constructions often rely on a trusted central authority (CA), introducing a key escrow problem and a single point of failure. Decentralized extensions mitigate these issues by distributing the role of the CA among multiple parties, but they incur two major drawbacks: 1) the authorization of rewriting privileges requires a modifier to interact with multiple authorities, bringing substantial communication costs; and 2) the existing decentralized schemes only guarantee security under a weak static model, which requires the adversary to commit all queries in advance and fails to capture realistic adversarial behaviors. In this paper, we propose a new redactable blockchain design that minimizes communication cost, eliminates key escrow, and provides stronger security guarantees. Our solution retains a centralized architecture to significantly reduce the communication cost compared to decentralized designs. Moreover, the CA does not possess or issue secret keys to the modifiers for performing rewriting operations, thereby eliminating the key escrow problem. To enable a generic design with rigorous security analysis, we introduce a cryptographic primitive, registered policy-based chameleon hash (RPCH), and formalize three security models that capture realistic adversarial capabilities. We propose a generic construction of RPCH accompanied by formal security proofs. Based on this framework, we present two concrete instantiations. The first is optimized for efficiency, leveraging a prime-order group and achieving selective security. The second prioritizes security guarantees by attaining adaptive security in a composite-order setting. To evaluate performance, we implement and compare our construction against both the classic PCH-based scheme and the state-of-the-art decentralized variant. Extensive experiments demonstrate that our approach achieves a strong balance between security and efficiency, and is particularly well-suited for redactable blockchain applications where only a small fraction of users are authorized to perform modifications.