**Perfect Hash Families with Few Functions**

*Simon R. Blackburn*

**Abstract: **An {\em $(s;n,q,t)$-perfect hash family} is a set of functions
$\phi_1,\phi_2,\ldots ,\phi_s$ from a set $V$ of cardinality $n$ to a
set $F$ of cardinality $q$ with the property that every $t$-subset of
$V$ is injectively mapped into $F$ by at least one of the functions
$\phi_i$.

The paper shows that the maximum value $n_{s,t}(q)$ that $n$ can take for fixed $s$ and $t$ has a leading term that is linear in $q$ if and only if $t>s$. Moreover, for any $s$ and $t$ such that $t>s$, the paper shows how to calculate the coefficient of this linear leading term; this coefficient is explicitly calculated in some cases. As part of this process, new classes of good perfect hash families are constructed.

**Category / Keywords: **combinatorial cryptography

**Date: **received 28 Jan 2003

**Contact author: **s blackburn at rhul ac uk

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Note: **This paper is about to undergo a major rewrite. In particular,
a reference to a paper of Fachini and Nilli (Recursive bounds
for perfect hashing, Discrete Applied Maths 2001) that appeared
after the paper has written will be added. Fachini and
Nilli's improvement of a bound of Dyachkov can be used as the
`if' part of Theorem 1 of my paper (and their argument is essentially
the same as the one I give).

**Version: **20030128:190356 (All versions of this report)

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

[ Cryptology ePrint archive ]