Back to search

University of Waterloo

Perfect Hash Families: Constructions and Applications

Abstract

dc:description.abstract

Let <b>A</b> and <b>B</b> be finite sets with |<b>A</b>|=<i>n</i> and |<b>B</b>|=<i>m</i>. An (<i>n</i>,<i>m</i>,<i>w</i>)-<i>perfect hash</i> family</i> is a collection <i>F</i> of functions from <b>A</b> to <b>B</b> such that for any <b>X</b> &#8838; <b>A</b> with |<b>X</b>|=<i>w</i>, there exists at least one ? &#8712; <i>F</i> such that ? is one-to-one when restricted to <b>X</b>. Perfect hash families are basic combinatorial structures and they have played important roles in Computer Science in areas such as database management, operating systems, and compiler constructions. Such hash families are used for memory efficient storage and fast retrieval of items such as reserved words in programming languages, command names in interactive systems, or commonly used words in natural languages. More recently, perfect hash families have found numerous applications to cryptography, for example, to broadcast encryption schemes, secret sharing, key distribution patterns, visual cryptography, cover-free families and secure frameproof codes. In this thesis, we survey constructions and applications of perfect hash families. For constructions, we divided the results into three parts, depending on underlying structure and properties of the constructions: combinatorial structures, linear functionals, and algebraic structures. For applications, we focus on those related to cryptography.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2003

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kim, Kyung-Mi

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Copyright: 2003, Kim, Kyung-Mi. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/1118

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kim, Kyung-Mi. Perfect Hash Families: Constructions and Applications. University of Waterloo, 2003. http://hdl.handle.net/10012/1118