International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: A sequence approach to constructing perfect hash families

Authors:
S.G. Barwick
W.-A. Jackson
Download:
URL: http://eprint.iacr.org/2005/465
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2005-12798,
  title={A sequence approach to constructing perfect hash families},
  booktitle={IACR Eprint archive},
  keywords={applications / perfect hash families},
  url={http://eprint.iacr.org/2005/465},
  note={ sue.barwick@adelaide.edu.au 13280 received 22 Dec 2005, last revised 12 May 2006},
  author={S.G. Barwick and W.-A. Jackson},
  year=2005
}