Separating hash families: A Johnson-type bound and new constructions

2016/01/19 by Shangguan, Chong, Ge, Gennian · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1601.04807

Abstract

Separating hash families are useful combinatorial structures which are generalizations of many well-studied objects in combinatorics, cryptography and coding theory. In this paper, using tools from graph theory and additive number theory, we solve several open problems and conjectures concerning bounds and constructions for separating hash families. Firstly, we discover that the cardinality of a separating hash family satisfies a Johnson-type inequality. As a result, we obtain a new upper bound, which is superior to all previous ones. Secondly, we present a construction for an infinite class of perfect hash families. It is based on the Hamming graphs in coding theory and generalizes many constructions that appeared before. It provides an affirmative answer to both Bazrafshan-Trung's open problem on separating hash families and Alon-Stav's conjecture on parent-identifying codes. Thirdly, let p_t(N,q) denote the maximal cardinality of a t-perfect hash family of length N over an alphabet of size q. Walker II and Colbourn conjectured that p₃(3,q)=o(q²). We verify this conjecture by proving q^2-o(1)

Cited by

• Quantitative Frameproof Codes and Hypergraphs

Related

• Constructions and bounds for separating hash families
• Separating hash families with large universe
• Perfect and separating Hash families: new bounds via the algorithmic\n cluster expansion local lemma
• A tight bound on the size of certain separating hash families
• Beating Fredman-Komlós for perfect k-hashing