**A sequence approach to constructing perfect hash families**

*S.G. Barwick and W.-A. Jackson*

**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 $\phi_1,\ldots,\phi_s$ of linear functionals from $V$ to $F$
with the following property: for all $t$ subsets $X\subseteq V$
there exists $i\in\{1,\ldots,s\}$ such that $\phi_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 {\em 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.

**Category / Keywords: **applications / perfect hash families

**Date: **received 22 Dec 2005, last revised 12 May 2006

**Contact author: **sue barwick at adelaide edu au

**Available format(s): **PDF | BibTeX Citation

**Version: **20060512:215913 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]