A tight bound on the size of certain separating hash families

2015/10/01 by Chuan Guo, Douglas R. Stinson, Guo, Chuan +1
Computer Science · Engineering · Mathematics · #Advanced Steganography and Watermarking Techniques #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #cs.DM #cs.IT #graph theory and CDMA systems #math.CO #math.IT

paper · pdf · doi:10.48550/arxiv.1510.00293

arxiv created 2015/10/01 · openalex publication_date 2015/10/01 · arxiv updated 2015/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we present a new lower bound on the size of separating hash families of type w₁^q-1,w₂ where w₁ < w₂. Our result extends the paper by Guo et al. on binary frameproof codes. This bound compares well against known general bounds, and is especially useful when trying to bound the size of strong separating hash families. We also show that our new bound is tight by constructing hash families that meet the new bound with equality.

Related

• Constructions and bounds for separating hash families
• Perfect and separating Hash families: new bounds via the algorithmic cluster expansion local lemma
• On tight bounds for binary frameproof codes
• Separating hash families: A Johnson-type bound and new constructions
• Separating hash families with large universe