Abstract
The classical orthogonal arrays over the finite field underlie a powerful construction of perfect hash families. By forbidding certain sets of configurations from arising in these orthogonal arrays, this construction yields previously unknown perfect, separating, and distributing hash families. When the strength s of the orthogonal array, the strength t of the hash family, and the number of its rows are all specified, the forbidden sets of configurations can be determined explicitly. Each forbidden set leads to a set of equations that must simultaneously hold. Hence computational techniques can be used to determine sufficient conditions for a perfect, separating, and distributing hash family to exist. In this paper the forbidden configurations, resulting equations, and existence results are determined when (s, t) {(2, 5), (2, 6), (3, 4), (4, 3)}. Applications to the existence of covering arrays of strength at most six are presented.
Original language | English (US) |
---|---|
Pages (from-to) | 25-55 |
Number of pages | 31 |
Journal | Designs, Codes, and Cryptography |
Volume | 52 |
Issue number | 1 |
DOIs | |
State | Published - Jul 2009 |
Keywords
- Covering array
- Finite field
- Orthogonal array
- Perfect hash family
- Separating hash family
ASJC Scopus subject areas
- Theoretical Computer Science
- Applied Mathematics
- Discrete Mathematics and Combinatorics
- Computer Science Applications