（基础数学专业论文）密码学中的hash函数族.pdf

摘要 设x 与】，是两个阶数为n 与m 的有限集，映射厂：x y 称为h a s h 函数，这 样的个h a s h 函数的集合称为( n ；n ，1 ) h a s h 函数族，记为f 如果对于x 的任 何一个w 元子集矿，h a s h 函数族f 中至少存在一个函数厂f 在形上是单射， 称之为完全h a s h 函数族h a s h 函数族在计算机科学中有很多应用，例如：操作 系统、语言传输系统、超文本、超媒体、档案管理和信息修复最近，人们发现 它在密码学中也有重要的应用，特别是门限密码 在实际应用中，完全h a s h 函数族的限制太严，在某些方面的应用受到限制 推广h a s h 函数族，定义分离h a s h 函数族如下如果一个h a s h 函数族满足下列 性质：对于任意c i ，c 2 ，e x ，lgl _ w t ，ic 2l _ w 2 ，lc fl _ w ，且 gnc ：= ( f - j ) ，至少存在一个函数f 使得：对任意f j 有 矿( x ) ：x q ) n 厂( x ) ：x q ) = ，就称其为分离h a s h 函数族，记为 s h f ( n ；n ，朋，w 2 ，w ) ) 分离h a s h 函数族在计算机科学中也有很重要的应 用，例如：指纹编码、安全指纹编码、i p p 编码等 在第二章，介绍了一些关于完全h a s h 函数族的结构与界的结果我们主要 利用矩阵和图论的知识研究了与w 较小的完全h a s h 函数族的结构与界的问题 我们用另一方法证明了p h f ( 3 ；n ，m ，4 ) 的矩阵结构特点 在第三章，首先介绍了分离h a s h 函数族，然后分析了与w 较小分离h a s h 函数族的结构与界，并利用矩阵和图论的知识，给出且证明了p h f ( 3 ；n ，m ， 2 ，2 ) ) 的结构和p h f ( 5 ；n ，m ， 3 ，3 ) ) 的界 第四章，介绍了一类特殊的h a s h 函数一广义布尔函数，非线性广义布尔函 数在密码学与编码理论中有重要应用，特别是流密码本文中，在介绍了布尔函 数的推广，广义布尔函数的表示方法、性质和变换的基础上，研究了非线性广义 布尔函数的性质，给出并证明了：( 1 ) 广义布尔函数厂在g f ( 3 ”) 到g f ( 3 ) 上谱表 示；( 2 ) 研究了广义布尔函数在子群和其j 下交子群中特征和谱的关系；( 3 ) 研究 了非线性广义布尔函数的覆盖；( 4 ) 广义布尔函数原象的界。 关键词：完全h a s h 函数族；分离h a s h 函数族；广义布尔函数 i i a b s t r a c t l e txb eas e to fo r d e r 刀a n dyb eas e to fo r d e rm a nh a s h f u n c t i o ni saf u n c t i o nf ：x j y a n ( n ；n ，m ) h a s hf a m i l yi sas e to fn h a s hf u n c t i o n s ，s a yf a n ( n ；n ，m ，w ) - p e r f e c th a s hf a m i l yi sas e r fs u c h t h a tf o ra n yw 互xw i t hl w i = w ，t h e r ee x i s t sa tl e a s to n ef u n c t i o n f f ，s u c ht h a tf l 矿i si n j e c t i v e p e r f e c t h a s hf a m i l yh a v em a n y a p p li c a t i o n st oc o m p u t e rs c i e n c e ，s u c ha so p e r a t i n gs y s t e m ，l a n g u a g e t r a n s l a t i o n s y s t e m ，h y p e r t e x t ，h y p e r m e d i a ， f il e m a n a g e r s ， a n d i n f o r m a t i o nr e t r i e v a l m o r er e c e n t l y ，t h e yh a v ef o u n ds i g n i f i c a n t a p p li c a t i o n st oc r y p t o g r a p h y ，e s p e c i a ll yt ot h r e s h o l dc r y p t o g r a p h y h o w e v e r ，f o rs o m ep r a c t i c a la p p l i c a t i o n s ，t h e r ei ss o m er e s t r i c t i o n o np e r f e c th a s hf a m i l y w es t u d yag e n e r a l i z a t i o no fp e r f e c th a s hf a m i l y ， n a m e l ys e p a r a t i n gh a s hf a m i l y a n ( n ；n ，m ， w ，w 2 ，彬) ) - s e p a r a t i n gh a s h f a m i l yi sa n ( n ；n ，肌) h a s hf a m i l y ，s a t i s f y i n gt h ef o l l o w i n gp r o p e r t y ：f o r a n yq ，g ，es xs u c h t h a tic li 一，i gi - w 2 ，ici - w a n d c i n c j = ( i ) f o ra n yi j 。t h e r ee x i s t sa tl e a s to n e f u n c t i o nj fs u c ht h a t f ( x ) ：x e c i n f ( x ) ：x e c l = f o ra n yi c j s e p a r a t i n gh a s hf a m i l yh a v e a p p l i c a t i o n st oc o m p u t e rs c i e n c e ，s u c ha sf r a m e p r o o fc o d e s ，s e c u r e f r a m e p r o o fc o d e s ，i d e n t i f i a b l ep a r e n tp r o p e r t yc o d e s i nc h a p t e rt w o ，w es u r v e ys o m er e s u l t sa b o u tp e r f e c th a s hf a m il y ： c o n s t r u c t i o n sa n db o u n d s t h e nw ew i l ld e r i v es o m en e wc o n s t r u c t i o n sa n d b o u n d so ns m a llt y p ep e r f e c th a s hf a m il yu s i n gm a t r i xa n dg r a p ht 0 0 1 w e g i v ea n o t h e rp r o o f o fc o n s t r u c t i o no fp h f ( 3 ；n ，掰，4 ) m a t r i xb ya p p l y i n g g r a p h i nc h a p t e rt h r e e ，w ei n t r o d u c es e p a r a t i n gh a s hf a m i l y ，c o n s t r u c t i o n s a n db o u n d so ns m a l lt y p es e p a r a t i n gh a s hf a m i l yu s i n gm a t r i xa n dg r a p h w ep r o v eap r e c i s es t r u c t u r a lc h a r a c t e r i z a t i o no fp h f ( 3 ；n ，m ， 2 ，2 ) ) f u r t h e r m o r e ，w eg i v ea n dp r o v ean e wu p p e rb o u n do fp h f ( 5 ；n ，m ， 3 ，3 ) ) i nc h a p t e rf o u r ，as p e c i a lh a s hf u n c t i o n g e n e r a li z e db o o l e a n f u n c t i o ni si n t r o d u c e d g e n e r a l i z e db o o l e a nf u n c t i o n sw i t hh i g h n o n li n e a r i t yp l a ya ni m p o r t a n tr o l ei nc r y p t o g r a p h y ，s e q u e n c e sa n dc o d i n g i i i t h e o r y ，e s p e c i a l l yi ns t r e a mc i p h e r i nt h i sc h a p t e r ，r e p r e s e n t a t i o na n d s o m et r a n s f o r mo fg e n e r a l i z e db o o l e a nf u n c t i o na r eg i v e n ，a n ds o m er e s u l t s o fg e n e r a l i z e db o o l e a nf u n c t i o n sa n dg e n e r a l i z e db o o l e a nf u n c t i o n sw i t h p e r f e c tn o n lin e a r it ya r eo b t a i n e d k e y w o r d s ：p e r f e c th a s hf a m i l y ；s e p a r a t i n gh a s hf a m i l y ：g e n e r a l i z e d b o o l e a nf u n c t i o n i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者： 钍李 日期：川年j 月3 0 日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门 或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学 可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印 或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文 或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大学。 保密论文在解密后应遵守此规定。 学位论文作者： 韶丢碜 日期：? 伽呻年s 月乡d1 9 第1 章绪论 1 1 背景介绍 信息的传递与保密是人类活动的一个重要内容随着人们生活水平和科学技术的发展， 信息的传递与保密变得越来越重要，从安全性的角度来考虑：主要包括信息的保密性、完 整性、可用性、认证性和不可否认性密码技术是保障信息安全的重要内容密码学是研究 信息加密的一门学科，有着悠久的历史几千年前就有古人运用简单的加密手段传递秘密信 息的历史记载在第一次与第二次世界大战中，密码技术是各国重点研究和应用的技术，以 保障各种信息的传递随着计算机与通信技术的发展，人们开始考虑通过计算机和通信网络 安全地传递信息和方便快捷地做好各项丁作，使得密码技术广泛应用于计算机和通信网络的 各个方面，也进一步促进了密码技术的发展 传统密码技术大多是密码学专家凭自己的直觉来进行密码的设计1 9 4 9 年，美国著名 的密码学家s h a n n o n 发表了保密系统的通信理论一文，文章从信息论的角度研究了信息 加密系统的安全性和设计准则，从此，密码学成为了系统科学的一个重要分支上世纪7 0 年代，i b m 公司设计出数据加密标准( d e s ) 一分组密码算法，1 9 7 7 年，被美国联邦政府采纳 为联邦信息处理标准几乎同时，d i f f i e 和h e l l m a n 在密码学的新方向一文中从理论 上解决了对称密码系统的密钥分配问题，并进一步提出了数字签名的新思路1 9 7 8 年， r i v e s t 、s h a m i r 和a l d l e m a n 设计出了公开密钥加密和签名方案- - r s a h a s h 函数就是从有限集到有限集的映射密码设置也是从有限集到有限集的映射，因 此，任何一种密码都可以表示为一个或一组h a s h 函数一个安全的h a s h 函数应该满足以 下几个条件： ( 1 ) 输出串长度足够大，主要是为了抵抗生日攻击 ( 2 ) 对每一个输入值，h a s h 值容易计算 ( 3 ) 对于给定的h a s h 函数和h a s h 函数值，求原像在手工计算上是不可行的 ( 4 ) 对给定的h a s h 函数和一个输入值，找到另一个输入值，使得它们的函数值相同 在计算上是不可行的( 主要是为了抵抗第二原像攻击) ( 5 ) 对给定的h a s h 函数，找到两个不同的输入值，使得它们的函数值相同，在计算 上是不可行的( 主要是为了抵抗碰撞攻击) h a s h 函数主要应用于各种密码的设置，例如：认证算法构造、口令保护、比特承诺协 议、随机数生成和数字签名算法等h a s h 函数的算法最著名的有肋系列和s h a 系列密码 算法，很久以来，人们认为肋系列和s h a 系列密码算法是足够安全的，被广泛应用于网 络通信和密码设置中2 0 0 4 年，我国山东大学的密码学家王小云教授和她的团队将m d 4 的 碰撞攻击复杂度时间降到手工可计算，并将寻找m d 5 算法实际碰撞的复杂度和s h a 一1 算法 碰撞的理论复杂度分别降为2 ”和2 6 3e 1 - 2 她们的工作使人们开始怀疑如系列和s h a 系列密码算法的安全强度，迫使人们研究新的h a s h 函数算法设计方法，吸引了众多学者研 究h a s h 函数，寻找安全程度更高的h a s h 函数和h a s h 函数族 秘密信息检索( p r i v a t ei n f o r m a t i o nr e t r i e v a l ，p 瓜) 方案是密码学的一个典型的问题p i r 方案是在1 9 9 5 年由c h o r 、g o l d r e i c h 、k u s h i l c v i t z 和s u d a n 提出的p 取方案可以表述为这 样一个模型：有k 个服务器( 它们之间是互不联系的) 同时储存了n 个比特的数据，用户希 望获得其中某个( 如第f 个) 比特的数据，同时又不向这k 个服务器泄漏关于数据f 的信息 关于秘密信息检索的主要研究课题是如何构造这样的方案，使其通信复杂度最小许 多学者f 3 7 】对此作了深入的研究 显然，我们可以让服务器发送所有数据给用户，用户可从这些数据中找到所需的数 据这是个平凡的p i r 方案，它的通信复杂度是d ( 刀) ，当数据量很大时，这是不可取的 下面我们考虑一个实例( 文献 4 5 】) ： 例1 1 1 假设“表示用户，墨和是表示两台服务器( 假定它们之间是互不能通信 的) z = 毛恐以1 ) ”是同时存储在服务器上的一串信息记印】= 1 ，2 ，刀) 对集 合，与元素a ，令 ，。口：j ，u 口)耋口诺， i ， 口 若a i 用户为了获得第f 个信息玉，他可以随机选取集合4 【甩】，然后把彳发送给服务器墨， 把彳o 磅发送给服务器是；服务器墨将信息乃= o 扣_ x j 返同给用户，服务器最将信息 y 2 = 0 ，。f 返回给用户显然有 y t0 儿= ( o ，。一t ) o ( 0 ，。一科) = o ，。由j | 。f = 五 因此用户通过计算乃。咒便可得到需要的信息玉这个过程中两个服务器是无法知道关于 f 的信息的 这是一个简单的2 个服务器的p i r 方案，它的通信复杂度也是o ( n ) ，和平凡的p i r 方 案相比没有实质的改善然而，正是这个简单的模型作为基础，c h o r 等【8 】利用纠错码等方 法，给出的一个2 个服务器的构造，其通信复杂度为o ( n 3 ) i s h a i 和k u s h i l e v i t z 1l 】构造 了七( 后 1 ) 个服务器的方案，其通信复杂度为o ( k 3 n “2 卜1 ) 我们知道，在有噪信道中，信息在传输过程中可能产生错码所以，上述实例中，如 果用户给服务器发送信息或服务器给用户发送信息的过程中，由于传输原因引起的错误就会 使用户无法真正得到玉 为了解决上述问题，b e i m es t a h l 9 】利用了完全杂凑函数族( p e r f e c th a s hf a m i l i e s ，p h f ) 的性质研究了一种称为加强p i r 方案( r o b u s tp r i v a t ei n f o r m a t i o nr e t r i e v a l ) 构造一个新的 p i r 方案，这个方案保证只要有k 个服务器( 共，个服务器) 在传输过程中不出现错误，用 户就可以获得想要得到的信息完全杂凑函数族在p i p 方案中的优异表现，引起了人们对 它的重视 完全杂凑函数族是由m e h l h o r n 1 0 在研究编译器设计( c o m p i l e rd e s i g n ) 时时提出的上 世纪末，许多密码学家对这类函数族进行了研究，使得它们在计算机各个领域有了广泛的应 用近几年，人们又发现完全杂凑函数族在密码学方面的许多方面的应用，例如：广播加密 【1 l 】、密秘共享和门限密码【1 2 】、密钥分配和安全f p 码 1 3 1 等 2 1 2 主要研究问题与结果 设有限集x 与】，的阶数分别为n 与m ，f 为从x 到】，的一个映射，称厂是一个 伽，m ) h a s h 函数，h a s h 函数的集合称为h a s h 函数族( h a s hf u n c t i o nf a m i l y ) ，记为f 所有的 f ：x 专】，的集合记为，并显然，fcf z ”，if x rl - 掰“假设疗是聊的倍数，如果 对任意y y 均有i 扛l x = f - 1 ( y ) ，x x ) l = n m ，我们称是平衡的 么=c口，。=口ali。口a12：alnann， 么= ( 嘞) 胁= i 口i 口2 3 4 = ( ) 缸，= 1 3 1 ；2 23 23。232 3 3 3l23l2 l 23 312231l 2323131 2 j 令x = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ) ，y = 1 ，2 ，3 ) 对于1 f 4 ，定义函数 彳( ) = a j ( 1 j 9 ) 我们可以验证：f = 石，五，石，丘) 便是一个脚( 4 ；9 ，3 ，3 ) 关于完全h a s h 函数族的研究主要包括两个方面： ( 1 ) 完全h a s h 函数族的结构 对于f 的结构是完全杂凑函数族的一个主要的研究课题，已经有许多学者如 b l a e k b u m 、w i l d 、m e h l h o m 、f r e d m a n 、k o m l o s 、s t i n s o n 、a f i c i 等都对p h f 的构造作了大 量的研究我们在本文中，主要利用矩阵和图论的方法研究与w 较小的完全h a s h 函数族 的结构，主要得到了2 w 4 时p h f ( 3 ；n ，m ，w ) 的一些结构定理主要结果如下： 垦同构 其中局：r a6 2 a 岛a ：圾a 6 ，q 勺( ，j ) ； lc lc 2 岛q 岛= 萎薹萎；茎 q 吩，c 岛，q ，c 包，巳，cz ， 4 赢l o g n m ( m ，w ) i 们l 。g 棚i l o g 我们可以看到，当m 和w 同定时，n ( n ，m ，w ) 是一个关于n 的函数o ( 1 0 9 n ) 2 分离h a s h 函数族( s e p a r a t i n gh a s hf a m i l y ) 设f = 石，五，厶) 为x 专】，的一个h a s h 函数族，q ，c 2 ，e 是x 的互不相交 的子集，且lqi - w l ，ic 2 | - w 2 ，iei = w 如果对于任意的c 与qo j ) ，至少存在 一个函数厂f 使得： 厂( 口) i a c ：) n 厂( 6 ) i b q ) = 称f 是一个分离h a s h 函数族，记为s h f ( n ；n ，m ， ，w 2 ，w ) ) 一般地，对分离h a s h 数族s h f ( n ；n ，m ， w ，w 2 ，w ) ) 的研究分为三个方面： 分离h a s h 函数族s h f ( n ；n ，m ， w ，w 2 ，w ) ) 的结构问题； 给定m 与 w ，w 2 ，w ，求疗与的关系，分两种情况：- - + 是给定n 求的最 小值，另一个是给定求玎的最大值； 特殊类型的分离h a s h 数族s h f ( n ；n ，m ， w l ，w 2 ，) ) 的应用 本文中研究了一些与w = 嵋+ w 2 + + w 较小的s h f ( n ；n ，m ， w l ，w 2 ，w ) ， 得到了一些结果我们分析了与w 较小的分离h a s h 函数族的结构与界，利用矩阵和图 论，给出并证明了p h f ( 3 ；n ，m ， 2 ，2 ) ) 的结构和p h f ( 5 ；n ，m ， 3 ，3 ) ) 的界 3 广义布尔函数 布尔函数是研究0 、1 这两个量之间的逻辑运算的一门学科，是以它的创始人乔治布 尔( g e o r g eb o o l e ) 的名字来命名的在此基础上发展起来的表示逻辑的函数称为布尔函 数布尔函数的严格定义是：从g f ( 2 4 ) 到g f ( 2 ) 上的函数或映射它是研究数字逻辑电 路的重要数学工具，也是研究密码学、密码技术和编码的重要工具人们在研究中取得了丰 富的成果t o b e t h 与c d i n g 在文献 2 8 ，3 0 ，4 0 q b 研究t ) l 乎完全非线性序列与完全非线性 函数的性质与计数及其在密码的编制与传输方面的应用；c c a d e t 在文献【2 9 】中列举了b e n t 函数( 完全非线性布尔函数) 一些最新结果和应用方法；e j m a c w i l l i a m s 与n ，j a s l o n e 在文献 3 8 】中研究了利用布尔函数的非线性性编制纠错码的方法：a m k e r d o c k 在文献 1 0 】 中研究了利用布尔函数进行非线性编码；t w c u s i c k 与v s p l e s s 等在文献 3 1 ，4 3 中利用布 尔函数构造密码序列等等我国密码界也对布尔函数进行研究( 4 1 - - 4 3 ) ，他们主要研究布尔 函数的线性性( 4 l ，4 4 ) ，满足某些条件的函数的计数( 4 3 ) ，相关免疫性( 4 2 】，布尔函数 在密码学中的应用( 4 2 ，4 4 ) 等 我们研究了一类特殊的h a s h 函数广义布尔函数。非线性广义布尔函数在密码学与编 码理论中有重要用用，特别是流密码本文中，主要研究了广义布尔函数的表示方法、性质 5 和变换等研究了非线性广义布尔函数的问题，将布尔函数的性质推广到广义布尔函数，给 出并证明了下述几个结论： 3 一1 设厂为g f ( 3 ”) 到g f ( 3 ) 上的广义布尔函数，则厂( x ) = s ( w ) ( - o 。叫 w = o 设e 是么的任意一个子群，、口。为a 任意两个元素，则有： z , 。( a o ) f p ( a o + a ) = te 上i 如( 口o ) ( 口) 缈( 口) a c a o + e i 4 e a o + e 设。是从有限域g f ( p “) 到g f ( p ) 的厂义布尔函数，对于任恿a g f ( p ”) ， ic yn ( q + 。- a ) l 6 g f ( p ) ，则有：p d 。厂( 工) = 6 ) = 竺丝塑旦l 万- 设厂是从有限域g f ( p “) 到g f ( p ) 的广义布尔函数，如果 gb g f ( p ) ) 是一 个( p 4 ，p ，p ”1 ) 覆盖，即厂是完全非线性函数记l qiy g f ( p ) ) l - k y ，则对于任意 a g f ( p ”) 、b g f ( p ) 有： 砖= p ” 砖砖+ 。= p ”1 “- 1 ) 砖= 旷1 p ”+ p 一1 ) 设厂是从有限域g f ( p “) 到g f ( p ) 的广义布尔函数，如果厂为完全非线性的，则对 任意6 g f ( p ) 有：p 川一、二丽 ，y = 1 ，2 ，m ) ，f = 彳，五，厶) ，a 为h a s h 函 数族f 的矩阵图g ( a ) 称为h a s h 函数族f 的图，其点集为x = l ，2 ，咒) ，其边由以下 方式确定：如果存在= z ( _ ) = z ( 以) = 口魄( 1 ，n ，z 五) ，i s j 点j , 与点五有一 条边相连，并用第，种颜色染色 例2 1 5 可以帮助理解该定义 7 例2 5 矩阵彳= 季季三薹 表示一个只二c 3 ；4 ，2 ，2 ，其图g c 么，为： ( 3 ) 图2 i ih a s h 函数族的图 其中圈中的数字表示点的编号，括号内的数字表示边的颜色编号，即矩阵的行号 显然，如果知道h a s h 函数族的矩阵，将其图做出来是容易的因此我们可以利用矩阵 和图论的方法来研究h a s h 函数族 如果两个图日与g 满足：v ( h ) 矿( g ) ，以h ) 以g ) ，厶是严格要求下的厶， 称日是g 是子图图2 1 1 中：由染色为( f ) 边构成图就是g ( 彳) 的子图，记为q ( 彳) 置 是x 的一个子集，由置以及与五两个点相连的边构成的图也是g ( a ) 的子图，记为g ( 4 ) 定义2 1 6g ( 彳) 与g ( b ) 是h a s h 函数族h f ( n ；n ，m ) 的两个图，彳与召是对应的矩 阵，如果g ( 彳) 与g ( b ) 同构，称4 与b 同构 2 2 完全h a s h 函数族的结构 根据定义2 1 2 、定义2 1 3 和定义2 1 4 易得定理2 1 1 ，定理2 2 2 和定理2 2 3 ： 定理2 2 1 图g ( a ) 是h a s h 谳h f ( n ；n ，m ) 的图，则q ( 4 ) o = 1 ，2 ，) 为简单 图 因为g ( 么) 中任意两个点最多有一条边相连 定理2 2 2 图g ( 彳) 是h a s h 函数族h f ( n ；n ，m ) 的图，如果第，个函数的函数值全相 同，则g ，( 彳) 是完全图 这是因为g ，( 彳) 中任意两个点都有且仅有一条边相连 r 定理2 2 3 如果图g ( a ) 是一个p h f ( n ；n ，m ，w ) 的图，那么图g ( 彳) 也是一个 至三 ， 三 三 三 ， 三 至 三 兰 三三 三 ， 三 至 三 三 f ，、1 l 二乏j 证明：彳是一个p h f ( n ；n ，m ，2 ) 的表示矩阵的充要条件是a 中任意两列不相同，即 任何两列构成的子矩阵不与上面的矩阵同构口 对于一个p h f ( n ；n ，m ，叻的图g ( 彳) 与表示矩阵彳，图g ( 彳) 的连通分支对应的矩阵 9 a 的子矩阵称为矩阵a 的连通分支设4 与4 为a 的两个连通分支，g ( a ) 中c ( 4 ) 与 g ( 4 ) 无边相连，对于矩阵彳满足下列性质：对所有的， l ，2 ，册有 以i 4 l q a qi ，4 ) = 在证明主要定理之前，先证明引理2 2 8 引理2 2 8 如果图g ( 么) 是一个p h f ( 3 ；n ，m ，叻( 以 m ，w 2 ) 的表示图，且g ( 彳) 是连 通的并含有三种颜色的边，则g ( 彳) 只可能有下列三种类型的子图： 三角形，三边颜色都相同或三边颜色都不同； 一条长度为3 的路，且三边颜色都不同； 一个三条边的星，且三边颜色都不同； 两种颜色交替的双色路 证明：设g ( 彳) 中，u v 为第一种颜色的边，v w 为第二种颜色的边，砂为第三种颜色 的边，记d = m i n d ( u ，功，a ( u ，y ) ，d ( u 功，d ( v ，j ，) ，c l ( w , x ) ，d ( 嵋y ) ) 如果d = 0 ，则x 与y 中至少有一个是与“、v 、w 的点重合，不难判定一定是引理 中的三种类型之一 如果d = 1 ，则一定有一条边荭或秒，z 恤，1 ，w ) ，不失一般性，不妨设盟是一 条边，则有下面9 种情况： ( 1 ) z = ”，尉为第一种颜色，则u v 与侬都是第一种颜色，u 1 x 为第一种类型，w v x y 为第二种类型； ( 2 ) z = u ，荭为第二种颜色，则y x u v 为第二种类型； ( 3 ) z = “，及为第三种颜色，则u x y 为第一种类型，x u v w 为第二种类型； ( 4 ) z = v ，嚣为第一种颜色，则“w 为第一种类型，w v x y 为第二种类型； ( 5 ) z = ，荭为第二种颜色，则1 m w 为第一种类型，u v x y 为第二种类型； ( 6 ) z = 1 ，嚣为第三种颜色，则v x y 为第一种类型，u v w x 为第三种类型； z = w 的三种情况类似于z = u 的三种情况 如果d = 2 ，不失一般性，不放设d = d ( “，力，则一定存在点z 正 ，w , y ) ，u z 与荔 是两条相邻的边u g 与弘颜色不能相同( 如果相同，则螂为一条边，与d = 2 矛盾) ，也 不能为第三种颜色( 不然，与假设矛盾) ，故u z 与弘颜色为第一、第二两种颜色如果u z 为第一种颜色，则u v z 为同色三角形；如果坛为第二种颜色，则荭为第一种颜色，则u z x y 为第二种的三色路 如果j 2 ，不失一般性，不放设：d 。= d ，x ) ，设尸连接为u 与x 的最短路，且尸 的边不能同色，也不能为第三种颜色，相邻的两条边不能同色，则这条路上与x 相邻的两个 点和j ，构成一条三色路因此，这条路p 一定是条双色路 口 1 0 e = 主墨差i 差 其中2 5 i ，c ：f c j ( i 歹) ； 岛= 萎茎至量茎 其中q a j ，( 岛，q ) ( 岛，c j ) ( i j ) 由于彳p h f ( 3 ；n ，m ，4 ) 的表示矩阵，由定理2 2 6 知，g ( a ) 为简单图设g ( 4 ) 为 6 ( a ) 的一个连通分支，4 为矩阵爿的对应的连通分支如果6 ( 4 ) 中的边是同色的，则4 c ( 4 ) 中含有三角形子图，其三条边要么同色要么是三种颜色，则4 必有子矩阵同 ( 至三至 或 三善三 习 g ( 4 ) 含有一个三边星子图，三边颜色不同，则4 必有同构于 刁 的子矩阵，由定理2 2 5 知，么不是p h f ( 3 ；n ，m ，4 ) ，矛盾 o f 4 ) 含有一条双色路，则4 f 必有同构于e 设五、毛、x 3 、x 4 是x 的任意四个元素，我们分下列两种情况： 五、屯、x 3 、x 4 属于彳的同一个连通分支4 ，而4 与且或垦或马同构，故彳必为 五、屯、x 3 、x 4 属于彳的不同的连通分支，不失一般性，不仿设五、屯4 ， 毛、x 4 4 ，有下列三种情况： ( i ) 4 与4 均同构于e ，其子矩阵在同构的意义下可表示为： 三差塞主 或 差差兰兰 由于卧6 2 、岛、6 4 互不相同，c l 、c 2 、c 3 、q 互不相同，故a 必为p h f ( 3 ；n ，m ，4 ) 的表示 ( i i ) 4 与4 均同构于垦，其子矩阵在同构的意义下可表示为： 至茎至圣 或 茎茎圣兰 由于a l 、a 2 、a 3 、a 4 互不相同，( 6 l ，c i ) 、( 吃，c 2 ) 、( 6 3 ，c 3 ) 、( 6 4 ，c 4 ) 互不相同，故a 必为 1 2 宰 6 宰 口 奎 搴 口6 c ，。一 刳 由于6 l 、如、岛、么与c i 、c 2 、c 3 、c 4 必有一组互不相同，故彳必为p h f ( 3 ；n ，m ，4 ) 的表 示矩阵； 综上所述，充分性得证 口 注：文献e 1 8 有相似的结论，但证明方法不同 2 3 完全h a s h 函数族的界 为了保持内容的完整，本节介绍了完全h a s h 函数族的上界与下界，即n 、m 与w 固定， n ( n ，m ，w ) 的上界与下界问题我 i f y u 举了目前最好的一些结果其次，介绍了一些与w 较小的完全h a s h 函数族的界的问题 关于完全h a s h 函数族的上界与下界，m e h l h o m 在【1 0 】中给出了著名的三个结果，为了 方便阅读，在定理2 3 1 ，定理2 3 2 和定理2 3 2 重述这三个结果和证明方法 定理2 3 1 如果存在p h f ( n ；n ，m ，w ) ，则 ( m ，w ) 掣 1 0 2 m 定理2 3 1 中的界在w = 2 时等号成立事实上，在【1 0 】中还指出，对于任何n m ，存 在一个构造使得：c 以，m ，2 ，l 。l 。o g g 掰n 定理2 3 2 如果存在肿( ；以，m ，w ) ，则 脚朋叻臀 推论2 3 4 如果存在脚( ；力，脚，叻，则( 刀，研，w ) - n , + 2 厄 又由于m d ( r ，f ) ，刀= 吩，则有： 3 m t m 卅d ( 2 ，卅d ( 3 ，f ) 】t ( 啊+ 2 厄) = 刀+ 2 壹厄以+ 2 石 不难解出：刀3 聊+ 2 2 ! 丽 口 根据上述定理，我们可以给出。f 述两个推论，这两个结论在文献 1 9 中有类似的结论 推论2 3 7 1 1 9 】如果存在册( ；刀，朋，4 ) ，则 以3 历纠+ 2 2 ；而 推论2 3 8 1 9 对于任意正整数刀，存在肿( 3 ；3 疗2 ，刀2 + 2 n ，4 ) 证明：下面我们构造一个矩阵彳，使它为p h f ( 3 ；3 n 2 , 一2 + 2 n ，4 ) 的表示矩阵首先使 a 有三个连通分支。每一个连通分支有刀2 列，而且每一个连通分支同构于易 第一个分支构造如下：第一行放n 2 个不同元素，第二行与第三行# rn 个不同元素； 第二个分支构造如下：第二行放玎2 个不同元素，第一行与第三行放，1 个不同元素； 第三个分支构造如下：第三行放刀2 个不同元素，第一行与第二行放以个不同元素； 这样可以使得彳为p h f ( 3 ；3 n 2 , 玎2 + 2 n ，4 ) 的表示矩阵 口 1 4 t：=ca。，。=、al!a12a1，n： 4 ：( 嘞) ： i 、 ，。 ( 2 ) 给定所与 w ，w 2 ，嵋) ，求栉与n 的关系一个是给定，l 求的最小值，另一 个是给定求刀的最大值； ( 3 ) 特殊类型的分离h a s h 函数族s h f ( n ；n ，m ， ，w 2 ，嵋) ) 的应用 下面我们举例说明分离h a s h 函数族s = 职( ；胛，m ， ，w 2 ，w ) ) 的应用 如果分离h a s h 函数 s h f ( n ；n ，m ， w ，w ) ) 中w = 也= = 嵋= l ， 它就是著名的完全h a s h 函数族p h f ( n ；n ，m ，f ) ，对其研究已有很长的时间， 我们在上一章已经做了一些研究其结果可参见文献【9 ，1 9 】 f p 码( f r a m e p r o o fe x , d e s ) 就是一类分离h a s h 函数族s h f ( n ；n ，m ， l ，w ) ) ， 理： 研究成果见文献 2 1 2 5 1 安全f p 码( s e c u r ef r a n e p r o o fc o d e s ) 就是一类分离h a s h 函数族 s h f ( n ；n ，m ， w 以) ，研究成果见文献 2 5 ，2 6 1 口p 编码( i d e n t i f i a b l ep a r e n tp r o p e r t yc o d e $ ) 是分离h a s h 函数族 s h f ( n ；n ，m ， 1 ，l ，1 ) + 2 ，2 ) ) ，研究成果见文献 2 5 ，2 7 本章研究一些与w 较小的分离h a s h 函数族册( ；珂，m ， w ，w 2 ，w ) ) 结构和给 定的情况下，n 的取值的最大值 3 2 分离h a s h 函数族结构 我们首先根据完全h a s h 函数族、分离h a s h 函数族定义和矩阵的概念易得下面两个定 定理3 2 1 如果矩阵彳是p h f ( n ；n ，m ，w