论文部分内容阅读
令A,B分别是有n和m个元素的集合,一个(n,m,w)-完全杂凑函数族是指一组从A到B的函数F,使得对A的任意w元子集X,都至少存在一个函数f∈F使得,f|x是单射的。完全杂凑函数族在计算机领域有广泛的应用,学多学者已经将其应用到操作系统、语言翻译系统、超文本、超媒体、文件管理和信息检索系统等方面。最近,人们发现它们在密码学中(尤其是门限密码中)也有出色的应用。 然而,在许多实际的应用中,完全杂凑函数族有一定的限制。为了实际需要,我们将其进行推广:一个(n,m,t)-倾斜完全杂凑函数族是指一组从A到B的函数H,使得对A的任意t元子集X,都至少存在一个函数h∈H使得h|x是满射的。我们发现倾斜完全杂凑函数族在秘密信息检索和秘密共享方案中有更灵活的应用。本文将主要讨论倾斜完全杂凑函数族的性质,构造及其在密码学中的应用。 我们首先介绍完全杂凑函数族,概述他们的上下界和构造,并给出它们的一个新的下界,然后将此下界和著名的Fredman-Komlos下界进行比较,分析并给出了我们的界比Fredman-Komlos界好的条件。 接着我们把完全杂凑函数族进行推广,引出倾斜完全杂凑函数族的概念,同时对他们的上下界进行了分析,然后运用编码,多项式,指数和,均衡不完全区组设计,拉丁矩阵和拉丁方阵等方法对倾斜完全杂凑函数族进行构造,并给出一些递归构造,得以从“小”的倾斜完全杂凑函数族构造“大”的倾斜完全杂凑函数族。 最后,我们介绍秘密共享方案及其累积数组和广义累积数组,分析如何运用完全杂凑函数族和倾斜完全杂凑函数族来构造(广义)累积数组,从而给出秘密共享方案的构造。