Heterogeneous Hash Families:Probability Methods And Combinatorial Constructions

Hash families have important application in the field of cryptography research. The paper generalizes the concepts of perfect hash families and separating hash fam-ilies, and then defines heterogeneous hash families (PHHF) and heterogeneous hash families (SHHF). The probability methods and combinatorial constructions of PHHF and SHHF are studied. By using Lovasz local lemma and expurgation method, we obtain the lower bounds of the maximum number of functions which the PHHF and SHHF contains. By using the direct construction and recursive method of combination designs, we show the existence of PHHF and SHHF with some parameters. Accord-ing to Setein-Lovasz theorem, we give the deterministic constructions of some other relevant combinatorial structures such as Turan system, directed covering and general cover and give their related existence theorem. By exploring symmetric designs and separating hash families we know symmetric design is a separating hash family of type {1,ω} under certain conditions.