（应用数学专业论文）密钥预分配方案及正交阵列.pdf

摘要 本文的结果有两部分t 一、基于有限域上的有理正规曲线，构造了一种密钥预分配方案，并给出了实现过程 = 、基于二元域上的r 维向量空间在构造正交阵列方面的应用。我们研究了正交阵列 o a a ( t ，n ，”) ( 参见定义3 1 ) 在_ = 2 时的情形，得到了如下结果 1 解决了t = 3 时的情形( 定理3 3 ) ； 2 完整地解决了平凡时的情形( 定理3 6 ) 另外，还得到了一类强部分平衡设计( 参见定义2 1 ，2 2 ) i 见定理3 2 ， f 、， a b s t r a c t 0 u rm a i na c h i e v e m e n th a v et w op a r t s ： f i r s t w ec o n s t r u c tak e yp r e d i s t r i b u t i o ns c h e m eb a s e do nr a t i o n a ln o r m a l c u r v e so v e rf i n i t ef i e l d s ，a n dg i v et h ep r o c e s so f r e a l i z i n gi t s e c o n d ，b a s e do nt h ea p p l i c a t i o no fc o n s t r u c t i n go r t h o g o n a la r r a y sw i t h v e c t o rs p a c e so fd i m e n s i o nro v e rf 2 ，w em a k es o m er e s e a r c ho no r t h o g o n a la r r a y s o a x ( t ，n ，v ) ( d e f i n a t i o n3 1 ) i ne a s eo fv = 2 ，a n dg e ts o m e r e s u l t sa sf o l l o w i n g ： 1 s o l v et h ec a s et h a tt = 3 ( t h e o r e m3 3 ) ： 2 s o l v et h et r i v i a lc a s e ( t h e o r e m3 6 1 o t h e r w i s e ，w eg e ta n e w f a m i l yo fs t r o n gp a r t i a l l yb a l a n c e dd e s i g n s ( d e f i n i t i o n 2 1 ，2 2 ) ：t h e o r e m3 2 前言 本文有两方面的内容密鲷预分配方案和正交阵列 一、密钥预分配方搴 随着信息技术的发展，计算机网络已经成为一个很普追的通信工具在这个网络世界 里，信息资源的共享和交流是非常方便的，但是，与此同时，网络的安全性也成为越来越 严重的问题网络的安全性问题是多方面的，例如信息传输时的窃听泄密问题、对信息窜 改、破坏问题、病毒注入问题以及。黑客。入侵问题等本文涉及到的是网络传输中的秘 密共事方面的一个问题t 密钥分配问题 在网络与通讯中，密钥分配一直是个关健的问题一般地说，网络总是广播式的，即 在网上传输的任何信息都能被其他用户看到为了保证信息的安全性与完整性。一种做法 就是广播加密。即加密后的信息只能被授权的特权用户子集中的用户读懂。而其他没被授 权的用户看到的只是毫无意义的东西，这样就需要对密钥进行预分配使得被授权的特权 子集中的每个成员都能够计算加密密钥( 注，我们考虑的是对称密码体制，加密密钥也是 解密密钢) ，从而可以获得明文信息，而没被授权的禁止子集即使勾结起来也无法计算加 密密钥也就得不到明文信息 本文的第一个专题就是讨论密钥预分配方案我们在第一章中介绍了密钥顶分配方案 的概念以及常见的几种密钥顶分配方案lm i c h e u 和p i p e r 在 12 】中定义了密钥分配模式 k d p ( k e y d i s t r i b u t i o np a t t e r n ) ，s t i n s o n 在( 1 4 】，1 i 5 1 中说明用k d p 可以构造k p s ，我们将 在第二章中说明利用强部分平衡t 一设计( m ，卢) ( 这里( m ，卢) 如定义2 1 ，定义2 2 所示) 能够 得到k d p ( 见定理2 1 ) ，从而可以构造出k p s 裴定一教授在【8 】利用有限域上的有理正 规曲线构造了一批强部分平衡t 一设计，利用这个设计我们就得到了一类新的k p s 用正交阵列也可以构造x p s i i s ，同这种方法相比。用我们的方法产生的k p s 至少有 以下的优点 1 产生方法简单t a 可以根据面临用户的个数。选择适当的g 2 面向对象灵活t 若特权子集的成员较多，则只需将p g ( n ，晶) 的n 取得大一点即可 我们在第四章讨论了用有理正规曲线构造k p s 的实现，因此从理论上的构造到应用中 的实现。我们给了一个完整的描述 = 、正交阵列 正交阵列。作为一类基本的组合结构，无论在密码学方面。还是在组合论方面都有着 广泛的应用例如，正交阵列可以构造k p s ，认证码，弹性函数等因此，对正交阵列的研 前言 究一直是个很活跃的专题，很多人对正交阵列的构造与应用做了研究，如j b i e r b r a u e r 的 2 】。d l k r e h e r 的 1 0 】和c j c o l b o r u n 的【7 但总的来说，已知的构造正交阵列的方法 并不多 本文的第二个专题就是构造正交阵列在第三章，基于2 元域上的r 维线性空间在正 交阵列构造方面的应用，得到了一些结果， i 对于任意的r 3 ，存在一个正交阵列0 4 2 r - 3 ( 3 ，2 “1 ，2 ) 2 对任意的r 23 ，不存在c e ( 2 ) 上的r ( r + 2 ) 矩阵m ，使得m 的任意r 个列向量线 性无关 3 对于任意的r 5 ，r 维向量空间中的一组向量。若其中任意r 1 个向量线性相关。 则最多可有r - i - 1 个向量 4 完整地解决了平凡时的情形，见定理3 6 我们的结果是”= 2 的情形利用正交阵列构造的k p s ，每个用户所保存的信息量是 ”的一个方幂，从减少信息量的角度来看，取”= 2 时最好。这就是我们考虑”= 2 的原因 另外，在第三章中，我们还给出了一类强部分平衡设计，见定理3 2 感谢 。粤弘8 2 9 8 衷心感谢我的导师裴定一教授和翟起滨教授，无论在我的学习中还 是在我的生活中，他们都给予了我无微不至的关怀，使我得以顺利完成学 业我的每一点进步，每一份收获，无不凝聚着他们的心血；他们严谨治 学的精神、乐以助人的态度将深深地影响着我，并指导我怎样做学问，怎 样做人 衷心感谢戴宗铎教授，感谢她在我硕士期间给予的生活上的关心和 学业上的帮助，她的一丝不苟、严谨治学的态度将深深地影响着我 衷心感谢赵战生教授，戴英侠主任，荆继武主任。吕述望教授，刘振 华教授，感谢他们对我学业上的支持和生活上的关心 衷心感谢韩非平老师，徐惠云老师，感谢他们在生活上给予的帮助与 鼓励，使我克服了生活中的很多困难 衷心感谢张实老师，周新成老师，和陈兰小姐，他们在我的生活方 面，在我复印资料方面，打印资料方面都给予了大力的支持 衷心感谢唐步天，陈立志等同学在计算机方面给予的帮助 衷心感谢张玉峰，蒋绍权，陈伟东等同学及欧海文博士，在学习期 间，与他们的讨论使我受益非浅，他们给予我的帮助更使我永远难忘 最后还要感谢我的女友艾红玲女士，感谢她在我准备论文期间给予 的关怀与帮助 第一章密钥预分配方案 在这一章中，我们对密钥预分配方案( k p sk e yp r e d i s t r i b u t i o ns c h e m e ) 做一简要的介 绍，然后列举一些常见的密钥预分配方案。并分析它们的效率 1 1k p s 的定义 k p s 模型是由一个可信机构( t a t r u s t e d a u t h o r i t y ) 和一个用户集合( 用甜= 1 ，2 ，n ) 来表示) 构成我们总假定信息在网络上传输，而且网络是广播式通道，即任何由t a 或网 上的用户所发出的信息都能被其它用户看到，因而是不安全的 用表示所有用户子集的集合，层表示所有可能成为t a 允许计算秘密密钥的 用户子集所构成的集合，称为特权子集；，表示t a 禁止得到密钥的任何信息的用户 子集的全体，称为禁止子集设p 8 是一个特权子集，令如表示t a 与特权子集p 之 间共事的秘密信息 首先。t a 为每个用户产生一个秘密信息，并以公开密钥加密算法加密或者以秘密的 方式分发给每个用户。我们把分给用户i 的信息称为u 然后。按照某些公开的算法或者共同约定的算法，经过授权的特权子集p 中的每个用 户i p 都能计算共事的秘密密钥b ，同时被t a 禁止得到秘密密钥b 的任何信息的用 户子集( 称为禁止子集) f ，即使f 中的成员联合起来也无法得到 p 这样就达到了共事 秘密密鲷的目的 设p 8 。令k p 表示分配给特权子集p 的秘密信息的随机变量，巩表示用户i 所 得到的t a 分发给他的秘密信息的随机变量，如表示禁止子集f 中所有用户得到的秘密 信息的随机变量 从熵的角度看。( 8 ，) 一k p s 是指 1 任何特权集合中的用户i 能够计算出k ： h ( k p i 巩) = 0对所有的i p 1 3 2 任何与特权子集p 不相交的禁止子集f ，联合起来也不能计算关于b 的任何信息t h ( k p ) = h ( k p i u r ) 对所有的p 8 和f ，且使得p n f = 西 这里介绍一些简单的记法如果特权子集8 是由甜中所有的t 阶子集构成所构成的， 我们就简记为( t ，) 一k p s ，如果b 是由中所有的阶效小于t 的子集所构成，则倚记为 ( st ，) 一k p s 。类似的记法也适用于， 2 第一章密钥预分配方案 例如，一个( 3 ，1 ) 一k p s 是指每一个特权子集p = a ，b ，c ) 能得到秘密信息k p ，而用户 j p 就得不到b 我们约定u g 日，g f ( q ) 为有限域，g 为一个素数的幂，并且可信机构t a 随机地 选取k p g r ，因而有h ( k i , ) = l o g 口 我们用以下概念来度量一个k p s 的效率t 一、信息率t ，刊n 涮。娜n ) - 棚n 端：1 娜n ) 二、总信息率 一h ( k p ) 一l o g q p t 3 h ( v u ) 2 可丽 三、用户存储i 的信息量， k ：掣 i o g g 注前两个是一个相对的概念，描述计算共事秘密信息的效率l 后一个绝对地描述用 户所存储的信息量我们在设计k p s 时，总希望让这三个量都比较小 1 2k p s 的构造 本节列举了一些k p s 的构造方案，并以定理的形式分别街量了其效率 1 2 1 平凡方案 定理1 1 对于任意的t 1 ，存在一个( ，n ) 一k p s ，它的信息率为， l 胪丽 总信息丰为t 1 灯2 西 每个用户所存储的信息量均为 k = c 二：) 对于任意的1 s i s n 证明t 对于每个t 一子集p g u 。t a 随机选撵b g f ( q ) 并且把b 交给p 中的 每个用户即可 5 1 2k p s 的构造 1 2 2 b i o t as c h e m e 定理1 2 对任意的u21 。存在一个( 2 ，s u ) 一衄唱信息丰为 总信息丰为 每个用户所存储的信息量均为， 1 p2i 万 1 刀2 而 k = u + 1 对于任意的1 i n 3 证明t 设q n 是一个素数的幂，t a 随机选择n 个整数s i g f ( q ) 并将s i 交给用户 i 。这不比是秘密的然后t a 随机选择一个多项式 其中a i j g f ( q ) ，且8 0 = d j 对于任意的1si n 。t a 计算 “ 们( z ) = m ，础) = b q z j = 0 将这u 个系数交给用户i 则与p = “j ) 相关的密钥是 b = g i ( s j ) = 9 j ( s 1 ) = ，( 巩，q ) 而信息率的计算是倚单的，这里从略 注，取，为t 元对称多项式 a i ，俨 z 2 i = 0 可以很容易地将此方案推广为( t ，su ) 一k p s 的情形，可参阅f 3 】，这里从略 1 2 3 f i a t - n a o rs c h e m e 定理1 3 对于任意的c ，21 ，则存在一个( sn ，。) 一k p s 信息丰为 1 胪丽i j = 0 。 矿 产 。 = o ， 。 i | 4 第一章密钥预分配方案 总信息率为 ( ；) 每个用户所存储的信息量均为 k = 薹( “i 1 ) 对于任触绑n 证明对于任意的f ，。f 至多有u 个元素，t a 随机选择s f g f ( q ) ，并将s f 交给1 2 f 的每个用户，对应于特权子集p 的密钥定义为t 如= s ， f e ，f ，n p = ) 对于f ，且f n p = ，因为f 中的成员都不知道s 尸，故它们合起来也不能得到b 1 2 4k d p 方法 m i c h e l l 和p i p e r 在【12 】中定义了密钥分配模式( k d p ，k e yd i s t r i b u t i o np a t t e r n ) ，s t i n s o n 在【14 】i 【1 5 】说明利用k d p 可以构造k p s 定义1 1 令z ，= t 1 ，2 ，n ) 为用户采，卢= b l ，口2 ，b b ) 为用户子集的集合设f ， 是用户子集的集合，称，卢) 是一个( b ，) 一k d p ，如果对于所有的p 8 ，f y 且 p n f = 。都有 毋l p 马，f f l 岛= ) 设似，卢) 是一个( b ，t ) - k d p ，对于任意的i “，令r i = l 马h b j ) i ，则有如下定理t 定理1 4 若似，p ) 是一个( 召，) 一k d p 。则存在一个( 8 ，) 一k p s ，其信息率为， 1 9 2 忑币丌珂 总信息丰为t l 刀2 i 用户所存储的信息量，k = r i 证明对于1sjs6 ，t a 随机选择s j ，并将勺交给马中的每个用户对于每个特 权子集p ，与其对应的密钥如定义为t k p = s j j l p c _ 毋】 则每个用户i 拥有 个秘密信息并且p 中的每个用户都可计算i p ，而对于每个拒绝子 集f 。f n p = ，由定义知，至少存在一个区组岛。使得p 马，但f n 岛= ，因 此尸中的所有用户都没有5 j 。因而投法计算b 而信息率的计算是简单的证毕 i 2k p s 的构造 5 1 2 5 甩有限域上的有理正规曲线 利用有限域上的有理正规曲线，可以构造k p s ，详见下一章或参阅【1 7 1 2 6 用正交阵列o a ( o r t h o g o n a la r r a y ) 在第三章，我们还要比较详细的描述某些正交阵列的存在性 设y 是一个u 元集合，a = ( a i j ) 是y 上的a v n 阶矩阵( 其中a ，8 ，n 为1 的 整数) ，满足下面的性质t 对于任意的s 一元子集( u l ，u ) y 及对于矩阵a 的任意s 列，例如7 l ，h ，恰有a 的a 行，使得对于任意的1si s ，t t i 在竹上出现记为 o a ( s ，n ，”) ，若a = l 。就简记为o a ( s ，n ，u ) 设矩阵a 是一个正交阵列o a ( s ”) ，令卢= 矿，即矩阵的行数，用1 ，卢来表示行， 甩1 ，n 来表示列，我们定义用户予集“= l ，2 ，n ) ，令z y i z l _ ：，1 z s ”一1 ， 对任意的l j 卢，定义 马= 引口j 。z ) 并且令 8 = b 1 ，b 口) 令2 s t ss l ，记j = s t ，下面说明似，8 ) 是一个( t ，u ) - k d p 对于任意的p = ( i l ，i t ) t 3 ，f = ( i 1 ，i ) ，) ，p n f = ，我们的目的是找到 一个区组马，使得p 毋但岛n f = 取n l ，d 。gz ，毗+ 1 ，a 。z ( 这些元素不比互不相同) 由正交阵列的定义对于 选定的8 列t 第i l ，ii ，i 。列，有a 行，不妨记为，7 l ，讹，使得对于任意的 1 m s ，d 。在7 l ，一，似的第i 。列和出现，我们考虑巩。，首先，因为a 1 ，m z ， 所以用户i 1 ，i l 在目。中，即p = ( i l ，i i ) s 岛；另一方面，因为a t + l ，a z ， 即用户i 件l ，i 不在b 。里故马n f = 即似，3 ) 是一个( t ，w ) - d k p 因而可以构造 密钥预分配方案k p s 因为y 中的每个元素的矩阵a 的每列中出现卢加次，所以w y 中的元素在矩阵 的 每列中出现掣次，即 n = 垒学 如果不考虑使用弹性函数来提高信息率。则这种信息率为 i 9 5 而s ；2 a v s - t 第一章密钥援分配方案 1 3 一个用正交阵鄙构造k p $ 的例子 取 = o ，1 ) 。我们有一个o a ( 4 ，5 ，2 ) 如下 00000 00 o11 0olo1 o1001 10001 00ll0 01010 10010 01100 1ol00 11000 l1110 1ll01 1l0l1 10111 01111 令z = 0 ) ，按照上一小节的方法，我们得到一个区组8 = b t ，阮，_ 8 1 5 ) 如下 b 1 = 4 ，5 )b 2 = 3 ，5 )b a = 2 ，5 )b 4 = 1 ，5 )b s = 3 ，4 ) b 6 = 2 ，4 )b y = 1 ，4 b 8 = 2 ，3 )b 9 = l ，3 )b l o = l ，2 ) b n = 1 ，2 ，3 ，4 ) b 1 2 = l ，2 ，3 ，5 ) b 1 a = 1 ，2 ，4 ，5 ) b 1 4 = 1 ，3 ，4 ，5 ) b i 5 = 2 ，3 ，4 ，5 ) 易知，b 是一个( 2 , 2 ) - k d p 。其中p = p i p 中只有两个元素) = 芦因此。我们可以 得到一个( 2 ，2 ) 一k p s ，用户个数为5 在开始阶段，信息中心r al 毫机选取勺g f ( q ) 。并将勺秘密地交给马中的每个用 户。对于任意的p p ，定义 b = 勺 j l p c _ b j 3 一个用正交阵列构造k p s 的饲子7 若有禁止予集f = 3 ，5 ) n f = ，虽然用户3 知道8 1 l ，s 1 2 。用户5 知道8 1 2 ，8 1 3 ，但他们 都不知道8 1 0 ，因而得不到“1 ，：) 易知，每个用户所存储的信息量都是= 8 3 s +2 s 上 s +o s | | 对k 财 田 1 ( = p 取如例 第= 章用有限域上有理正规曲线构造k p s 在这一章中，我们首先说明，利用强部分平衡t 一设计可以构造密钥顶分配方案k p s 然 后引入有限域上有理正规曲线的概念及其性质，由此构造出一批强部分平衡t 一设计 8 jl 最后，描述由此而构造的k p s 1 7 2 i 强部分平衡t 一设计 强部分平衡g 一设计的定义如下 定义2 1 令m 走一个含有 个元素的集合，p = b 1 ，b 2 ，b ) ，其中b j m ( j = 1 ，2 ，8 ) 是k 元子集，称为区蛆，我们称( m ，卢) 走一个部分平衡t ( _ ， ，a ，0 ) 设计是指， 对肘的任意t 元子集，要么在p 的任一区蛆不出现，要么在卢的a 个区虹中出现。( 其 中 ，t ， 都是整数) 定义2 2 - - + 部分平衡t 一( ，九，0 ) 设计( m ，卢) ，如果对任意1 r s t 也是一个部分平 衡r 一( 口，女，a ，0 ) 设计，则称( m ，卢) 是强部分平衡t 一设计，记为t 一( ”，i ， 1 ，九，0 ) 设 计 注t 若肘的任意t 元子集都在p 的a 个区组中出现。则称( m ，卢) 为t ( ，女，a ) 设计， 我们约定强部分平街设计( m ，卢) 的卢中没有重复的区组 利用强部分平衡t 一设计，能够得到k d p ，根据定理1 4 ，从而可以构造出k p s 设 ( m ，卢) 为一个强部分平衡一设计，对于isr t 。由定义。( m ，卢) 是一个r 一( ”， ，0 ) 设计 定理2 1 ( m ，口) 走一个强部分平衡t 一k ， 1 ，h ) 设计。对于1 sr t ，如果嘶 r + l a r 。则( m ，卢) 是一个( 辫，兰w ，) - k d p ，其中辫是所有在卢中出现的m 的r 一1 元子臬 证明t ( m ，芦) 是一个( r + 1 ) 一设计( r + 1 ) 一( ”，女，a r + 1 ，0 ) ，由定义它也是一个r _ ( ”，女，k ，0 ) 设计，任职p 研，p = i 1 ，i 2 ，i r ) ，则p 在p 中的区组中要么不出现。要么出现k 次， 设f = j l ，j 2 ，如，) ，p n f = 考虑集合s = i x ，i 2 ，一1 ，如) ，伸= 1 ，2 ，) 由 定义可知s 在p 的区组中最多出现a r + 1 次而嘶a ，+ 1 ( 1 r t ) 2 2 有限域上的有理正规曲线 利用有限域上的有理正规曲线可以构造强部分平衡设计。这种方法取自于【8 】，为了 结构的完整，在这里我们将对有限域上的有理正规曲线的性质给以详细而完备的描述 2 2 1 射影空问 记日是g 元有限域，其中口为素数幂，e g ( n ，) 为f 口上的n 维射影空间，它由 凡上所有n + 1 元数组x = ( z o ，x l ，。) ( 其中x o ，x l ，。不全为零) 组成，且x 与 a x = ( a z o ，a 。l ，a 。) 表示空间中同一个点 2 2 2 射髟变换 设t 是b 上的n + 1 阶非异矩阵，则映射t p g ( n ，日) _ p g ( n ，如) ( # g o ，。“，z n ) + 扛o ，1 ，x n p 为一一映射。称为p g ( n ，岛) 上的射影变换，p g ( n ，舀) 的所有射影变换构成一个群，记为 p g l n + 1 ( 局) 2 2 3 有理正规曲线 曲线c 0 为下面映射的像 p g ( 1 ，r ) _ p g ( n ，岛) ( x o ，z 1 ) 一( 3 ，z ；。z i ，? ) 显然c 0 上有g + 1 个点 ( 1 ，o t ，口2 ，口”) i 口日) u ( 0 ，o ，- 一，1 ) ) 我们称c o 在射影变换下的像为有理正规曲线 命趣2 1 有理正规曲残是如下映射的像 p g ( 1 ，日) _ p g ( n ，) ( z o ，1 ) 寸( a o ( 2 0 ，。1 ) ，a i ( x o ，x 1 ) ，a n ( 嚣o ，1 ) ) 其中a o ( z o ，1 ) ，a 1 ( 2 0 ，z 1 ) ，如( x o ，1 ) 是x o ，1 上n 次齐次多项式空间的任一姐基 1 0 证明设 第二章用有限域上有理正规曲线构造k p s a o ( = o ，z 1 ) = a o o z 3 + a l o x ：一1 虬+ + a n 0 2 仝 1x o ，1 ) = a o l 8 + a l l 。3 1 2 1 + + 口n l 。? a o ( x o ，1 ) = a o n 吕+ 8 i n 吕一1 z l + - + a n n z m a ( z 1 ) 0 ( 三i 三i 三a l ! n ) ( 三a 1 ) = 。 f 。( 。，z t ) ， t ( 吼)如x 0 1x 1 ) 1 = ( 。3 ，。；一1 z - 习 因此，这两种定义方式一致 2 2 4 有理正规曲线的性质 称点a = ( x d o ，z m ，z 。) ，“= 0 ，l ，m ) 是线性无关的，如果矩阵( 。玎) 。的秩是 m 引理2 1p g ( n ，日) 中有理正规曲线上的任意( 竹+ 1 ) ( nsg ) 个点都是线性无关的 证明利用范德繁行列式的性质可知。曲线岛上的任意n + 1 个点都线性无关，而 非奇异的线性变换并不改变向量之问的线性关系，因此射影变换不改变向量之间的线性关 系。命题证毕 ；l 印毗 一 o o 0 如虮 一 ，f，i_iii 贯 2 2 有限域上的有理正规曲线 引理2 2 假设q n + 2 ，则通过p v ( n ，f 口) 中任意n + 3 个点( 这n + 3 个点中任意n + 1 个点都是线性无关的) 。有且仅有一条有理正规曲线 证明t 设p i = ( x i o ，x l l ，z m ) ，i = 1 ，2 ，n + 3 ，取非奇异的射影变换t t 1 = 若令点p n + 2 在非奇异的射影变换丑作用下的象为t x p 。+ 2 = ( a o ，a l ，o 。) ，则必有 a o 0 ，8 l 0 ，a 。0 ，否则着嘶= 0 ，则p l ，p 2 ，p l 一1 ，p r , + l ，p l + 1 ，p n + l 必线性相 关再取射影变换t 2 ： 乃= e 0 d 二1 则通过射影变换n 乃使得这n + 3 个点有如下形式 p 1= ( 1 ，0 ，一，0 ) p 2= ( 0 ，1 ，0 ) ( 2 1 ) p 。+ 1 = ( 0 ，0 ，0 ) p n + 2 = ( 1 ，1 ，1 ) p n + 3 = ( v 0 ，u 1 ，一， n ) 其中巩( i _ 0 ，1 ，n ) 互不相同否则的话，一定可以找到n + 1 个线性相关的点令 ，。)=”(。一”ilxlg(zo 1 7 i = 0 ) ，吼( z 。，z - ) = 揣 ，。1 ) = ( 。o 一”i ) ，凰( z 1 ) = 嵩氅 hr ， 考虑a i h i ( z o ，z 1 ) = o ，f l i 晶，令( x 0 ，1 ) = ( 1 ，地) ，可知m = 0 ，( 15 i sn ) 因此 h i ( x o ，q ) “= 0 1 ，n ) 线性无关，从而为p g ( 1 ，& ) 上n 次齐次多项式空问的基 再考虑映射 6 ：( x o ，x 1 ) _ ( h o ( = o ，z 1 ) ，h l ( = o ，2 1 ) ，日n ( z o ，。1 ) ) o 0 。矿 1 2 第二章用有限蛾上有理正规曲线构造k p s 因为6 ( 1 ，地) = a ( 1s i n + 1 ) d ( 1 ，0 ) = p n + 2 ，d ( o ，1 ) = p n + 3 因此，由j 定义的有理正规 曲线通过上述n + 1 个点反之，对任意给定n + 1 个点，上述的6 是唯一的，因而有唯一 的一条有理正规曲线通过这些点 引理2 3 设n 2 为整数，g n + 2 是一个素数的幂则p g ( n ，日) 中共有g 掣一1 兀( 矿一1 ) 条有理正规曲线 证明考虑射影空问p g ( n ，f 口) 中所有满足下列性质的点集该点集含有n + 3 个元 素，其中任意n + 1 个元素线性无关设这些集合的个数为| 令 p 1 ，p ：，p n + 3 ) 是满足 条件的点集因为p g ( n ，r ) 中有( q “+ 1 一1 ) ( g 一1 ) 个点，故p 1 有( 矿+ 1 1 ) ( q 1 ) 种选 法，当p l , p 2 ，p ( 1 i n ) 选好后。与p l , p 2 ，一，p l 线性相关的点有( q 一1 ) ( q 一1 ) 个， 因此p 有 ( 口“+ 1 一1 1 ( q 一1 ) 一一( 口”+ 1 一一1 ) f 了q 一1 一；= 1 种选法 仿照引理2 2 。可以选取非奇异的射影变换n ，使得p l ，m ，“+ l 的象形如式( 2 1 ) 对于任意的“+ 2 = ( a o ，o 一，n 。) ( 其中啦0 ( 0 s i sn ) ) ，只须取射影变换b ， 0 0 a 二1 则射影变换t x t 2 可将p l , 砌，“+ l ，p n + 2 变为形如式( 2 1 ) 因而p n + 2 的取法有( q 一 1 ) n + l i ( q 一1 ) = ( 口一1 ) “种p n + 3 形如( b o ，b l ，b 。) 以0 ，虬6 ( 0si j n ) 因而有 ( q 一1 ) ( g 一2 ) ( q n 一1 ) ( q 一1 ) = ( q 一2 ) ( 口一n 一1 ) 种选法因此 ：皇! ：! ! ：! ：n 旦+ l ! ! 二! ：! 竺：n 娶+ l ! ! ：! ! ! ：二! ( n + 1 ) ! 一 ( n + 1 ) ! 而每条曲线上有q + 1 个点，鼠此p g ( n ，f q ) 上有 南= g 掣一1 ( g i ) 。 条有理正规曲线 一1 0 口 o l 一0 a 0 o ，。 l l 乃 5 2 3k p s 的性质 1 3 引理2 4 设5 是整数，对于任意的素数幂g t 一1 ，存在一个t 一( ，1 ，0 ) 设计，其 中u = ( 口“2 1 ) ( q 一1 ) ，女= g + 1 这也是- - 4 r 一( ，k ，k ，0 ) 设计( 3sr t 一1 ) 及 r 一( f ，k ，) 设计，r = 1 ，2 其中 a 1 ：g 掣一- 。宵( 一一1 ) k ：g 灶掣+ “l “i7 ( 矿一1 ) 。宵( 口一i ) ( 2 s ，t 一3 ) t 写1 1 ( 2 2 ) 儿一2 = ( q 1 ) ( “4 ) 兀( g i ) f 一3 悟l 沁一1 = n ( q i ) = 2 1 - 一2 ( 其中如果r = 2 时，1 1 ( q 一 ) = 1 ) 证明令m = p g ( t 一3 ，马) ，令p g ( t 一3 ，日) 上的所有有理正规曲线作为区组集合 p ，由前面的引理知对于m 中任意t 个点。如果其中任意t 一3 个点都线性无关，则它们只 在p 的一个区组中出现，否则的话，不在卢的区组中出现，因此完成了第一部分的证明 对于m 中任意给定的r ( 1 r t 一2 ) 个点，如果它们是线性相关的，则没有有理正 规监线经过这些点，如果它们是线性无关的，由上述引理3 的证明，有条有理正规曲线 经过这些点其中k 的计算方法是引理2 3 的证明中同定前r 个点时开始计数。容易得到 后半部分的结论 我们得到如下结论t 由上述引理知，利用有限域上的有理正规曲线可以构造一强部分 平衡设计，由本章的定理2 2 知，可以得到k d p ，再由第一章的定理1 4 可得到一类新的 k p s 下面我们来分析它的信息率及其性质 2 3k p s 的性质 设n 2 是整数，令m = p a ( n ，) ，口中的区组是m 上的所有有理正规曲线，由引 理2 4 可知( m ，口) 为一个强部分平衡( n + z ) - 设计设丸( 1si n + 2 ) 如上引理2 4 所 述，则有- 引理2 5 设( m ，卢) 及k ，1 s n + 2 如上所述，则有 1 = a n + 3 n + 2 a n + 1 - a l 1 4第二幸用有限域上有理正规曲线构造k p s 舞：篙鬻糕= 黼 t 上= o 圭：2 o 一= j t 口：醑 “” 口灶掣山啪一1 ) w ( q q ) _ 仃( 州) ”1 “” 拣：掣：猎 拣2 声。猎 n ( q 一)。 甓= 午= 1 - i ( 口一 ) 定理2 2 ( ，p ) 如上所述，令w i ( 1si n + 1 ) 表示满足撕 忠的整数，b i 表示m 中所有线性无关的i 元子集，则( m ，卢) 是一个( 毋，s 撕) 一j p 由此所构造的k p s 的信 息率是 1l 胪i 2 再酝习k 五 总信息丰为 l 盯5 _ = = = 币一 g 掣一l + 百( 矿一1 ) 每个用户所存储的信息量均为t k = a t = g 掣一1 ( 一一1 ) i = 2 证明t 由引理2 4 知如上所述的( m ，p ) 构成一个强郝分平衡t 一设计。再由引理2 5 知 定理2 2 的条件成立，因此定理的前一结论成立对于慨，) 一k d p ，容易算出信息事 与总信息率证毕 分析上面的参数，我们可以看出用这种方法产生的k p s 有以下的优点 1 产生方法简单。t a 可以根据面临用户的个数，选择适当的g ，这时用户集的数目是 出q - i = o ( q “) l 2 面向对象炅活t 若特权子集的成员较多，则只需将p g ( n ，) 的n 取得大一点即可， 若禁止子集的成员较多，这种k p s 仍能使用，因为由( 3 ) 3 式可知禁止成员的个致是 u = o ( q “一1 ) s t i n s o a 曾在【1 5 】中利用正交阵列( o r t h o g o n a la r r a y ) o a x ( s ，n ， ) 构造了一类( t ，s t ) 一k p s ( 2 tss 一1 ) ，但是这类k p s 的构造依赖于正交阵列的构造，然而正交阵列并不 是很容易构造的我们将在第三章构造一些正交阵列 2 4 一个例子1 5 2 4 一个例子 2 4 1 饲子 取口= 5 ，n = 2 ，则射影空间p g ( 2 ，f 5 ) 中有 鲁51 = 。-一l 个点，即有3 1 个用户 由引理2 3 知，p g ( 2 ，f 5 ) 上共有 5 掣一1 ( 5 3 1 ) = 3 1 0 0 条有理正规曲线，每条曲线上有5 + i = 6 个点 令m = p g ( 2 ，氏) ，p 是由这3 1 0 0 条有理正规曲线组成，由引理2 4 。则( m ，芦) 是一 个强部分平衡5 一( 3 1 ，6 ，1 ，0 ) 设计，同时它也是i 一( ，自，k ，o ) “= l ，2 ，3 ，4 ，) 部分平衡设计， 其中 a l = 6 0 0a 2 = 1 0 0a 3 = 1 6a 4 = 3 可计算得 0 i = 50 2 = 6 “3 = 5 再由定理2 2 知，存在一批k p s t 慨，u ) 一k p s ( i = i ，2 ，3 ) ，其中特权子集鼠是肘中所 有的线性无关的i 元子集，禁止子集是所有个数不超过u f 的用户的全体 这类k p s 的信息率都为- 1 p 。丽 总信息率t 1 加。莉i 每个用户所存储的信息量t v = 6 0 0 2 4 2 与平凡方案的比较 令用户子集甜= 1 ，2 ，3 1 ) 有3 1 个用户，特权子集b = p i p 是3 元子集) 按照平 凡方案的构造方法所得到的k p s 的信息率 11 胪雨2 磊 1 6 总信息率为 每个用户所存储的信息量均为 第二章用有限域上有理正规曲线构造k p s 11 刀2 两2 蕊 k = ( 警) = 4 3 5 对于任意的1 s i 3 本章提供了一种构造k p s 的方法，按这种方法。可以构造出一类k p s 。这类k p s 有 其明显的优点，也有一些缺点t 信息率较低，这是因为区组太多，但这可以使可信机构t a 在选择特权子集时有很大的选择余地，这在上面的方案中可以看到；而且我们还可以用弹 性函数来提高信息率。这种方法可参考【1 4 】，这里从略 第三章正交阵列 s t i n s o n 在 1 5 】中利用正交阵列o a ( o r t h o g o n a la r r a y ) 构造了一类k p s 。我们在第一 章中给出了简单的描述正交阵列作为一类组合结构。无论在密码学方面还是在组合学方 面都有着广泛的应用，例如s t i n s o n 在 1 6 】中利用正交阵列构造了认证码也有很多人对正 交阵列的构造进行了研究，例如j b i e r b r a u e r 的【2 】，d l k r e h e r 的【1o 】和c j c o l b o r u n 的 m 但总的来说，巳知的构造正交阵列的方法并不多 在本章中，我们对2 元域上r 维线性空间进行考察，得到了一些关于构造正交阵列方 面的结果本章的内容安排如下t 第一节，给出正交阵列的定义和性质 第二节，给出研究的方法； 第三节t 给出一般性的结果l 第四节。对下面两种k p s 的效率进行比较；由有限域上的有理正规监线所构造的k p s 和由正交阵列所构造的k p s ，当然由于对正交阵列的存在性还没有一个普遍的结果，因此 我们只能用两个例子，在相同的用户，特权子集相近的条件下进行比较 3 1 正交阵列的定义及性质 3 1 1 正交阵列的定义 定义3 1 设y 是- - + 元集合，a = ( 8 l j ) 是y 上的 矿xn 阶矩阵( 其中 ，t ，n 为1 的整数) 。满足下面的性质对于任意的t 一元子秉( b 1 ，一，蛳) y 及对于矩阵 的任意 如。t 阶子矩阵b ，( t l i ，毗) 作为矩阵b 的行，恰好出现a 次记为o a a ( t ，n ，u ) ，若 = 1 ，兢简记为o a ( t ，n ， ) 3 1 2 正交阵列的性质 命题3 1 “j 一个o a a ( t ，n ， ) 也是- - + o a a p ( s ，n ，”) ，对任意的1s 8st ，砂一个o a a ( t ，n ，_ ) 也是一个o 厶( t ，8 ， ) ，对任意的f 8 n 证明，( 1 ) 设a n 矩阵a 是一个o a x ( t ，n ，u ) ，给定1ss t 。对任意的元素组 ( 钆i 2 ，口) 歹石歹占丽及矩阵a 的任意s 列1 ，7 2 ，, 7 j ，将其补充为t 列。 由题设。对任意的 t 一+ d 雨翮y t y o ，竹1 ，m ) 5 1 8 第三章正交阵列 在矩阵a 的饥，忱，7 i + 一，7 列中出现 次，而这种元素组( 8 1 ，8 2 ，8 ，b j + 1 ，口t ) 共有 个。因而( a l ，d 2 ，a ) 在7 l ，7 ，列中出现a 口次，也就是说矩阵a 是一 个o a 一( s ，n ，u ) (