# Proof of UOWHF construction from a strongly universal hash family

I am currently trying to rigorously prove Lemma 2.2 of [NY].

More specifically, a UOWHF family can be constructed from a composition of a strongly universal family $$G_k = \{g : \{0, 1\}^k \rightarrow \{0, 1\}^{k - 1}\}$$ and a one-way permutation $$f$$, conditioned on the Collision Accessibility property where given a collision pair $$(x, y)$$, we can sample $$g \in G$$ such that $$g(x) = g(y)$$ uniformly over the set $$\{g \in G: g(x) = g(y) \}$$ in polynomial time.

In the paper, an example of a strongly universal family $$G_k = \{g_{a, b} : g_{a, b}(x) = \mathrm{chop}(ax + b), \forall a, b \in \operatorname{GF}[2^k]\}$$ is given, where $$\mathrm{chop} : \{0, 1\}^k \rightarrow \{0, 1\}^{k - 1}$$ is a function that removes the least significant bit of the input. Given a collision pair $$(x, y)$$, we can sample $$g_{a, b}$$ by sample $$a \leftarrow \{0, (x - y)^{-1}\}$$ and $$b \leftarrow \{0, 1, 2, \dots, 2^k - 1\}$$.

In the proof of Lemma 2.2, the paper claims that fixing $$f(x)$$, the process of uniformly sampling $$z \leftarrow \{0, 1\}^k$$ and then sampling $$g \leftarrow \{g \in G_k : g(f(x)) = g(z)\}$$ gives $$g$$ that is uniformly distributed over $$G_k$$. It is important that $$g$$ is uniformly distributed to simulate the input distribution of the adversary $$A$$. However, by taking $$G_k$$ from the example above, $$g_{0, b}$$ will always be in $$\{g \in G_k : g(f(x)) = g(z)\}$$, regardless of $$z$$ so $$g$$ should not be uniformly distributed over $$G_k$$.

Moreover, the proof then claims that $$g \circ f$$ is a 2-1 function so the adversary always finds the pre-image of $$z$$ when $$A$$ succeeds in producing a collision. However, $$g_{0, b}$$ is clearly not a 2-1 function. In this specific example, the probability of sampling $$g_{a, b}$$ where $$a \neq 0$$ is non-negligible so if I can fix the previous part about sampling $$g$$, the proof still works. Unfortunately, I am struggling to show this fact on a general strongly universal family.

I find that putting a constraint where $$a \neq 0$$ will make the proof valid but $$G_k$$ will no longer be a strongly universal family.

Is my understanding of the proof correct? If so, what approach should I take to prove Lemma 2.2?

[NY]: Naor and Yung, Universal One-Way Hash Functions and their Cryptographic Applications, STOC'89