Perfect Hash Families with Few Functions

Simon R.  Blackburn

Paper 2003/017 Original: eprint.iacr.org/2003/017 ↗

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.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2003-01-28: last updated; 2003-01-28: published
Short URL: https://ia.cr/2003/017
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2003/017,
      author = {Simon R.  Blackburn},
      title = {Perfect Hash Families with Few Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2003/017},
      year = {2003},
      url = {https://eprint.iacr.org/2003/017}
}