Some bounds on separating hash families.pdf

1、設X和Y是兩個有限集滿足|X|=n且|Y|=m，F是從X到Y的函數組成的集合且|F|=N，若對X中任意t個兩兩不相交的子集C1，C2，…，Ct，滿足|Ci|=wi，1≤i≤t，都存在一個函數f∈F使得f(Ci)∩f（Cj）=(Φ)，1≤i≠j≤t，則稱F是一個（N;n，m{w1，w2，…，wt}）-可分hash族，簡記為SHF(N;n，m，{w1，w2，…，wt}）.
　　SHF的概念最早由D.R.Stinson等人在2000年提

2、出，它在編碼理論和密碼學中有廣泛的應用，如D.Boneh和J.Shaw提出的防誣陷碼等價于SHF(N;n，m，{1，w});D.R.Stinson等人研究的安全防誣陷碼是SHF(N;n，m，{w，w});H.D.L.Hollmann等人發(fā)起研究的多元追蹤碼不僅是SHF(N;n，m，{w+1{1,…,1})，也是SHF（N;n，m，{w，w}）.
　　本文主要研究SHF(N;n，m，{w1，w2})中n的上界.當w1=w2=w時，J

3、.N.Staddon等人證明了n＜m[N/w]+2w-2;當w1=w2=w且N=2w時，M.Bazrafshan和T.Trung將上述界改進為n＜m2;當w1≠w2且N=w1+ w2時，SHF（w1+w2;n，m，{w1，w2}）的結果已有很多，目前最好的結果是n≤m2.
　　我們的主要結果是:證明了SHF(4;10，4，{2，2})是最優(yōu)的并給出了相應的構造;當m＞5時，將SHF(2w;n，m，{w，w})的上界改進為n≤(m-