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?


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.