TY - JOUR

T1 - Explicit Constructions of Perfect Hash Families from Algebraic Curves over Finite Fields

AU - Wang, Huaxiong

AU - Xing, Chaoping

PY - 2001/1

Y1 - 2001/1

N2 - Let A be a set of order n and B be a set of order m. An (n, m, w)-perfect hash family is a set H of functions from A to B such that for any X⊆A with X=w, there exists an element h∈H such that h is one-to-one when restricted to X. Perfect hash families have many applications to computer science, such as database management, circuit complexity theory and cryptography. In this paper, we provide explicit constructions of perfect hash families based on algebraic curves over finite fields. In particular, using the Garcia-Stichtenoth curves, we obtain infinite classes of (n, m, w)-perfect hash families with H=O(logn) for fixed m and w, which are among the most efficient explicit constructions for perfect hash families known in the literature. We also exhibit examples to show the efficiency of the new constructions and their applications to the constructions of cover-free families.

AB - Let A be a set of order n and B be a set of order m. An (n, m, w)-perfect hash family is a set H of functions from A to B such that for any X⊆A with X=w, there exists an element h∈H such that h is one-to-one when restricted to X. Perfect hash families have many applications to computer science, such as database management, circuit complexity theory and cryptography. In this paper, we provide explicit constructions of perfect hash families based on algebraic curves over finite fields. In particular, using the Garcia-Stichtenoth curves, we obtain infinite classes of (n, m, w)-perfect hash families with H=O(logn) for fixed m and w, which are among the most efficient explicit constructions for perfect hash families known in the literature. We also exhibit examples to show the efficiency of the new constructions and their applications to the constructions of cover-free families.

KW - Algebraic curves

KW - Cover-free family

KW - Perfect hash family

UR - http://www.scopus.com/inward/record.url?scp=0042322434&partnerID=8YFLogxK

U2 - 10.1006/jcta.2000.3068

DO - 10.1006/jcta.2000.3068

M3 - Article

AN - SCOPUS:0042322434

SN - 1096-0899

VL - 93

SP - 112

EP - 124

JO - Journal of Combinatorial Theory: Series A

JF - Journal of Combinatorial Theory: Series A

IS - 1

ER -