（基础数学专业论文）具有几何参数的d界距离正则图与认证码.pdf

河北师范大学硕士学位论文 中文摘要 本文在直径为d 的d _ 界距离正则图中给出了子空间的两个新的计数定理， 并利用子空间构作了一类c a r t e s i a n 认证码所得结论如下： 1 设r 是直径d 3 具有几何参数( d ，b ，o l ) 的d _ 界距离正则图，z y ( r ) ， 令p ( x ) 是r 中包含z 的所有子空间的集合而0 tsi + t ，j + t i + j + t d ， ，和分别是p ( x ) 中直径为t 和i + t 的子空间，。a ，则p ( x ) 中满足 n 7 = 。的直径为j + f 的子空间7 的个数是一个与。和的特殊选取无 关而仅依赖于i ，j 和t 的常数，记为尬( t ，i + ，j + ；d ) ，它是 拶一“ 护 进一步，p ( z ) 中满足d ( a n ) = t 的直径为j + t 的子空间，的个数是一个 与的特殊选取无关而仅依赖于i ，j 和的常数，记为m ( t ，i + t ，j + ；d ) ，它是 铲玎r 护 其中嘲舻是基为6 2 的g a u s s i a n 二项式系数 2 设r 是具有几何参数( d ，b ，o ) 直径d 3 的d 界距离正则图，z y ( r ) 令p ( x ) 是r 中包含z 的所有子空间的集合设1 m o m d ，a o 是p ( x ) 中 的一个固定的直径为m o 的子空间定义信源集5 为包含o 的直径为m 的 子空间集，编码规则集为与o 交为如 直径为d m o 的子空间集，信息集 m 为与0 交为p ) 的直径为m m o 的子空间集对任意a 8 ，a 。，定义 ，( ，a 。) = ana 1 则如上的构作是一个c a r t e s i a n 认证码 3 构作得到的c a r t e s i a n 认证码的参数为 吲= m d - 一t o m o 。 护，吲= 6 2 m 0 ( d m ) ，1 m i = b 2 m “m m ) l m d - 一m m o 。 j 驴， 其中吲。是基为b 2 的g a u s s j a n 二项式系数 假设编码规则按等概率分布选取，成功的模仿攻击概率和成功的替换攻击 概率分别为 毋= 历而1 二而，p s = 丽1 具有几何参数的d 一界距离正则图与认证码 关键词：距离正则图，d - 界距离正则图，有几何参数的距离正则图，子 空间，c a r t e s i a n 认证码 河北师范大学硕士学位论文 u l a b s t r a c t i nt h i sp a p e r ，w es t u d yt h ed - b o u n d e dd i s t a n c e - r e g u l a rg r a p hfw i t hd i a m e t e rd w eo b t a i nt w on e wf o r m u l ao fc a l c u l a t i o no fs u b s p a c ea n dc o n s t r u c tac l a s so fc a r t e s i a n a u t h e n t i c a t i o nc o d eu s i n gt h es u b s p a c e s t h em a i nr e s u l t sa r ea sf o l l o w s 1 l e tfb ead - b o u n d e dd i s t a n c e - r e g u l a rg r a p hw i t hg e o m e t r i cp a r a m e t e r s ( d ，b ，o ) a n dd 3 f o rz y ( r ) ，l e tp ( x ) b eas e to fa l ls u b s p a c e sc o n t a i n i n gzi nf s u p p o s e 1 垦，0 t i + ta n dj + t i + j + t d ，a n ds u p p o s ea 1a n d a r es u b s p a c e w i t hd i a m e t e rta n di + t ，r e s p e c t i v e l y t h e nt h en u m b e ro fs u b s p a c e s ，i np ( x ) w i t h d i a m e t e rj + ts u c ht h a t n a 7 = 1 ，d e n o t e db yu l ( t ，i + ，j + d ) ，i sd e t e r m i n e db y ja n dt i n d e p e n d e n to ft h ec h o i c eo fa 1a n d a n di sg i v e nb y 尬c t ，t + t ，+ t ；回= 。2 u d 一；一。 护 f u r t h e r m o r e ，t h en u m b e ro fs u b s p a c e s i np ( x ) w i t hd i a m e t e rj + ts u c ht h a t d ( an 7 ) = t ，d e n o t e db ym ( t ，i + t ，j + t ；d ) ，i sd e t e r m i n e db yi ，ja n dt ，i n d e p e n d e n to f t h ec h o i c eo f 1a n d a n d i sg i v e nb y m c t ，t + 屯。+ 以却= 。2 坩 d 一；一。 。 i j 。 护， w h e r e 【 i st h eg a u s s i a nc o e f f i c e n t sw i t hb a s i sb 2 2 l e tfb ead - b o u n d e dd i s t a n c e - r e g u l a rg r a p hw i t hg e o m e t r i cp a r a m e t e r s ( d ，b ，o t ) a n dd 3 f o rz y ( r ) ，l e tp ( x ) b eas e to fa l ls u b s p a c e sc o n t a i n i n g2i nf w ea l s o s u p p o s e1 m 0 1 且a ，0 时的距离正则图的分类。 张宝环【矧研究了出界距离正则图中强闭包子图的一些性质距离正则图 在认证码中的应用是一项很有意义的工作 认证码用于解决信息传输中的认证问题假设在一个通信系统模型中，除 了信息的发方和收方外，还存在一个敌方，敌方掌握了某种手段，可以截获 信息系统中的信息，也可以向系统中注入其它干扰信息通常敌方对该系统 进行两种主动攻击：一是模仿攻击，二是替换攻击所谓模仿攻击，即敌方在 未观测到信道中发方给收方发送的信息的条件下，通过信息发送一个他伪造 的信息给收方；而替换攻击是敌方截获到发方给收方的一个信息，并进行分 2 具有几何参数的d 一界距离正则图与认证码 析后再给收方发送另一个信息替换原信息在这个信息系统模型中，发方和 收方使用同一编码规e ，收方收到信息m ，检查m 是否包含编码规则e ，如果包 含，收方解密信息m 得到相应的信源8 ，否则收方认为m 是非法的，并拒绝 它 自认证码提出的将近二十年里，世界上许多数学家，密码学家都对它进行 了研究，他们的研究主要集中在认证码的性质上和构作上认证码的创始人 s i m m o n sg j 和s t i s o nd r 以及我国的裴定一教授等在认证码性质的研究方面 作了大量的工作，得到了认证码被敌方模仿攻击和替换攻击的概率的组合论 下界和信息论下界；1 9 9 4 年，j o h a n s s o nt 得到了带有仲裁的认证码被成功 攻击的五种概率的下界【堋 认证码的构作方面得到的结果更是异彩纷呈由于认证码的构作就其本质 来说是组合设计问题，而有限域上的典型群几何一射影几何、仿射几何、辛 几何、伪辛几何、酉几何、正交几何等提供了较好的组合结构，且易于计数， 在六，七十年代就被用于研究区组设计问题九十年代，万哲先院士、冯荣权 博士等用有限典型群几何构作了一系列没有仲裁的认证码【2 鲥所有这些研究 对于认证码的研究具有重要的意义 本文对具有几何参数的出界距离正则图子空间的一些性质进行了研究，设 1 和分别是p ( z ) 中直径为t 和i + t 的子空间，证明了p ( z ) 中满 足n ，_ ，的直径为j + t 的子空间，的个数是一个与。和的特殊选 取无关而仅依赖于i ，j 和t 的常数，并给出了它的计数公式，利用一些特殊子 空间构作了一类新的认证码 河北师范大学硕士学位论文 3 1 2 本文综述 本文共分4 章第1 章阐述了课题背景及发展概况；第2 章为预备知识， 着重介绍了后面几章中要用到的一些符号，概念和基本结论；第3 章研究了 出界距离正则图中强闭包子图的一些性质；第4 章构作了一类新的认证码， 并计算了它的参数主要结果是： 定理3 4 设r 是直径d23 具有几何参数( d ，b ，q ) 的出界距离正则图，而 0 t i + t ，j + t i + j + t d ，a 1 和分别是p ( x ) 中直径为t 和i t t 的子空间， a ，a 则p ( z ) 中满足n ，= ，的直径为j + t 的子空间的个数是一个 与，和的特殊选取无关而仅依赖于i ，j 和t 的常数，记为m i ( t ，i + t ，j + t ；d ) ， 它是 矽 d _ 一护 进一步，p ( z ) 中满足d ( a n ，) = t 的直径为j + t 的子空间，的个数是一个 与的特殊选取无关而仅依赖于i ，j 和t 的常数，记为m ( t ，i + t ，j + t ；d ) ，它是 叫扣川护m 护， 其中 】萨是基为b 2 的g u a s s i a n 二项式系数 定理4 1 设r 是具有几何参数( d ，b ，口) 直径d 3 的出界距离正则图， z y ( r ) 令p ( z ) 是r 中包含茁的所有子空间的集合设1 m o m d ，a o 是 p ( x ) 中的一个固定的直径为蛳的子空间定义信源集s 为包含o 的直径为 m 的子空间集，编码规则集为与o 交为 z ) 直径为d m o 的子空间集，信 息集州为与0 交为伽) 的直径为i n r n o 的子空间集对任意a s ，- ， 定义，( ，1 ) = ana 1 则如上的构作是一个c a r t e s i a n 认证码 定理4 2 构作得到的c a r t e s i a n 认证码的参数为 阶i m d - 一t o 蜘。小i = 耙( d _ 朋i = 舭一 m d - 一t o 咖o 庐， 其中吲6 2 是基为6 2 的g u a s s i a n 二项式系数 定理4 5 假设编码规则按等概率分布选取，所构作的c a r t e s i a n 认证码的成 4 具有几何参数的d 一界距离正则图与认证码 功的模仿攻击概率和替换攻击概率分别为 q = 南，p s = 南 河北师范大学硕士学位论文 5 第2 章预备知识 本章介绍距离正则图，认证码的基本概念和性质 2 1 距离正则图的基本概念 我们给出图的定义和习惯记号关于距离正则图的其它知识，读者可参考 专著 8 1 定义2 1 1 设x 是一个集合，e 是由x 的一些元的无序对构成的集合则 我们称集合对f ：= ( x ，e ) 是一个图其中x 称为图r 的顶点集合，用y ( r ) 表 示而e 称为图r 的边集合，用e ( f ) 表示 在本文我们恒假定图为有限的，即 x i o 。我们把在上诱导的子图，仍 记为设cy ( r ) ，仍用表示上的诱导子图，并记a = ( y ( ) ，e ( ) 定义2 1 2 设f = ( x ，e ) 是一个图图r 的两个顶点z 和y 叫做邻接的，如 果x y e ，记为z y 否则，x 和y 叫做不邻接的，记为z y 设钍和秽是图 r 的两个顶点 ( 1 ) 图r 中从顶点让到顶点口的长为f 的一条途径是r 中2 + 1 个顶点序列 ( u = 删o ，w 1 ，w t = 钞) 使得 “2 w o “如1 “i f 3 1 2 口 ( 2 ) 图r 的一条途径( u = w o ，叫，枷= t ，) 称为道路，如果对任一个i ( i = 1 ，l 一1 ) ，都有毗一l 毗+ 1 一条道路( 钍；伽o ，卸1 ，毗= t ，) 称为约简的，如 果对任一个i ( i - 1 ，z 一1 ) ，都有毗一l 与毗+ 1 不邻接 ( 3 ) 图r 中的顶点“和”的距离是r 中连接u 和t ，的最短路的长，记为 卉( u ，钉) 如果在r 中不存在连接钍和”的路，那么规定a r ( u ，钌) = o o ( 4 ) 图r 的直径是r 中任意两点间距离的最大值，记为d = d ( r ) 同样，r 的子图的直径记为d ( ) ( 5 ) 一个图r 叫做连通的，若对r 中任意两个顶点仳和秽，在f 中都有连接 “和口的道路 6 具有几何参数的d 一界距离正则图与认证码 定义2 1 3 一个图f = ( x ，e ) 中，两个顶点相同的边叫做环；两条具有相同 端点的边叫做重边即无环又无重边的图叫做简单图 定义2 1 4 设a ，bcx ，定义o ( a ，b ) = m i n 0 ( x ，u ) l x a ，y b 定义2 1 5 设r 是一个连通无向的简单有限图，对于顶点u 和t ，用砩( 牡，口) 表示r 内“与”的距离设毛y ，用弘( 茹，y ) 表示内与y 的距离设 d = d ( r ) 表示r 的直径，且对任意0 i ，j d 规定 r ( 钍) = 钉v ( r ) i 西( 牡，口) = t ，r 1 ( 札) = r ( “) ； ( z ) = g y ( ) i o a ，y ) = i ，l ( z ) = ( z ) d ；= r d u ) n d ( 牡) r 叫做距离正则的，如果集合谚( u ，t ，) 的基数仅与仳和”之间的距离有关， 而与顶点u 和钉的选取无关关于距离正则图的更详尽的内容可参阅文献 a l 下面文中，凡涉及到r 的，r 均指距离正则图 在这种情形下，记 反，j = i q ( 乱，圳， 其中t = a ( 甜) 设k i = p o i = m ( 让) i 特别记k = k x ，且 c = 西，l 一1 ( 1 i d ) ；0 4 = 砖，( osi d ) ；b i = 西，件1 ( o i d 一1 ) 我们把k 叫做r 的价，而把m ，魄，q 叫做r 的交叉数 定义2 1 6 设t ，钉y ( f ) ，砩( 钍，钉) = i ，我们称r 一1 ( 钍) n r ( 口) 是关于( u ，钉) 的a 图，有时也将其记做a ( 缸，v ) ；称l ( 钍) n r ( v ) 是关于( 乱，口) 的a 图，有时也将其 记做a ( 钍，可) ；称r i + l ( “) nr ( 口) 是关于( 钍，口) 的鼠图，有时也将其记做b i ( u ，t ，) 并且记c ( ，可) = l a ( “，钉) l ，啦( u ，t j ) = l a ( 札，t ，) | ( 钍，”) = i b i ( 趾，”) | 定义2 1 7 我们称 ( r ) = 宰c 1 c 2c ic d 一1国 0a l 眈啦a d 一1a d kb 1 b 2 6 b n 一1 4 河北师范大学硕士学位论文 7 为r 的交叉阵列 例如，考虑立方体q 。，它是一个直径为3 的距离正则图，其交叉阵列为 ( q 3 ) = 定义2 1 8r 的子图称为是强闭包的，如果对任意“，秽a ，都有e ( “，) u a ( u ，t ，) ( a 正则的强闭包子图称为子空间显然，r 的强闭包子图是连通的，并且对 任意，甜a ，都有砩( 钍，移) = 九( ，口) 定义2 1 9 一个直径为d 的距离正则图r 称为具有典型参数( d ，b ，o l ，p ) 的， 如果它的交叉数满足 q = i 。( - + 口r 1 。) ，。z 兰正 氏= ( ；】。一 i 。) ( p q ： 。) ，。t d ， 玛l - - ：1 0h - 1 ， 玛1 - ：0 1 而b i - b ， 如果b = 1 如果b 1 表示基为b 的g a u s s i a n 二项式系数 定义2 1 1 0 一个具有典型参数( d ，b 崩卢) 的距离正则图r 称为具有几何参 数( d ，b ，o ) 的，如果卢= 口( 1 + 6 d ) ( 1 6 ) ，b 1 定义2 1 1 1 设r 是一个直径为d 的距离正则图r 称为是d 界的，如果 满足下列两个条件 ( 1 ) r 的每个强闭包子图都是正则的； ( 2 ) 对任意z ，y v ( r ) ，存在包含z 和y 且直径为砩( 甄y ) 的强闭包子图 例如，设t 是一个正整数，则二部完全图凰，。是一个直径为2 的2 界距离 正则图，它的交叉阵列为 3 o 2 o 1 1 0 2 o 3 8 具有几何参数的d 一界距离正则图与认证码 。( k t ，t ) = 定义2 1 1 2 设r 是一个直径为d 的出界距离正则图，。和。是r 中的 两个子空间称包含。和。的最小子空间为。与2 的和，记为。+ 2 1 。 o 卜 o t 河北师范大学硕士学位论文 9 2 2 认证码的概念 本节介绍认证码的概念 设s ，和m 是三个非空有限集，而，：s e + m 是一个映射四元组 ( s ，m ；，) 称为一个认证码f 圳，如果 ( i ) 映射，：5 + m 是一个满射， ( i i ) 对任意m m 和e ，如果存在s 5 使得s ( s ，e ) = m ，那么8 是由m 和e 惟一确定的 假设( s ，朋；，) 是一个认证码那么s ，和m 分别称为信源集，编码规 则集和信息集，称为编码映射如果s se 和m m 使得m = s ( s ，e ) ， 那么我们说信源8 在编码规则e 下加密成信息m ，或称信息m 包含编码规则e 基数1 s l ，吲和i m i 称为这个码的参数此外，如果认证码还满足，对任意信息 m 朋总存在惟一信源8 s 使得m = f ( a ，e ) ，其中e 是包含在m 中的任意编码 规则，则称这样的认证码为c a r t e s i a n 认证码除此外，假设编码规则按等概率 分布选取，成功模仿攻击的概率用b 表示，成功替换攻击的概率用p s 表示 1 0 具有几何参数的d 一界距离正则图与认证码 第3 章子空间的计数定理 本章得到了下面主要定理 命题3 1 ( 文献【2 2 】引理4 2 和引理4 5 ) 设r = ( v c r ) ，e ( r ) ) 是一个直径为d 的 出界距离正则图那么下面的( i ) 一( i i i ) 成立 ( i ) 两个子空间的交或者是子空间或者是空集 ( i i ) 设是r 的一个子空间那么是距离正则的，并且有交叉数 q ( ) = 6 ，0 i d ( ) ， 啦( ) = a i ，0 s i d ( ) ， 堍( ) = 玩一呛( ) ，0 i d ( ) ( i i i ) 对任意z ，y y ( r ) ，包含z 和y 且直径为o ( z ，y ) 的子空间是惟一的 显然，在直径为d 的出界距离正则图r 中，包含z 和y 且直径为0 ( x ，y ) 的 子空间有且只有z ，y 设，和。是r 中的两个子空间称包含- 和。 的最小子空间为。与。的和，记为- + 。 命题3 2 ( 献 1 2 】引理2 1 ) 设r 是直径d 3 且具有几何参数( d ，b ，q ) 的d - 界 距离正则图，而i 十1 i + 8 t + 8 + t d ，和，分别是r 中直径为i 和 i + 8 + t 的子空间，并且则r 中满足五且直径为i + 8 的子空 间厶的个数是一个与和的特殊选取无关而仅依赖于i ，8 和t 的常数，记 为n ( i ，i + s ；i + s + ) ，它是 f 】护 命题3 3 ( 文献【2 2 】引理5 5 ) 设f 是一个直径d 3 且具有几何参数( d ，b ，) 的出界距离正则图对r 的任意子空间，如果n ，0 ，那么 d ( a ) + d ( a 7 ) = d ( a n 7 ) + d ( a + a ) 定理3 4 设r 是直径d 3 具有几何参数( d ，b ，o t ) 的出界距离正则图，而 0 t i + t ，j + t i + j + t d ，1 和分别是p ( x ) 中直径为t 和i + t 的子空间， 。则p ( x ) 中满足n ，= 。的直径为j + t 的子空间的个数是一个 河北师范大学硕士学位论文 与。和的特殊选取无关而仅依赖于i ，j 和t 的常数，记为m ( t ，i + t ，+ 缸d ) ， 它是 b 2 0l d _ 卜o i 【 j j 庐 进一步，p ( z ) 中满足d ( a n 7 ) = t 的直径为j + t 的子空间7 的个数是一个 与的特殊选取无关而仅依赖于i ，j 和t 的常数，记为m ( t ，t + t ，j + t ；d ) ，它是 叫加卅护m 驴 证下面分3 步证明结论 第一步，设五是一个包含且直径为i + j 十t 的子空间因为d ( a ) = i - - t ，a lc ，所以存在z ，z l ，y a ，使得o ( z ，z ) = t ，a ( z ，y ) = i ，o ( y ，z ) = i + t 于是，由命题3 1 ( i i i ) 知，1 = z ，a = 秒，z 下面求在五中满足 na = z ，z 的直径为j + t 的子空间，的个数 首先，在五中取点列2 = u o ，札l ，u j = w ，使得m b ( y ，撕一。) n 厶，1 l j 则由命题3 1 ( i i i ) 知，五= y ，伽，而且= z ，硼是一个直径为j + 的子 空间由命题3 3 知，子空间7 是满足n a 7 = 墨z 的子空间因为在五 中上述点列的取法为 e = ( 氏+ t 一6 十，+ t ) ( 玩+ 件1 一玩十，+ t ) ( 坟+ t + j 一1 一岛+ j + t ) ， 所以，得到e 个满足na - - - - 为z 直径为j + t 的子空间( 相同的按重复 次数计) 其次，计算上面e 个子空间中，每个重复计数的次数设7 是这e 个子空间 中的一个则可在7 中取点列z = v o ，v l ，= 埘，使得功b ( x ，仇一1 ) n 7 ，1 l 工于是由命题3 1 ( i i ) 知7 中共有 e 7 = ( b t 一幻+ ) ( 6 t + 1 一+ t ) ( 巩蜘一1 一吗+ t ) 个这样的点列显然，a ( z ，码) = j + t ，= 霸吩我们断言：a ( f ，) = i + j + t 下面用归纳法证明：o ( y ，铆) = i + t + l ，0 z j 当f _ 0 时结论显然成立假 设当f j 一1 时结论成立，即a ( s ，功) = i + t + l ，0sz j 一1 当l = j 时，因为 吩b 扛，吻一1 ) n ，a ( 暑，一1 ) = i + t + j - 1 ，所以i + t + j 一2so ( y ，码) i + t + j 如果 1 2 具有几何参数的d 一界距离正则图与认证码 i + t + j 一2 o ( v ，v j ) i + t + j 1 那么由y ，吩一l 是子空间知，y ，吩一l 于是，= z ，码c y ，吩一1 但d ( y ，一1 ) = i + t + j 一1 ，这与定理3 4 矛盾因此，o ( y ，) = i + t + j 于是，在上面e 个子空间中，重复计数的 次数为e 设，是五中满足n = z ，名直径为j + t 的子空间则在，中存在 点使得，o ( z ，w ) = j ，o ( x ，w ) = j + t 于是，z ，彬= a 7 因此，由上面讨论 得，o ( v ，w ) = i + j + t 再由定理3 4 知，d ( + a ) ；i + j + t 由命题3 1 ( i i i ) 知， + ，= 五= y ，w 说明是上述e 个子空间中的一个 因此，得到e e 个满足na = z ，z 直径为j + t 的子空间 第二步，设五是一个包含且直径为i + 歹+ t 的子空间由命题3 2 知， 中包含n ( o ，t ；i + t ) 个p ( x ) 中的直径为t 的子空间再由命题3 1 ( i i i ) 和命题 3 3 得，鑫中满足d ( an a ) = t 直径为j + t 的包含 z ) 的子空间的个数是 n ( o ，t ；i + ) e e 第三步，由命题3 2 知，p ( x ) 中包含且直径为i + j + t 的子空间的个数 是n ( i + t ，i + j + f ；d ) 设厶和厶1 是p ( x ) 中两个包含且直径为i + j + t 的子 空间，则五中满足d ( a na 7 ) = t 直径为j 十t 的包含 x ) 的子空间与五。中 满足d ( an i ) = t 直径为j + t 的包含 x ) 的子空间i 一定不相同事实上， 若= ；，则 鑫= a + 7 = + a ：= 五1 在p ( x ) 中的任意一个满足d ( a n 7 ) = t 直径为j + t 的子空间7 都包含在直 径为i + j + t 的子空间+ 7 中 通过上面三步讨论，得到p ( x ) 中满足d ( n 7 ) ；t 直径为j + t 的子空间7 的个数是n ( i + t ，i + j + t ；d ) n ( o ，；i + t ) e e 再由命题3 2 及其证明得， 邮“删哪川e e = 拶r 引垆嘲驴 河北师范大学硕士学位论文 第4 章认证码的构作 定理4 1 设r 是具有几何参数( d ，b ，口) 直径d 3 的d - 界距离正则图， z y ( r ) 令p ( x ) 是r 中包含z 的所有子空间的集合设1 m o msd ，0 是 p ( z ) 中的一个固定的直径为m o 的子空间定义信源集s 为包含。的直径为 m 的子空间集，编码规则集为与o 交为 z 直径为d m o 的子空间集，信 息集朋为与0 交为 z ) 的直径为m m o 的子空间集对任意a s ，。， 定义s ( a ，a 1 ) = ana 1 则如上的构作是一个c a r t e s i a n 认证码 证设是一个信源，t 是一个编码规则因为，n a o = 扛1 所以由命 题3 3 知，1 + o = f 说明+ a l = f 于是，由命题3 3 知， d ( a n a l ) = d ( a ) + d ( 1 ) 一d ( a + 1 ) = m m o 又( n 。) n 0 = a n ( a 1n 0 ) = 扛 说明n - 是一个信息因此，是一 个映射 其次，设2 是一个信息，则d ( a 2 ) = m m o ，2 n 0 一 ) 令a = a o + a 2 则由命题3 3 知，d ( ) = m ，即是一个信源再设3 是满足3n = d 的直径为d m 子空间，则r = 3 + = 3 + ( 2 + o ) = ( 3 + 2 ) + 0 由 扛 a 3 n a 2 a s n = z ) 知，3n a 2 = z ) 于是由命题3 3 知， d ( ( 3 + 2 ) n a o ) = d ( a s + 2 ) + d ( a o ) 一d = 0 ， 即( 3 + 2 ) n 0 = 。) 说明2 + 3 是一个编码规则显然，2 ( 3 + 2 ) h a 再由命题3 3 和f = ( 3 + a 2 ) + o ( a 3 + a 2 ) + a 知，d ( ( 3 + a 2 ) n ) = d ( 3 + 2 ) + d ( a ) d m m o 于是，由命题3 1 ( i i i ) 得，( 3 + 2 ) n a 盏a 2 即 f ( a ，a 3 + 2 ) = a 2 说明，是一个满射 最后，若7 是另一个相应于信息2 的信源，则。，0 ，所以 a = 0 + a 2 a 7 由d ( a ) = a ( a ) = m 和命题3 1 ( i i i ) 得，= ，所以上述构 作方法得到一个c a r t e s i a n 认证码 定理4 2 构作得到的c a r t e s i a n 认证码的参数为 i s l = m d - 一m 蛳e 驴，= 删扛伽j ，i m i = 删一叫m d - 一t o 伽o 护 1 4具有几何参数的d 一界距离正则图与认证码 其中旧。，是基为b 2 的g u a s s i a n 二项式系数 证由= n ( m o ，r a ；d ) ，蚓= m ( o ，弛，d t o o ；d ) ，m l = m ( o ，蛳，m m o ；d ) 得 到 引理4 3 包含在任意一个信息中的编码规则的个数是6 2 ，l o ( d 一) 证设：是一个信息，则= 2 + o 是相应于。的信源我们断言：含 于。的编码规则集恰为p ( x ) 中满足n 。= a 2 的直径为d m o 的子空间 。的集合事实上，设。是含于。的一个编码规则，则a ( a - ) = d m o ，2 1 ，0n 1 = 如 显然， 2 1n 因为r = o + c l + ，所以由定理 3 4 知，a ( a 1n ) = m m o 于是，由命题3 1 ( i i i ) 知，a 2 = a 1n ，a 1 是满足 n 1 = 2 的直径为d m o 的子空间反之，设1 是满足na 1 = 2 的直 径为d 一蛳的子空间，则 z ) c a l n a o l n a = a 2 ，a i n 0 a o 于是，。n 0 2n 0 = p 说明ln o = 茁) 因此，1 是一个含于2 的编码规则 由定理3 4 知，含于2 的编码规则的个数为尬( m m o ，m ，d m o ；d ) = 6 2 m ( d m ) 引理4 4 设。，越是包含同一个编码规则的两个不同信息，分别是对 应于2 和链的惟一的信源设d ( a 2 + 岛) = r ，则有m m o + 1s rsm i n ( 2 m 一 2 m o ，d m o ) ，并且同时包含在。和链中的编码规则的个数是6 2 伽( d - m ”) 证显然，= 。+ o ，a = 鸽+ o 因为2 ，越是包含同个编码规则两个 不同子空间，所以由命题3 1 ( i i i ) 知，m 一蛳+ l r m i n ( 2 m - 2 m o ，d - t o o ) ，并且由 编码规则的定义知，( a 2 + 越) n o = 矗) 则由命题3 3 得，则d ( + 7 ) = m + r 我 们断言：同时含于。和越的编码规则集恰为p ( x ) 中满足a i n ( a + a 7 ) = a 2 + a ：f 的直径为d - ”协的子空间l 的集合事实上，设1 为满足1 n ( + ，) = 2 + ： 的直径为d r a o 的子空间，则z a 1 n o a 1 0 ( a + ，) = 2 + 越因此， 。n o ( 。+ 越) n 0 = z ) 说明t 是一个同时包含在。和越中的编码 规则反之，设，是同时含于。和越的编码规则，则由引理4 3 知，- 是 满足 】n a = a 2 ( l n = 2 ) 河北师范大学硕士学位论文 1 5 的直径为d m o 的子空间因此，l n ( + 7 ) 三2 + 魁再由 d ( 1 n ( a + a ，) ) = d ( a 1 ) + d ( a + a 7 ) 一d ( a 1 + ( + ，) ) = ( d r n o ) + ( m o + r ) 一d = r 和命题3 1 得，1 n ( + a ) = a 2 + 越 因此，由定理3 4 知，同时包含在。和；中的编码规则的个数是 m l ( r ，m o + r ，d m o ；d ) = b 2 m ( a - m o 一” 定理4 5 构作方法得到了一个c a r t e s i a n 认证码，它的参数由定理4 2 给出 假设编码规则按等概率分布选取，成功的攻击概率分别为 p i = 南，p s = 击， 证由引理4 3 和引理4 4 得p s = m a x ( 1 6 2 m ( 啪+ r 一) ，其中m m o + 1 r m i n ( 2 m 一2 m o ，d m o ) 因为r 可以取到m m o + 1 ，所以p s = 而1 1 6 具有几何参数的d 一界距离正则图与认证码 参考文献 【1 】b a n n a ie ，c o d e si nb i p a r t i t ed i s t a n c e - r e g u l a rg r a p h s ，j l o n d o nm a t h s o c 1 9 7 7 ，1 6 ( 2 ) ：1 9 7 - 2 0 2 【2 】b a n n a ie ，o np e r f e c tc o d e s i nt h eh a m m i n gs c h e m eh ( n ，w t hqa r b i t r a r y ； j c o m b i n t h ，1 9 7 7 ，2 3 ( a ) ：5 6 - 5 7 3 】b a n n a ie ，i t ot ，a l g e b r a i cc o m b i n a t o r i c s 工c a l i f o r n i a ，b e n j a m i n - c u m m i n g s ， 1 9 8 4 【4 】b i e rt ，l a t t i c e sa s s o d a t e dt ot h er e c t a n g u l a ra s s o c i a t i o ns c h e m e , a r sv o i d - b i n ，1 9 8 7 ，2 3 ( a ) ：4 1 5 0 【5 】b i g g sn l ，a l g e b r a i cg r a p ht h e o r y , c a m b r i d g et r a c t si nm a t h 6 7 ，c a m - b r i d g eu n i v e r s i t yp r e s s ，c a m b r i d g e ，1 9 7 4 【6 j b i g g sn l ，d e s i g n s ，f a c t o r sa n dc o d e sj ng r a p h s ，q u a r t j m a t h o x f o r d ， 1 9 7 5 ，2 6 ( 2 ) ：1 1 3 - 1 1 9 【7 】b i g g sn l ，p e r f e c tc o d e s ng r a p h s ，j c o m b i n t h ，1 9 7 3 ，1 5 ( b ) ：2 8 9 - 2 9 6 【8 】b r o u w e ra e ，c o h e na m a n dn e u m a i e ra ，d i s t a n c e - r e g u l a rg r a p h s ， s p r i n g e rv e r l a g ，b e r l i n ，h e i d e l b e r g ，1 9 8 9 【9 】d e l s a x t ep h ，a na l g e b r a i ca p p r o a c h 幻t h ea s s o c i a t i o ns c h e m e so fc o d i n gt h e - o r y , p h i l i p sr e s e a r c hr e p o r t ss u p p l ，1 9 7 3 ，1 0 【1 0 】f e a gr a n dw a nz ，ac o n s t r u c t i o no f c a r t e s i a na u t h e n t i c a t i o nc o d e s f r o mg e - o m e t r yo f c l a s s i c a lg r o u p s ，j o u r n a lo fc o m b i n a t o r i c s ，i n f o r m a t i o na n ds y s t e m s c i e n c e s ，1 9 9 5 ，2 0 ：1 9 7 - 2 1 0 【1 1 】g o d s i lcd ，a l g e b r a i cc o m b i n a t o r i e s , n e wy o r k ，c h a p m a na n dh a l l ，1 9 9 3 河北师范大学硕士学位论文 【1 2 g a os ，g u oj a n dl i uw ，l a t t i c e sg e n e r a t e db ys t r o n g l yc l o s e ds u b g r a p h s i nd - b o u n d e dd i s t a n c e - r e g u l a rg r a p h sw i t hg e o m e t r i cp a r a m e t e r s ，( t oa p p e a r i ne u r o p e a nj ，c o m b i n a t o r i c s ) 【1 3 】h e m m e t e rj ，t h el a r g ec l i q u e s i nt h eg r a p ho fq u a d r a t i cf o r m s , e u r j c o m b i n ，1 9 8 8 ，9 ：3 5 9 - 4 1 0 【1 4 h i r a k ia ，a na p p l i c a t i o no f ac o n s t r u c t i o nt h e o r yo fs t r o n g | yc l o s e ds u b - g r a p h sj 丑ad i s t a n c e - r e g u l a rg r a p h ，e u r o p j c o m b i n ，1 9 9 9 ，2 0 ：2 7 1 2 7 8 【1 5 】h u a n gt ，s o m er e s u l t s0 nt h ea s s o c i a t i o ns c h e m e so fb f l i n e a rf o r m s , p h d t h e s i s ，o h i os t a t eu n i v ，1 9 8 5 【1 6 i v a n o va a ，d i s t a n c e - t r a n s i t i v eg r a p h sa n d t h e i rc l a s s i f i c a t i o n ，i n v e s t i g a t i o n i na l g e b r a i ct h e o r yo fc o m b o b j e c t s ，k l u w e ra c a d p u b l 1 9 9