本体技术视点 | 什么是“变色龙哈希函数”？

#0.

引言

我们在本体技术视点 | 从密码学到区块链，你无法绕开的哈希函数中介绍了哈希函数这一重要的密码学原语，知道了哈希函数是一个确定性函数，可以将任意比特的输入变换成固定长度的输出。同时，我们还了解了密码学哈希函数相关的一些特性，比如正向计算有效性、逆向计算困难性、抗碰撞性和散列性等等。在采用哈希函数构造其它密码学方案时，有时候哈希函数会被抽象成随机预言机模型，并在此模型下证明构造的密码学方案具有相应的安全性质。

今天，我们聊一聊密码学哈希函数中一个有意思的特例，变色龙哈希函数。

图源网络

#1.

陷门函数

在了解变色龙哈希函数之前，我们先简单地介绍一个密码学概念：单向陷门函数。单向陷门函数 是指满足以下性质的函数：

a. 对于定义域 中的任意元素 ，可在多项式时间内计算得到 ；

b. 对于值域 中的任意元素 ，无法在多项式时间内计算得到 ；

c. 当知道某个信息 以后，对于值域 中的任意元素 ，都可以在多项式时间内计算得到 。

我们称信息 为这个单向陷门函数的陷门。简单地讲，当陷门信息未知时，单向门陷门函数等同于普通的单向函数：正向可有效计算，逆向则难以计算。当陷门信息已知时，单向陷门函数的逆运算便可高效实现。

#2.

变色龙哈希函数

我们知道，普通的密码学哈希函数具有抗碰撞性。即，给定某个哈希函数，找到其定义域中的两个不同元素 和 ，满足 ，这在计算上是不可行的。区块链难以篡改的安全特性来源之一就是哈希函数的抗碰撞性。而变色龙哈希可以在一定的情况下非常高效地找到碰撞。

哈希函数是一种单向函数，而变色龙哈希函数（Chameleon Hash Function）就是一种带陷门的哈希函数，该原语从 Chameleon Commitment 中引出，由 Krawczyk 和 Rabin 于1997年正式提出。简单来说，对于变色龙哈希函数，如果陷门信息已知，则可以高效地计算出任意输入数据的碰撞，即在不改变哈希函数输出的哈希值情况下，改变输入为任意值。如果陷门信息未知，那么变色龙哈希函数和普通的哈希函数一样具有上述的抗碰撞性。

图源网络

稍微形式化地定义变色龙哈希函数，一个变色龙函数由下面三个算法组成：

a. . 给定安全参数 ，密钥生成算法输出公钥 和陷门 。

b. . 给定公钥 ，待哈希的消息 和辅助随机数 ，哈希算法输出哈希值 。

c. . 给定陷门 ，消息 ，随机数 和另外一个消息 ，变色龙算法输出满足 的 ，并且 是在随机数空间均匀分布的。

在这里，我们省略了验证函数，当正确生成的哈希摘要参与验证时，将会通过验证。而不正确的哈希摘要则不能通过验证。

#3.

变色龙哈希函数的应用

我们知道，哈希函数一种重要应用是用作签名算法的前置函数。即一般签名生成遵循先哈希再签名的范例（Hash-and- Sign Paradigm）。我们假定签名算法是一个安全的数字签名算法，当用来计算消息摘要的哈希函数是变色龙哈希时，会形成一个变色龙签名算法。

图源网络

除了不可伪造性以外，变色龙签名具有比较有趣的性质。我们假定 Bob 掌握一个变色龙哈希算法 的陷门信息，而 Alice 签名的前置哈希算法就是该算法 。当 Alice 签名以后，Bob 如果拿着 Alice 的签名结果给第三方 Charlie 看，第三方必然不会相信这个签名结果，因为 Charlie 知道 Bob 拿有哈希算法的陷门信息，他可以任意更改被签名的消息。即，Bob 不能将 Alice 签名的合法性向第三方展示。这是变色龙签名的不可传递性（non-transferability）。另外，Alice 也由于没有陷门信息，不能找到哈希碰撞，从而不能否认其已经签过名，这就是不可抵赖性（non-repudiation）。

在区块链中，如果将区块链的哈希函数改用变色龙哈希函数，陷门信息由特定人掌握，则这些特定人就可以任意修改区块数据，而不会破坏链式结构的完整性。这给区块链带来了可编辑的特性。可以看到，掌握陷门信息的人掌握区块链信息的修改权。一般来说，如果此项技术用于联盟链，那么会有一个分布式随机数生成算法来使得多人共同拥有陷门信息。当然，可编辑区块链还可以通过其它技术来实现，比如采用多链平行结构等。

#4.

结语

变色龙哈希是一个比较有趣的密码学概念。它可以让拥有陷门信息的人轻易找到哈希函数的碰撞。除了形成指定验证者的签名方案以外，在区块链中，变色龙哈希可以用来做可编辑的区块链。埃森哲就采用了变色龙哈希来构造可编辑区块链。我们期待可以看到变色龙哈希的其它精彩应用。