#0.
引言
我们在本体技术视点
从密码学到区块链，你无法绕开的哈希函数中介绍了哈希函数这一重要的密码学原语，知道了哈希函数是一个确定性函数，可以将任意比特的输入变换成固定长度的输出。同时，我们还了解了密码学哈希函数相关的一些特性，比如正向计算有效性、逆向计算困难性、抗碰撞性和散列性等等。在采用哈希函数构造其它密码学方案时，有时候哈希函数会被抽象成随机预言机模型，并在此模型下证明构造的密码学方案具有相应的安全性质。
今天，我们聊一聊密码学哈希函数中一个有意思的特例，变色龙哈希函数。
图源网络
#1.
陷门函数
在了解变色龙哈希函数之前，我们先简单地介绍一个密码学概念：单向陷门函数。单向陷门函数是指满足以下性质的函数：
a.对于定义域
中的任意元素
，可在多项式时间内计算得到
；
b.对于值域
中的任意元素
，无法在多项式时间内计算得到
；
c.当知道某个信息
以后，对于值域
中的任意元素
，都可以在多项式时间内计算得到
。
我们称信息
为这个单向陷门函数的陷门。简单地讲，当陷门信息未知时，单向门陷门函数等同于普通的单向函数：正向可有效计算，逆向则难以计算。当陷门信息已知时，单向陷门函数的逆运算便可高效实现。
#2.
变色龙哈希函数
我们知道，普通的密码学哈希函数具有抗碰撞性。即，给定某个哈希函数，找到其定义域中的两个不同元素
和
，满足
，这在计算上是不可行的。区块链难以篡改的安全特性来源之一就是哈希函数的抗碰撞性。而变色龙哈希可以在一定的情况下非常高效地找到碰撞。
哈希函数是一种单向函数，而变色龙哈希函数（ChameleonHashFunction）就是一种带陷门的哈希函数，该原语从ChameleonCommitment中引出，由Krawczyk和Rabin于年正式提出。简单来说，对于变色龙哈希函数，如果陷门信息已知，则可以高效地计算出任意输入数据的碰撞，即在不改变哈希函数输出的哈希值情况下，改变输入为任意值。如果陷门信息未知，那么变色龙哈希函数和普通的哈希函数一样具有上述的抗碰撞性。
图源网络
稍微形式化地定义变色龙哈希函数，一个变色龙函数由下面三个算法组成：
a.
.给定安全参数
，密钥生成算法输出公钥
和陷门
。
b.
.给定公钥
，待哈希的消息
和辅助随机数
，哈希算法输出哈希值
。
c.
.给定陷门
，消息
，随机数
和另外一个消息
，变色龙算法输出满足
的
，并且
是在随机数空间均匀分布的。
在这里，我们省略了验证函数，当正确生成的哈希摘要参与验证时，将会通过验证。而不正确的哈希摘要则不能通过验证。
#3.
变色龙哈希函数的应用
我们知道，哈希函数一种重要应用是用作签名算法的前置函数。即一般签名生成遵循先哈希再签名的范例（Hash-and-SignParadigm）。我们假定签名算法是一个安全的数字签名算法，当用来计算消息摘要的哈希函数是变色龙哈希时，会形成一个变色龙签名算法。
图源网络
除了不可伪造性以外，变色龙签名具有比较有趣的性质。我们假定Bob掌握一个变色龙哈希算法
的陷门信息，而Alice签名的前置哈希算法就是该算法
。当Alice签名以后，Bob如果拿着Alice的签名结果给第三方Charlie看，第三方必然不会相信这个签名结果，因为Charlie知道Bob拿有哈希算法的陷门信息，他可以任意更改被签名的消息。即，Bob不能将Alice签名的合法性向第三方展示。这是变色龙签名的不可传递性（non-transferability）。另外，Alice也由于没有陷门信息，不能找到哈希碰撞，从而不能否认其已经签过名，这就是不可抵赖性（non-repudiation）。
在区块链中，如果将区块链的哈希函数改用变色龙哈希函数，陷门信息由特定人掌握，则这些特定人就可以任意修改区块数据，而不会破坏链式结构的完整性。这给区块链带来了可编辑的特性。可以看到，掌握陷门信息的人掌握区块链信息的修改权。一般来说，如果此项技术用于联盟链，那么会有一个分布式随机数生成算法来使得多人共同拥有陷门信息。当然，可编辑区块链还可以通过其它技术来实现，比如采用多链平行结构等。
#4.
结语
变色龙哈希是一个比较有趣的密码学概念。它可以让拥有陷门信息的人轻易找到哈希函数的碰撞。除了形成指定验证者的签名方案以外，在区块链中，变色龙哈希可以用来做可编辑的区块链。埃森哲就采用了变色龙哈希来构造可编辑区块链。我们期待可以看到变色龙哈希的其它精彩应用。互动时间
以下哪个选项说法正确？
A.当陷门信息未知时，单向门陷门函数等同于普通的单向函数：逆向可有效计算，正向则难以计算。
B.对于变色龙哈希函数，如果陷门信息已知，则可以高效地计算出任意输入数据的碰撞。
C.哈希函数一种重要应用是用作签名算法的前置函数。即一般签名生成遵循先签名再哈希的范例。
D.如果将区块链的哈希函数改用变色龙哈希函数，陷门信息由特定人掌握，这些特定人修改区块数据会破坏链式结构的完整性。
请将正确答案私信后台，前5名答对的小伙伴将每人获得一件哦~
如有任何问题，可通过research
ont.io联络我们。添加“ontology_”并备注可进行技术探讨或加入社群。
?点击阅读原文查看往期精彩
预览时标签不可点收录于话题#个上一篇下一篇