Paper 2006/002

Geometric constructions of optimal linear perfect hash families

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

Abstract

A linear $(q^d,q,t)$-perfect hash family of size $s$ in a vector space $V$ of order $q^d$ over a field $F$ of order $q$ consists of a sequence $\phi_1,\ldots,\phi_s$ of linear functions from $V$ to $F$ with the following property: for all $t$ subsets $X\subseteq V$ there exists $i\in\{1,\ldots,s\}$ such that $\phi_i$ is injective when restricted to $F$. A linear $(q^d,q,t)$-perfect hash family of minimal size $d(t-1)$ is said to be optimal. In this paper we use projective geometry techniques to completely determine the values of $q$ for which optimal linear $(q^3,q,3)$-perfect hash families exist and give constructions in these cases. We also give constructions of optimal linear $(q^2,q,5)$-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-01-04: received
Short URL
https://ia.cr/2006/002
License
Creative Commons Attribution
CC BY

BibTeX

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