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

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

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

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