# Provable security of cryptographic hash functions

I am working on the following exercise question:

Consider the following construction of a “keyed” hash function from Katz & Lindell (ex. 7.22 (1st ed.)/ 8.21(2nd ed.)).

Gen : On input $$1^n$$ , generate a cyclic group $$\mathcal{G}$$ of order $$q$$, where $$q$$ is an $$n$$-bit prime, and a generator $$h_1$$. Then select $$h_2, \ldots , h_t \leftarrow \mathcal{G}$$. Output $$s := (\mathcal{G}, q,(h_1, \ldots, h_t))$$ as the key.

H : Given a key $$s$$ and input $$x_1, \ldots , x_t$$ where $$x_i \in \mathbb{Z}/q\mathbb{Z}$$, output $$H_s(x_1, \ldots , x_t) := \Pi_i\, h_i x_i$$

a) Let $$\pi$$ be a permutation of the integers $$1, \ldots , t$$. Prove that no adversary $$A$$, even knowing $$\pi$$, can distinguish between $$(h_1, \ldots , h_t)$$ and $$(h_{\pi(1)}, \ldots , h_{\pi(t)} )$$ with better than negligible probability. Give a formal description of this statement as an experiment before completing the proof.

b) Prove that if Gen produces groups $$\mathcal{G}$$ where the discrete logarithm problem is hard, then $$H_s$$ is collision resistant.

a) For this part I can intuitively see that since picking numbers from random in a cyclic group are no different than a permutation,I am not sure how to formulate it. b) how can you break the discrete logarithm problem if you find a collision in such a scheme?

Suppose we have the elements $G$ and $H$, and which to find the value $k = log_G H$, that is, the solution to $kG = H$.
What we do is select $h_i = r_i G + s_i H$, where $r_i, s_i$ are random values. Then, present these $h_i$ values (along with the rest of the parameters) to the black box.
The black box will produce a collision, that is, two messages $m, m'$ with $\sum m_i h_i = \sum m'_i h_i$. Rewriting this, we get $(\sum (m_i - m'_i)r_i)G + (\sum (m_i - m'_i)s_i) H = 0$, or $aG + bH = 0$, for values $a, b$ which we can compute (as we know the $m_i, m'_i, r_i, s_i$ values)
As the $r_i, s_i$ parameters are random values unknown to the blackbox (and at least one of the $m_i - m'_i$ values will be nonzero), it is unlikely that $b$ will be 0; if it is not, then we have $k = -ab^{-1}$