Some bounds on separating hash families.pdf

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

2、出，它在編碼理論和密碼學(xué)中有廣泛的應(yīng)用，如D.Boneh和J.Shaw提出的防誣陷碼等價(jià)于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的上界.當(dāng)w1=w2=w時(shí)，J

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