Skip to main content

It is called perfect hash families in the design theory and computer science literature.

A perfect hash family PHF$(N; k, v, t)$ is an $N \times k$ array on $v$ symbols with $v \geq t$, where for every $N \times t$ subarray at least one row consists of distinct symbols. The following shows a PHF$(6; 12, 3, 3)$. $$\left[ \begin{array}{cccccccccccc} 1&0&0&2&2&2&1&1&2&1&0&2\\ 2&0&1&1&2&0&2&0&1&1&2&1\\ 2&0&2&1&2&1&0&2&2&1&1&0\\ 0&1&2&2&1&2&2&0&1&1&0&0\\ 2&0&1&2&1&1&2&2&0&1&2&1\\ 0&2&1&0&2&2&2&1&0&1&2&1 \end{array}\right]$$

For instance, if we take the second, third and fifth columns, then the the second row is $(0,1,2)$, which consists of distinct symbols. It is readily checked that for any combination of three columns, at least one row is free from identical symbols. To avoid triviality, we generally assume that there is at least one row in which all $v$ elements appear and that $k \geq v$. In the combinatorial design theory literature, the parameter $t$ is called strength.

By regarding your codewords in $C$ as the columns, you can easily see that a PHF$(l; \vert C\vert, q, k)$ is exactly the code you defined. Note that my $k$ is your $\vert C \vert$ while your $k$ is my $t$.

Perfect hash families are introduced by Kurt Mehlhorn in 1980's as an efficient tool for compact storage and fast retrieval of frequently used information, such as reserved words in programing languages and command names in interactive systems. PHFs have since found many other applications in computer science and combinatorics (See, for example,

A. Fiat, M. Naor, Broadcast encryption, Lecture Notes in Computer Science, 773:480–491, 1994.

S. R. Blackburn, M. Burmester, Y. Desmedt, P. R. Wild, Efficient multiplicative sharing schemes, Lecture Notes in Computer Science, 1070:107–118, 1996.

D. R. Stinson, T. van Trung, R. Wei, Secure frameproof codes, key distribution patterns, group testing algorithms and related structures. J. Statist. Plann. Infer., 86 (2000), 595–617.

for some use found in the last century in cryptography and related areas).

Very recent applications include compressive sensing in signal processing and covering arrays for software interacting testing in engineering.

Their existence and generalizations such as separating hash families have been extensively investigated. So if you're interested, you've got a large body of literature to dig in. Since you tagged your question as "combinatorial designs," you find informative the section on PHF in the Handbook of Combinatorial Designs. It's Section 43 of Chapter VI (page 566-568).

There are so many results on bounds on parameters, explicit constructions, and applications inside and outside of mathematics. I think the section in the Handbook of Combinatorial Designs is a good starting point. Updated tables of known PHFs can be found here:

http://www.public.asu.edu/~redoughe/phf_pages/phf_tables.html

Also, if you are curious, the equivalence between a matrix satisfying these conditions and a perfect family of hash functions in the computer theoretic sense is as follows:

A $(k,v)$-hash function is a function $h\ :\ A \rightarrow B$ between finite sets $A$ and $B$, where $\vert A \vert = k$ and $\vert B \vert = v$. The function $h$ is perfect with respect to a subset $X \subseteq A$ if $h$ is injective on $X$, that is, if $h\vert_X$ is one-to-one. Given integers $k$, $v$, and $t$ satisfying $k \geq v \geq t \geq 2$, let $H$ be a set of $N$ $(k, v)$-hash functions between finite sets $A$ and $B$, where $\vert A \vert = k$ and $\vert B \vert = v$. Then $H$ is a perfect hash family of parameters $(N; k, v, t)$ if for any $X \subseteq A$ with $\vert X \vert = t$, there exists at least one $h \in H$ such that $h\vert_X$ is one-to-one. This definition is equivalent to the one given earlier. In fact, one can obtain a perfect family of hash functions by regarding each row of a matrix representation of a PHF$(N; k, v, t)$ as a function $h$, where the value in column $i$ of the row for $h$ represents the value of $h(i)$.

Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43