Separating hash families with large universe

Abstract

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\ge 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.

arXiv comment17 pages, no figure