Ramp Perfect Hash Families

Let A be a set of order n and B be a set of order m. An (n, m, w)-perfect hash families is a set T of functions from A to B such that for any X (?) A with |X| = w, there exists at least an elements f ∈ F such that f\x is injective. Perfect hash families have many applications to computer science, such as operating system, language translation system, hypertext, hypermedia, file managers, and information retrieval. More recently, they have found significant applications to cryptography (especially to threshold cryptography).However, for some practical applications, there is some restriction on perfect hash families. We study a generalization of perfect hash families, namely ramp perfect hash families. An (n, m, t)-ramp perfect hash families is a set H of functions from A to B such that for any X (?) A with |X| = t, there exists at least an element h ∈ H such that h\x is surjective. We will find that ramp perfect hash families have more flexible applications to private information retrieval and secret share scheme. We will provide bounds on H and describe some constructions for ramp perfect hash families, and then analyze their applications to cryptography.First, we survey some results about perfect hash families: bounds and constructions. Then we will derive a new lower bound on perfect hash families, and compare it with the well-known result of Fredman-Komlos, and give the conditions on which our bound is better than Fredman-Komlos's.Secondly, we generalize perfect hash families to ramp perfect hash families. We analyze and provide their lower bounds and upper bounds, then use some methods, such as coding, polynomial, exponential sum, balanced incomplete block designs, Latin rectangle and Latin square to give their constructions. we also describe some recursive constructions, showing that we can construct a "big" ramp perfect hash families from some "small" ones.Finally, we introduce the concept of secret share scheme and its cumulative arrays and generalized cumulative arrays, and then describe how to use...