IACR paper details
Title  Perfect Hash Families with Few Functions 

Booktitle  IACR Eprint archive 

Pages  

Year  2003 

URL  http://eprint.iacr.org/2003/017 

Author  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.


Search for the paper
@misc{eprint200311735,
title={Perfect Hash Families with Few Functions},
booktitle={IACR Eprint archive},
keywords={combinatorial cryptography},
url={http://eprint.iacr.org/2003/017},
note={ s.blackburn@rhul.ac.uk 12080 received 28 Jan 2003},
author={Simon R. Blackburn},
year=2003
}
Download a complete BibTeX file.