Tagged Chameleon Hash from Lattices and Application to Redactable Blockchain

基于格的标签变色龙哈希函数及其在可修改区块链的应用

Yiming Li, Shengli Liu*

研究目标

变色龙哈希函数(Chameleon Hash， 简称作 CH) 可以看作带陷门的抗碰撞哈希函数，使用陷门可以高效地产生一对哈希碰撞。近年来，变色龙哈希函数的一个重要应用方向是可修改区块链，利用它可以实现删除、修改区块链上的信息，用于处理区块链中存在可被攻击者利用的漏洞或是存在一些违法的信息。目前已知的具有完全抗碰撞性的变色龙哈希函数都是通用构造，需要使用复杂的密码原语，如具有证据提取性质的NIZK。这些CH通用构造的实例化方案或者依赖于离散对数家族困难问题，无法抵抗量子攻击；或者需要使用(量子)随机预言机，只能在(量子)随机预言机模型下证明安全。因此，我们的研究目标为：如何在标准模型下构造满足可修改区块链应用需求的后量子变色龙哈希函数，且避免使用非交互零知识证明系统这一复杂密码原语?

关键问题

由于变色龙哈希的主要应用是在可修改区块链上，如何针对可修改区块链这一具体应用场景来定义变色龙哈希的安全性质，是我们需要解决的关键问题。

研究内容

我们对以下内容进行研究

  1. 提出新型的、满足可修改区块链场景的变色龙哈希函数的安全定义。

  2. 基于后量子假设，设计出满足上述安全定义的变色龙哈希函数的高效实例化。

  3. 设计出应用变色龙哈希函数将传统区块链改造为可修改区块链的方法。

技术路线

我们首先根据可修改区块链这一具体场景，发现变色龙哈希的完全抗 碰撞性并不是必要条件。也就是说，我们可以借助区块链的性质(或一些简单改动)来降低其对于变色龙哈希抗碰撞性的需求，从而降低满足应用需求的变色龙哈希的构造难度。结合上述的发现，我们提出了新的密码原语：带标签的变色龙哈希函数（简写为tCH），并给出了的语义描述及其正确性、统计不可区分性、抗碰撞性和完全抗碰撞性定义，并证明当tCH工作在一次标签模式时，其抗碰撞性等价于完全抗碰撞性。之后，我们基于格上的SIS假设，构造出了具有抗碰撞性的、带标签的变色龙哈希函数(tCH)方案。最终，我们介绍如何使用带标签的变色龙哈希函数(tCH)将传统区块链改造为安全的可修改区块链，并分析了可修改区块链构造的安全性。

7. 带标签的变色龙哈希函数

研究意义

我们给出了新的密码学原语：带标签的变色龙哈希函数(tCH)，并给出了适用于可修改区块链的安全定义。我们给出了更加高效的、具有后量子安全的tCH方案的构造，并在标准模型下证明了我们方案的安全性。最后，我们借助工作在一次标签模式的具有抗碰撞性的tCH 组件，将传统区块链改造成为安全的可修改区块链。特别地，我们提出的标准模型下具有抗碰撞性的tCH方案 也是首个满足可修改区块链安全需求的、标准模型下的、后量子变色龙哈希函数。