Perfect Hash Families with Few Functions

Simon R.  Blackburn

Paper 2003/017

Perfect Hash Families with Few Functions

Simon R. Blackburn

Abstract

An {\em -perfect hash family} is a set of functions from a set of cardinality to a set of cardinality with the property that every -subset of is injectively mapped into by at least one of the functions . The paper shows that the maximum value that can take for fixed and has a leading term that is linear in if and only if . Moreover, for any and such that , 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.

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

Metadata

Available format(s): PS
Publication info: Published elsewhere. Unknown where it was published
Keywords: combinatorial cryptography
Contact author(s): s blackburn @ rhul ac uk
History: 2003-01-28: received
Short URL: https://ia.cr/2003/017
License: CC BY

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}
}