Separating hash families with large universe

Separating hash families are useful combinatorial structures which generalize several well-studied objects in cryptography and coding theory. Let p t ( N , q ) denote the maximum size of universe for a t -perfect hash family of length N over an alphabet of size q . In this paper, we show that q 2 − o ( 1 ) < p t ( t , q ) = o ( q 2 ) for all t ≥ 3 , which answers an open problem about separating hash families raised by Blackburn et al. in 2008 for certain parameters. Previously, this result was known only for t = 3 , 4 . Our proof is obtained by establishing the existence of a large set of integers avoiding nontrivial solutions to a set of correlated linear equations.