傾斜完全雜湊函數(shù)族.pdf

1、令A(yù),B分別是有n和m個(gè)元素的集合,一個(gè)(n,m,w)-完全雜湊函數(shù)族是指一組從A到B的函數(shù)F,使得對(duì)A的任意w元子集X,都至少存在一個(gè)函數(shù)f∈F使得,f|x是單射的。完全雜湊函數(shù)族在計(jì)算機(jī)領(lǐng)域有廣泛的應(yīng)用,學(xué)多學(xué)者已經(jīng)將其應(yīng)用到操作系統(tǒng)、語言翻譯系統(tǒng)、超文本、超媒體、文件管理和信息檢索系統(tǒng)等方面。最近,人們發(fā)現(xiàn)它們在密碼學(xué)中(尤其是門限密碼中)也有出色的應(yīng)用。
　　然而,在許多實(shí)際的應(yīng)用中,完全雜湊函數(shù)族有一定的限制。為了實(shí)際需

2、要,我們將其進(jìn)行推廣:一個(gè)(n,m,t)-傾斜完全雜湊函數(shù)族是指一組從A到B的函數(shù)H,使得對(duì)A的任意t元子集X,都至少存在一個(gè)函數(shù)h∈H使得h|x是滿射的。我們發(fā)現(xiàn)傾斜完全雜湊函數(shù)族在秘密信息檢索和秘密共享方案中有更靈活的應(yīng)用。本文將主要討論傾斜完全雜湊函數(shù)族的性質(zhì),構(gòu)造及其在密碼學(xué)中的應(yīng)用。
　　我們首先介紹完全雜湊函數(shù)族,概述他們的上下界和構(gòu)造,并給出它們的一個(gè)新的下界,然后將此下界和著名的Fredman-Komlos下界進(jìn)行

3、比較,分析并給出了我們的界比Fredman-Komlos界好的條件。
　　接著我們把完全雜湊函數(shù)族進(jìn)行推廣,引出傾斜完全雜湊函數(shù)族的概念,同時(shí)對(duì)他們的上下界進(jìn)行了分析,然后運(yùn)用編碼,多項(xiàng)式,指數(shù)和,均衡不完全區(qū)組設(shè)計(jì),拉丁矩陣和拉丁方陣等方法對(duì)傾斜完全雜湊函數(shù)族進(jìn)行構(gòu)造,并給出一些遞歸構(gòu)造,得以從“小”的傾斜完全雜湊函數(shù)族構(gòu)造“大”的傾斜完全雜湊函數(shù)族。
　　最后,我們介紹秘密共享方案及其累積數(shù)組和廣義累積數(shù)組,分析如何運(yùn)用