Xin Wei, Separating hash families with large universe

Separating hash families are useful combinatorial structures that generalize several well-studied objects in cryptography and coding theory. Let $p_t(N, q)$ denote the maximum size of the universe for a $t$-perfect hash family of length $N$ over an alphabet of size $q$. We show that $q^{2 – o(1)} < p_t(t, q) = o(q^2)$ for all  $t \ge 3$, thereby resolving an open problem raised by Blackburn et al. (2008) for certain parameter ranges. Previously, this result was known only for $t = 3$ and $t = 4$. Our approach establishes the existence of a large set of integers that avoids nontrivial solutions to a system of correlated linear equations. This is joint work with Xiande Zhang and Gennian Ge.