# Help to understand the chameleon hash function?

Recently, I'm reading Non-Interactive Key Exchange, in the section 4.2(Towards a factoring-based scheme in the standard model,Page 10), the authors uses

$$t\gets ChamH_{hk}(Z||ID;r);\\ Y\gets u_0u_1^tu_2^{t^2};X=Y^x$$ this way, I don't understand why the authors use the chameleon hash function like this, who can tell me why? And I also don't understand the corresponding proof in the appendix D(Proof of Theorem 4,Page 22)

Edit: Sorry, I know this is bad form, but I'm replacing my entire answer :).

The proof takes place in the so-called CKS-light model, which allows the adversary only two "register honest" queries, i.e. the ability to register two identities of his choice and receive their generated public keys. In the end, he must distinguish the shared secret of these keys from random.

In the proof, the fact that the public key involves a degree-two polynomial in $t$ is used to generate a uniformly random pair of keys satisfying $p(t) = a_0 + a_1t + a_2t^2 = 0$ for the same polynomial $p$, and these $t$-values are used to satisfy the adversary's two honest-key queries. This strongly suggests that the 2 in "degree-2 polynomial in $t$" and the 2 in "adversary only gets 2 honest queries" are one and the same.

One way to test this intuition is to adjust the security game so that the adversary gets 3 honest queries and see if this lets you break it. Another way is to drop the polynomial in $t$ to degree 1 and see if you can break it under the same security model. I think either one will give you some intuition as to why $t$ is used the way that it is.

(My original answer suggested that if the polynomial in $t$ had only degree 1, and the adversary was able to register two identities with the same secret key $x$, this would give him undue power. This is true but irrelevant, since the security game does not let the attacker do this.)

Edit2: As for problems in the proof in the appendix: I'm pretty sure that we need $u_i = g^{b_i}$ for $i = 0, 1, 2$; but I don't see this written anywhere. Also the line $$X_i = D^{\alpha_{3-i}b(t_i)} = (u_0u_1^tu_2^{t^2})^{\frac1{\alpha_i2^{3k}}}$$ is wrong; it should be $$X_i = D^{\alpha_{3-i}b(t_i)} = (u_0u_1^tu_2^{t^2})^{\frac1{\alpha_i}}$$ which sets the secret key $x = 1/(\alpha_i 2^{3k})$ as claimed.

• Actually, I don't quite understand what you have said. Maybe the proof of this part can provide some clues, but I think there are some problems with the Proof of Theorem 4. – T.B Sep 13 '14 at 14:16
• Oh! I did not even see "proof of theorem 4 is in Appendix D". I will give it a read and update my comment ... at first glance, I see it is proving CCA security, which suggests that my algebra is right but motivation was wrong. – Andrew Poelstra Sep 13 '14 at 14:53
• Now, I'm thinking about making this Non-Interactive Key Exchange to be interactive and identity-based in the standard model, would you give me some suggestions?(Or maybe to cooperate to do this, if you will) – T.B Sep 14 '14 at 2:36
• @Alex : $\:$ Identity-Based interactive key exchange can be built from identity-based signatures and [a PKE scheme that is allowed to use trusted public parameters]. $\;\;\;\;$ – user991 Sep 14 '14 at 6:23
• @Andrew Poelstra, I'm sorry that you have made a mistake, as $a(t)=(t-t_1)(t-t_2)$ so $a(t_i)=0$. The proof of Theorem 4 is right, you are wrong. you need to reconsider.. – T.B Sep 20 '14 at 4:25