Optimal linear perfect hash families with small parameters

Abstract

A linear (qd, q, t)-perfect hash family of size s consists of a vector space V of order qd over a field F of order q and a sequence Φ1; . . . ; Φs of linear functions from V to F with the following property: for all t subsets X ⊆ V, there exists i ∈ {1; . . . ; s} such that Φi is injective when restricted to F. A linear (qd, q, t)--perfect hash family of minimal size d(t - 1) is said to be optimal. In this paper, we prove that optimal linear (qd, q, t)-perfect hash families exist only for q = 11 and for all prime powers q > 13 and we give constructions for these values of q.