变色龙哈希调研
1. 调研背景
1.1哈希函数定义
哈希函数是一类具有以下特征的函数：将任意长度输入的字串可转换成一个固定长度的字串，通过原始字串可以很容易地算出转换后的字串，通过转换后的字串很难还原出原始字串。
1.2哈希函数特征
抗弱碰撞性：对于消息x，找到y≠x且H(x)=H(y)的y在计算上是不可行的。抗强碰撞性：找到任何满足H(x)=H(y)的偶对(x,y)在计算上是不可行的。已知一个消息x，去找y使得两者的哈希相等要比随便找两个消息x，y使得两个的哈希相等要更难，可能性更“弱”，所以已知一个消息x，寻找消息y使得两个哈希值相等叫做“弱碰撞”，找到x，y使得两个哈希值相等叫做强碰撞
高灵敏度不可逆
1.3哈希函数在区块链中的使用
区块链技术当中，使用了哈希函数来计算当前区块的父区块的区块头的哈希，并存放在当前区块中。如下图所示：
在上述区块链示意图中，使用的哈希函数是SHA256。如果我们想要碰撞一个已经确定了的区块，就要尝试2256中可能，这是不可行的。这也是区块链不可篡改的密码学基础。
1.4存在的问题
如果使用普通的哈希哈希函数，对于基于区块链的版权保护系统而言，可能会有这样一种场景：原作者创作了数字作品之后，并没有将自己的作用上链，而是以其他方式公布到了网上，Evil可能在网上或者其他地方看到这个作品，然后在未经作者的应允的情况下，将作品以自己的身份上链。如果上链成功，此后，当原作者要求改变区块链上该作品的版权的时候，由于区块链的不可篡改性，这时候就难以解决。
因此，我们考虑引入变色龙哈希。
2. 变色龙哈希概述
2.1变色龙哈希（Chameleon Hash）的定义
一个变色龙哈希函数由四个部分组成：cham_hash=(Setup,KeyGen,Hash,Forge)
Setup(λ):输入安全性参数λ，输出公共参数pp;KeyGen(pp):输入公共参数pp，输出公私钥对（HK,CK）,HK为公钥，CK为私钥，又称门限；Hash(HK,m,r):输入公钥HK,消息m和随机数r，输出变色龙的哈希值CH;Forge（CK，m，r，m’）:输入私钥CK，消息m，随机数r，消息m’，输出另一个随机数r’，满足CH=Hash（HK,m,r）=Hash(HK, m’,r’)。
2.2变色龙哈希满足的安全性要求
抗碰撞：不存在一个有效算法在输入公钥HK，可以找到(m1,r1)和(m2,r2),其中m1≠m2 ，满足Hash（HK,m1,r1）= Hash（HK,m2,r2）。陷门碰撞：存在有效算法，在输入门限CK后，对于任意的m1,r1，给定m2，可以计算出r2，满足Hash（HK,m1,r1）= Hash（HK,m2,r2）。语义安全：对于任意消息m1 m2，Hash（HK,m1,r1）与 Hash（HK,m2,r2）的概率分布是不可区分的，特别的，当r为随机选择时，从Hash（HK,m,r）无法得到关于m的任何信息。2.3变色龙哈希函数分析
相比于传统哈希函数的难以找到碰撞，变色龙哈希可以人为的设一个“弱点”或者“后门”：掌握了这个后门就可以轻松的找到哈希碰撞。
这种设计在一定程度上破坏了哈希函数的两个碰撞性的特点，同时，也破坏了基于哈希函数的区块链的不可篡改的特性，但是也扩大了区块链的应用场景，而且对于不知道门限的普通用户来说，想要找到碰撞依然是不可行的，也就是说，变色龙哈希的安全性也是可以保障的，对于持有“后门”的管理人员，如果其随意篡改区块，也是可以通过验证两个区块的哈希是否相等来验证。
2.4变色龙哈希函数构造
同传统的密码学算法一样，变色龙哈希也都是基于数学难题的，比如：
2.4.1 基于因式分解的变色龙哈希函数的有效构造
2.4.2基于格的变色龙哈希函数的构造
2.4.3基于离散对数的变色龙哈希函数的构造
Hugo Krawczky 和 Tal Rabin 在2000年提出了变色龙哈希方案，具体方案描述如下：
Setup(λ):输入安全性参数λ，构造满足安全性参数λ的大素数p,q,其中p，q满足p=kq+1,选取乘法循环群Z*P中阶为q的元素g，输出公共参数pp=（p,q,g）；KeyGen(pp):输入公共参数pp，在乘法循环群Z*P中随机选择指数x，计算h=gx，最后得到私钥CK=x，公钥HK=h；Hash(HK,m,r):输入公钥HK，消息m，随机数r，其中m，r均为Z*P中元素，输出变色龙哈希值CH=gmhr mod p;Forge（CK，m，r，m’）： 输入私钥，CH=x，消息m，随机数r，消息m’,其中m,r, m’,均为Z*P中的元素，根据CH= gmhr= gm’hr’mod p,可得 m+xr = m’+xr’mod q,继而可计算出r’=（m-m’+xr）x-1 mod p。
如果攻击者在不知道门限的情况下，想要进行碰撞，就必须要求解离散对数𝑙𝑜𝑔𝑔h,而这是不可行的。
对于其他的变色龙哈希函数，其难度也是基于一定的数学难题的，因此其安全性取决于其对应的数学难题的难易程度。
