I have the following question related to proving a hash function is secure if discrete log in group $\mathbb{G}$ is hard. The hash function (Gen,H) goes as follows:

Gen: on input $1^n$, run to obtain cyclic group $\mathbb{G}$ of order $q$ prime and $h_1$, then select uniformly at random $h_2,h_3,..,h_t \ \in \ \mathbb{G}$. Output $s= \ \langle\mathbb{G},q,(h_1,..h_t)\rangle$ as the key.

H: given a key $s \ = \ \langle\mathbb{G},q,(h_1,..,h_t)\rangle$ and input $(x_1,...x_t)$ with $x_i \in Z_q$, output $\Pi_i h_i^{x_i}$.

Prove that if this log is hard in $\mathbb{G}$ the construction is a collision resistant hash function. Discuss how this construction can be used to obtain compression regardless of the number of bits needed to represent elements of $\mathbb{G}$.

So I assume there is adversary that can find a collision in the hash function and I try to use him to build adversary that can solve dis log in ppt. If the adversary can find a collision then: $\Pi_i h_i^{x_i}$ = $\Pi_i h_i^{x_i'}$ where $x'$ another input that caused the collision. I do not know how to continue from here to prove that I can solve discrete log. Thank you in advance for your help.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.