Perfect Hash Families: Constructions and Applications

[摘要] Let A and B be finite sets with |A|=n and |B|=m.An (n,m,w)-perfect hash familyis a collection Fof functionsfrom A to B such that for any X⊆ A with |X|=w, there exists at least one ? ∈ F such that ? is one-to-one when restricted to X.Perfect hash families are basic combinatorial structures and theyhave played important roles in Computer Science in areas such as databasemanagement, operating systems, and compiler constructions. Such hashfamilies are used for memory efficient storage and fast retrievalof items such as reserved words in programming languages, commandnames in interactive systems, or commonly used words in naturallanguages. More recently, perfect hash families have found numerousapplications to cryptography, for example, to broadcast encryptionschemes, secret sharing, key distribution patterns, visualcryptography, cover-free families and secure frameproof codes.In this thesis, we survey constructions and applications of perfecthash families. For constructions, we divided the results into threeparts, depending on underlying structure and properties of theconstructions: combinatorial structures, linear functionals, and algebraic structures. For applications, we focus on those related to cryptography.

[发布机构] University of Waterloo

[效力级别] Perfect Hash Families

[关键词] Mathematics;Perfect Hash Families;Combinatorial Structures;Cryptography;Probability Methods