Provable security of cryptographic hash functions

Question

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?

Answer 1

First this, a nit about the hash function: one can trivially create a collision by appending a 0 value; an appended 0 does not change the hash value, and hence that produces a collision.

If we say that collisions are required to have at least one place there two colliding messages differ with at least one having a nonzero value, then we can show it. Here is how, given a black box which finds a collision, can perform discrete logs (with good probability).

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}$