Paper 2005/465

A sequence approach to constructing perfect hash families

S. G. Barwick and W. -A. Jackson

Abstract

A linear (qd,q,t)-perfect hash family of size s in a vector space V of order qd over a field F of order q consists of a set ϕ1,,ϕs of linear functionals from V to F with the following property: for all t subsets XV there exists i{1,,s} such that ϕi is injective when restricted to . A linear -perfect hash family of minimal size 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 -perfect hash families and -perfect hash families. The sequence approach also explains a relationship between linear -perfect hash families and linear -perfect hash families.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Unknown where it was published
Keywords
perfect hash families
Contact author(s)
sue barwick @ adelaide edu au
History
2006-05-12: revised
2005-12-31: received
See all versions
Short URL
https://ia.cr/2005/465
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/465,
      author = {S. G.  Barwick and W. -A.  Jackson},
      title = {A sequence approach to constructing perfect hash families},
      howpublished = {Cryptology {ePrint} Archive, Paper 2005/465},
      year = {2005},
      url = {https://eprint.iacr.org/2005/465}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.