1
$\begingroup$

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.

$\endgroup$

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.