变色龙哈希简介
Chameleon Hash 是一类特殊的 Hash 函数，对于绝大多数使用者，其同样满足哈希函数的 collision-resistant。然而，如果某个人知道 Chameleon 哈希的一些秘密，其可以非常容易破坏collision-resistant。也就是说，对于任意 $m$，其很容易能够找到 $m^\prime \neq m$，使得$ChameleonHash(m^\prime) = ChameleonHash(m)$。这看起来破坏了哈希函数的碰撞抵抗性，但同时带来了non-transferable 和 non-repudiated 的特性。
变色龙哈希
Chameleon Signature Generation -- CHAM-SIG
输入消息$m\in Z_q^*$，签名私钥$S,SK_S$，接收者的$HK_R(i.e.HK_R=y(=g^x mod\ p),g,p,q)$
- 选择一个随机数 $r\in Z_q^*$，计算消息 $m$ 的变色龙哈希 $hash=CHAM-HASH_R(m,r)=g^my^rmod\ p$
- 生成签名 $sig = SIGN_S(hash, HK_R)$
- 则消息 $m$ 的签名为 $SIG(m)=(m,r,sig)$
Chameleon Signature Verufucatuin -- CHAM-VER
输入 $SIG(m)=(m,r,sig)$，公钥 $S,VK_S$， 接收者的$HK_R(i.e.HK_R=y,g,p,q)$
- 计算哈希 $hash=CHAM-HASH_R(m,r)=g^my^r mod \ p$
- 验证 $VERIFY_S((hash, HK_R), sig) $是否为真，为真则正确，为假则不正确
Generate Collision
输入 一个伪造的签名 $SIG(m^\prime) =(m^\prime, r^\prime, sig)$
- 签名者找出计算$sig$时用到的$m,r$
- 签名者计算 $x=\frac{m-m^\prime}{r^\prime-r}mod\ q$
- 签名者选择任意消息 $\bar{m}\in Z_p^*$然后计算$\bar{r}=\frac{m+xr-\bar{m}}{x}mod\ q$
- 签名者给出 $(\bar{m}, \bar{r})$
变色龙哈希的特性
不可转移性(Non-transferability)
签名者S给接收者R一个签名$SIG=(m,r,sig)$，接收者无法让第三方确定$m$的真实性。这是由于对于接收者而言，其可以很简单的通过变色龙哈希函数伪造消息$m$得到一组$(m^\prime,r^\prime)$使得$CHAM-HASH_R(m^\prime,r^\prime)=sig$。计算方法为伪造$m^\prime$，然后计算$r^\prime=\frac{m+xr-m^\prime}{x}mod\ q$。且由于这一特性造成了对于任意的$m$，接受者都可以找到$r$使得满足签名，这就保证了$sig$与$m$无关，即从$sig$中无法获取有关$m$的任何信息。
抗伪造性(Unforgeability)
没有第三方可以找到任意一对$m,r$满足签名，如果接收者不进行伪造的话。
不可否认性(Non-repudiation)
当接收者给出$SIG(m)=(m,r,sig)$时，若接收者没有进行伪造，则签名者$S$无法证明接收者$R$伪造了该消息，也就是说签名者只能承认该消息及签名是真的。
上述构造的缺点
当接收者进行伪造消息$m$时，他同时会暴露自己的私钥$x$，同时，所有用该私钥进行过计算的信息全部都变得不安全了。这一特点抑制了接收者伪造$m$的愿望，但也破坏了不可转移性(Non-transferability)的概念。
无密钥暴露问题的变色龙哈希
Key Generation
输入一个安全参数 $k$，输出一对($SK,PK$)，类似于概率函数：
$$ KeyGen: 1^k\rightarrow(SK,PK) $$
Hash
输入一个公钥$PK$，一个标签$L$，一条消息$m$和一个随机参数$r$，输出一个$\tau$位的二进制字符串
$$ Hash: (PK, L, m, r)\rightarrow C\in\{0,1\}^\tau $$
Universal Forge
输入密钥$SK$，标签$L$，消息$m$，和参数$r$，输出满足$Hash(PK,L,m,r)=Hash(PK,L,m^\prime,r^\prime)$的二元组$(m^\prime,r^\prime)$
$$ UForge(SK,L,m,r)\rightarrow(m^\prime,r^\prime),such\ that $$
$$ Hash(PK,L,m,r)=C=Hash(PK,L,m^\prime,r^\prime) $$
Instance Forge
输入公钥$PK$，标签$L$，消息$m,m^\prime$，随机参数$r,r^\prime$，其中满足$Hash(PK,L,m,r)=Hash(PK,L,m^\prime,r^\prime)$，输出另一对$(m^{\prime\prime},r^{\prime\prime})$满足$Hash(PK,L,m,r)=Hash(PK,L,m^{\prime\prime},r^{\prime\prime})$
$$ IForge(PK,L,m,r,m^{\prime},r^{\prime})\rightarrow(m^{\prime\prime},r^{\prime\prime}),such\ that $$
$$ Hash(PK,L,m,r)=C=Hash(PK,L,m^{\prime},r^{\prime})=Hash(PK,L,m^{\prime\prime},r^{\prime\prime}) $$
除此之外，该函数还满足
Collision-Resistance
在只知道$PK,L,m,r$时，不存在高效的算法可以得到$m^\prime,r^\prime$满足$Hash(PK,L,m,r)=C=Hash(PK,L,m^\prime,r^\prime)$
Semantic Security
变色龙哈希值$C$不揭示关于$m$的任何信息。
Message hiding
当接收者使用 $UForge$ 生成碰撞时，签名者在看到$m^\prime,r^\prime$后，可以在无需曝光$m$的情况下，提出一对$(m^{\prime\prime},r^{\prime\prime})$来证明接收者在伪造消息（即使用$IForge$)。
Key Exposure Freeness
如果接收者有公钥$PK$，并从未计算过一个在标签$L$下的碰撞，则当给出$C=Hash(PK,L,m,r)$时，不存在高效的算法可以找到一个碰撞。即便攻击者拥有$UForge$的访问权限，且可以执行多项式次查询，他也无法得知$SK$。
使用RSA和因子的具体设计（key exposure freeness)
这个设计中有两个后门，其一为RSA模型的因子，另一个时RSA环中元素的根
Key Generation
$\tau，k$为安全参数， $H$为一个抗碰撞的哈希函数，其可以将任意长度的消息变成固定长度为$\tau$的二进制串（例如SHA1,md5)。从${2^{k-1}, ..., 2^k-1}$中取出两个质数$p,q$，令$n=pq$。再生成一个随机的质数$e>2^\tau$。私钥$d$计算公式为$ed=1mod(p-1)(q-1)$。接收者的公钥为$n,e$，私钥为$p,q,d$。
Hash Scheme
用$S$代表标识接收者的字符串，$L$作为一个标签。$C:\{0,1\}^*\rightarrow\{0,...,2^{2k-1}\}$是一个安全的哈希编码算法，将二进制字符串映射成小于$n$的整数。通常的讲，这样的算法是概率的，需要一个随机字符串。这里不考虑它。利用$C$计算 $J=C(L)$，则后门则为$B=J^dmod\ n$，例如在$L$上的一个安全的RSA签名。
那么，$Hash(\cdot)$算法为：
$$ Hash(L,m,r)=J^{H(m)}r^emod\ n,where J=C(L) $$
Collision Finding
为了计算一个碰撞$(m^\prime,r^\prime)$，接收者应该选择一个随机的消息$m^\prime$，然后考虑以下等式：
$$ J^{H(m)}r^e=J^{H(m^\prime)}r^{\prime e} $$
然后求解$r^\prime$即可，即：
$$ r^\prime = rB^{H(m-H(m^\prime))}mod\ n $$
Collision-Resistance 和 Key Exposure Freeness
当接收者给出一个碰撞时，任何人都可以获取与$J=C（L)$关联的密钥$B$，即：
$$ J^{H(m)}r^e=J^{H(m^\prime)}r^{\prime e}\Rightarrow r^\prime/r=B^{H(m)-H(m^\prime)} $$
很明显$\Delta=H(m)-H(m^\prime)$小于$2^\tau$，由于$e$是一个大于$2^\tau$的质数，则$gcd(\Delta,v)=1$，使用扩展的欧几里得算法，可以计算出满足$\alpha\Delta+\beta v=1$的$\alpha,\beta$。则$B$可以被得到：
$$ B=(r^\prime/r)^\alpha J^\beta $$
由于B是一个在$L$上的安全的RSA签名，计算碰撞就等同于破坏RSA签名算法。所以我们认为在不知道trapdoor时计算碰撞是困难的。同时，注意到由于给出碰撞等同于计算签名，所以该算法是key exposure safe.
Semantic Security
对于每个消息$m$， 值$C=Hash(L,m,r)$是由 $r$ 唯一确定的。所以是语义安全的。
Message Hiding
用$C$表示承诺值，一旦碰撞被发现，一个不知道后门的人可以选择任意消息$m^{\prime\prime}$来诋毁承诺。从上面的证明中我们知道一对碰撞$(m,r),(m^\prime,r^\prime)$暴露了后门信息$B=C(L)^d$，为了找到另一个碰撞，选择$m^{\prime\prime}$，计算$r^{\prime\prime}=rB^{H(m)-H(m^\prime)}$即可。
举几个例子🌰
一个简单的例子便于理解
假设小明和小红达成协议，小明将家族产业10%股份转让给小红。签了合同小名很担心啊，如果小红把这件事告诉别人怎么办？这时候就可以用变色龙函数进行签名。小红生成一个只有她才能找到碰撞的函数交给小明，小明再用这个函数来签电子文档。这下小红把签名后的文件丢给大家也没人相信她了。为什么呢？她掌握着哈希函数的弱点，可以随便生成哈希碰撞啊。她把10%股份改成99%都能保证哈希不会变，进而创造出新文件本来就是小明签的这种假象。因此出自小红之手的文件可信度为零。这个特性叫non-transferability，即两者之间达成的信任不能转到第三方。“你知道的太多了” 此时此刻成了真正的包袱。
问题来了，小明抵赖怎么破？如果小明死死咬定转让10%股份是小红伪造，事实上只有1%呢？事实上小明也不能信口开河，他得提供对应的证据。证据就是哈希碰撞。假设双方达成的最初合同是A，而小红将其篡改成了相同哈希的A’，那么小明看到A’这份伪证之后一定能拿出最早那个A来并表明A和A’形成哈希碰撞，否则A’就是真货了。因为正常情况下小明无论如何也找不到碰撞，他就不能抵赖。这个特性叫non-repudiation。
注：引用知乎用户@滕亦飞的回答
- 正版软件授权
开发商使用变色龙哈希签名，发给购买者，购买者即便分享该软件，其他人也无法信任其有没有对软件进行修改，增加后门，即利用了不可传递性。
参考文献
[1] Krawczyk, H. and T. Rabin. “Chameleon Signatures.” NDSS (2000).
[3] Ateniese, G. and B. D. Medeiros. “On the Key Exposure Problem in Chameleon Hashes.” SCN (2004).
