Linear hash families and forbidden configurations

Charles Colbourn, Alan C H Ling

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


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 languageEnglish (US)
Pages (from-to)25-55
Number of pages31
JournalDesigns, Codes, and Cryptography
Issue number1
StatePublished - Jul 2009


  • 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


Dive into the research topics of 'Linear hash families and forbidden configurations'. Together they form a unique fingerprint.

Cite this