A sequence approach to linear perfect hash families

Abstract

A linear (q d, q, t)-perfect hash family of size s in a vector space V of order q d over a field F of order q consists of a set S = {φ1, ⋯, φs} of linear functionals from V to F with the following property: for all t subsets X\subseteq V there exists φi ∈ S such that φi is injective when restricted to F. A linear (q d, q, t)-perfect hash family of minimal size d(t - 1) is said to be optimal. In this paper, we extend the theory for linear perfect hash families based on sequences developed by Blackburn and Wild. We develop techniques which we use to construct new optimal linear (q 2, q, 5)-perfect hash families and (q 4, q, 3)-perfect hash families. The sequence approach also explains a relationship between linear (q 3, q, 3)-perfect hash families and linear (q 2, q, 4)-perfect hash families. © 2007 Springer Science+Business Media, LLC.