05526553

a

05526553 Colbourn, Charles J. Constructing perfect hash families using a greedy algorithm. Li, Yongqing (ed.) et al., Coding and cryptology. Proceedings of the first international workshop, Wuyi Mountain, Fujian, China, June 11--15, 2007. Hackensack, NJ: World Scientific (ISBN 978-981-283-223-8/hbk). Series on Coding Theory and Cryptology 4, 109-124 (2008). 2008 Hackensack, NJ: World Scientific EN

doi:10.1142/9789812832245_0008

Summary: A perfect hash family $\text{PHF}(N;k,v,t)$ is an $N\times k$ array on $v$ symbols with $v\ge t$, in which in every $N\times t$ subarray, at least one row is comprised of distinct symbols. Perfect hash families have a wide range of applications in cryptography, particularly to secure frameproof codes, in database management, and are indirectly used in software interaction testing. A simple one-row-at-a-time greedy algorithm for constructing small perfect hash families is described. The algorithm is deterministic, and its worst-case runtime is polynomial in $k$ and $v$ but exponential in $t$; consequently, when $t$ is fixed, the algorithm runs in polynomial time in the worst case. It provides a deterministic guarantee that the number $N$ of rows produced is $O(\log k)$. In addition to these strong asymptotic guarantees, the method is shown to be practical for the computation of perfect hash families for ``small" values of $k$ and $t$.