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



Your Answer

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