（基础数学专业论文）强分裂系统码与hash族界的改进.pdf

摘要 本文从分裂认证码出发，构造了一种新的码：强系统认证码利用这 种特殊的码与一般系统认证码的关系，得到了这种码在编码规则概率空间 服从均匀分布时的最大模仿概率芹的下界公式；另外，还进一步探讨了 q ( i = 1 ，2 ，k ) 固定的( e l ，c 2 ，c k ) 型强分裂系统码的芹的下界公式， 并且利用一种改进的平衡化方法，证明了任何一个( c l ，c 2 ，铅) 强分裂系 统码，都可以转化为一个新的芹最小的( c t ，c 2 ，c k ) 型强分裂系统码 最后，把s i n g l e t o n 界引入到h a s h 族界的讨论中，得到了新的界通过 与旧的界的比较，得到了两个界的优劣情况 关键词认证码，系统认证码，分裂认证强，分裂系统码，强分裂系统 码，平衡化，h a s h 族，h a s h 函数，p l o t k i n 界，s i n g l e t o n 界 a b s tr a c t f r o mt h es p l i t t i n gs y s t e m a t i ca u t h e n t i c a t i o nc o d e s ，i nt h i sp a p e rw ec o n s t r u c tan e wk i n do fc o d e s ：s t r o n g l ys p l i t t i n gs y s t e m a t i ca u t h e n t i c a t i o nc o d e s t h r o u g ht h er e l a t i o nb e t w e e n t h i ss p e c i a lc o d e sa n dg e n e r a ls y s t e m a t i ca u t h e n t i c a t i o nc o d e s ，al o wb o u n do fm a x i m u mp r o b a b i l i t i e so fas u c c e s s f u li m p e r s o n a t i o n p 1 妇a l lt h o s ec o d e si sd e r i v e di fe n c o d i n gr u l ed i s t r i b u t i o n sa r ee q u i p r o b a b l e m o r e o v e r ，i nt h i sp a p e rw es t u d yt h el o wb o u n do f 芹o f ( e l ，c , z ，c k ) s t y l e s t r o n g l ys p l i t t i n gs y s t e m a t i ca u t h e n t i c a t i o nc o d e s ( c i ( i = 1 ，2 ，是) a r ei n v a r i - a b l e ) ，u s i n gai m p r o v e dc o d i n ga l g o r i t h m ，c a l l e du n i f o r m i z a t i o n ，w ep r o v et h a t a l l ( c 1 ，c 2 ，c k ) s t y l es t r o n g l ys p l i t t i n gs y s t e m a t i ca u t h e n t i c a t i o nc o d e sc a nb e u n i f o r m i z e di n t ot h es a m es t y l eo fc o d e sw h i c hh a st h em i n i m a l 芹 t h e n ，w es t u d yt h eb o u n do nt h r e ek i n d so fh a s hf a m i l yu s i n gt h es i n g l e t o n b o u n d ，a n dg e tn e wb o u n d so nh a s hf a m i l y t h r o u g hc o m p a r e i n gw i t ht h eo l d b o u n d s ，w eg e tt h ec a s e sw h e nt h en e wb o u n d sa r eb e t t e r k e yw o r d s a u t h e n t i c a t i o nc o d e s ，s y s t e m a t i ca u t h e n t i c a t i o nc o d e s ， s p l i t t i n ga u t h e n t i c a t i o nc o d e s ，s p l i t t i n gs y s t e m a t i ca u t h e n t i c a t i o nc o d e s ，s t r o n g l y s p l i t t i n gs y s t e m a t i ca u t h e n t i c a t i o nc o d e s ，u n i f o r m i z a t i o n ，h a s hf a m i l y , h a s h f u n c t i o n ，p l o t d i nb o u n d ，s i n g l e t o nb o u n d 1 1 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除了 文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过 的研究成果参与同一工作的其他同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了谢意 签名。踢嫩 日期3 哏厶； 本论文使用授权说明 本人完全了解上海大学有关保留，使用学位论文的规定，即：学校有权 保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文 的全部或部分内容 ( 保密的论文在解密后应遵守此规定) 签名：埸y 狐 导师签名： 日期。冗厶 第一章引言 编码理论是一门年轻的学科，它源于现代通信技术与电子计算机技术 中差错控制研发的实际需要早在1 8 世纪后期，就有关于某个特定码的构 造及解码算法的论文，如b c h 码但直到1 9 4 8 年，美国数学家c e s h a n n o n 发表的著名论文”am a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n ”，首次阐明了在有 干扰的信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，开 创了一门在现代科学技术中具有重要意义的崭新学科，即信息论编码理 论是信息论的一个专门分支 g i l b e r t ，m a c w i l l i a m s ，s l o a n e ? 于1 9 7 4 年在 ”c o d e sw h i c hd e t e c td e c e p t i o n ”一文中，首次提出了认证码，近年来，随着 计算机技术的日新月异，认证理论做为编码理论的一个重要分支，已在信 息安全领域发挥了重要的作用编码理论主要讨论的是信源编码和信道编 码在信道编码理论的研究中，有两大主流，一是不断提出新的方法，改进 构造出性能更好的码；二是研究在引入某种代数结构后的码的界我们所 研究的认证码及认证理论，就是从这两条主流出发，加以研究的一方面， 构造性能更好的认证码，另一方面，研究认证码的界，这里主要考虑的是最 大伪造概率和最大替换概率下界目前，处理传输信息的认证，主要有以下 三种形式，即无条件安全认证码，信息认证码，以及数字签名信息认证码 与数字签名分别对应一种对称加密技术与不对称加密技术，其优点是密钥 的可重复利用性大大降低了网络数据流量，但是随着计算机计算能力的不 断升级，对称加密与不对称加密的安全性，不断遭受质疑，一个个加密标准 被证明无法面对越来越强大的信息攻击作为唯一一种可以应对拥有无限 计算能力攻击的认证方法，研究其性质以及构造方法，具有很大的理论意义 与实际意义 1 1 认证码概率界问题的来源与研究现状 1 1 1 认证码概率界问题的来源 1 2 0 0 9 上海大学硕士学位论文 2 认证码源于通信编码理论，在保护数据安全传输方面有着不可替代的 研究意义当今的社会是信息化的社会，我们已不满足于将绝密信息锁于 密码箱中，或者人工进行传递，如何在信息传递通道上，安全的传递机密 信息，验证信息来源，是我们最为关心的问题。认证码理论所提供的数学模 型，正是为处理此类问题应运而生的，认证码最早是由g i l b e r t ，m a c w i l l i a m s 和s l o a n e 于1 9 7 4 年在。c o d e sw h i c hd e t e c td e c e p t i o n ”一文中提出的，认 证理论的数学模型则是由s i m m o n s 1 6 1 在8 0 年代初期，在。a u t h e n t i c a t i o n t h e o r y ”中建立起来的 图1 1 1 ：经典的认证模型 袭 它表达了这样一个信息传递的问题：即考虑一个信息发送者，一个信息 接收者在一个不安全的信息通道上传递信息，而他们的对手试图以伪造信息 和替换信息两种方式两种方式破坏这种通信，即所谓的模仿攻击和替换攻 击我们称信息发送者发送的信息为源语句，记作s ，其取自一个有限的源语 句集合s ( 8 s ) 源语句通过一一映射，且只有信息收发双方知道的编码规 则e e ( e 为所有编码规则集合) ，加密成对手无法识别的信息m m ( m 为 所有信息集合) 对于e e ，用e ( s ) 表示源语句s 经编码规则e 得到的信息， 定义m ( e ) = e ( s ) l s s ) ，则信息接收者接受认证信息当且仅当m m ( e ) ， 进而对信息m ，进行了解密te - 1 = 8 e ( 8 ) = m ( e 是一一映射，故e - l e 有 意义) 一个认证码的最大的成功模仿攻击和替换攻击的概率表现了该码应对 强大信息攻击的能力，我们记对手最大的成功模仿攻击和替换攻击的概率 分别为片和b 因此，为了构造性能更好的认证码，研究片和p s 的下界 2 0 0 9 上海大学硕士学位论文 3 是十分有意义的，其处于认证码研究领域的中心位置，所有其他问题都是围 绕它逐步展开的 1 1 2 研究现状与研究方法 认证理论是- - f 涉及代数编码理论、纠错码理论、组合设计、密码学、 仿射几何、有限群、代数几何的交叉热点学科g i l b e r t ，m a c w i l l i a m s ，s l o a n e 于1 9 7 4 年在”c o d e sw h i c hd e t e c td e c e p t i o n 一文中，首次提出了认证码以 来，在国内外已经有了很多重要的研究成果，下面对国内外已经有的研究 成果给出综述 在1 9 8 5 年，s i m m o n s 在”a u t h e n t i c a t i o nt h e o r y 一文中，证明了对于任 意一个i s i = k ，i m i = t ，的认证码，有 日石k ，p s 暑 ( 1 1 1 ) t ， u 一上 。 以及对于系统认证码【1 5 】，有 p s 毋 ( 1 1 2 ) 另外，s i m m o n s 1 6 ，1 7 还发现，毋等等号成立，当且仅当 船( e ) = i k ( 1 1 3 ) e e e m 6 m ( e ) 。 之后，m a s s e y 和s t i n s o n 1 8 分别在1 9 8 6 年和1 9 8 8 年发现了，b 等 等号成立，当且仅当 瓷嚣糌鞣瓣= 等1 ， 。e i m 肘( e ) ) 船( e ) 船( e 一1 ( m ) ) 口一。 卜“。7 对于肘中的每一对m m 都成立 s i m m o n s 1 6 】和b r i c k e l l 2 0 】等人又分别在1 9 8 4 年与1 9 8 5 年，从信息论 的角度出发分别证明了片和b 下界的另一个估计，即著名的s i m m o n s 界。 片2 - i ( m ；e ) ，p s 2 一日( e i m ) ，i s i 2 ( 1 1 5 ) 其中，h ( x ) 表示随机变量x 的熵，而，( x ；y ) 表示随机变量x 和y 的交 互信息 2 0 0 9 上海大学硕士学位论文 4 s i m m o n s 界，让我们能更好地理解认证码保护数据的机制，从中可以 看出，为了更好地保护数据使其不被伪造( 即，使得成功伪造信息的概率片 尽可能的小，一方面，我们不得不泄露关于编码规则的许多信息；另一方 面，为了更好的保护数据不被替换，编码规则的不确定怀需要尽可能的大 也就是说，我们不能把所有的关于编码规则的熵都花费在保护数据不被伪 造上，同时需要用一定量的编码规则的不确定性来减少替换攻击成功的概 率于是，数学家们做了许多的研究工作以调和这对矛盾，并且构造出了许 多性质很好的认证码子类 认证码与组合设计有着密切的联系1 9 9 2 年，b r i c k e l l 和s t i n s o n 2 3 1 等人第一次将认证码与平衡不完全区组设计联系在一起，并且发现片= 尝 和p s = 西k - 1 时，b 业k ( k 坐- 1 ) 等号取到，当且仅当编码规则矩阵为一个 ( u ，k ，1 ) 一b i b d 且信源和编码规则都是等概率分布 从此，组合设计方法，开始引入到认证码的研究之中目前，这样的组 合设计主要包括。横截设计，正交区组设计及平衡不完全区组设计等 1 9 9 3 年，s t i n s o n ? 】进一步提出，对于任何一个i s l = k ，l m i = v 的认 证码，若片= p s = 尝= ，则有 ( 1 ) b z 2 等号取到，当且仅当认证矩阵是一个正交阵o a ( 1 ，k ，1 ) 且认证 规则是等概率的 ( 2 ) b k ( t 一1 ) + 1 等号取到，当且仅当认证矩阵是一个正交阵o a ( 1 ，k ，a ) 且认证规则是等概率的，其中，a = 巡掣 s t i n s o n 1 9 1 还对一类特殊的认证码对称认证码进行了一系列研究 继s t i n s o n 等人在仿射空间，射影空间对认证码的组合特征的研究后， 万哲先等人【2 】，于1 9 9 4 年，开始把问题延伸到比仿射空间稍复杂一些的辛 空间k 卸( 日) 中来构造系统认证码，并且成功构造了参数为 后= ! ! 群，6 = 9 2 ( t ，一1 ) ，口= ! ! 醋口2 ( t ，一，t 1 ) + m 1 ( 1 1 6 ) 的系统认证码并且给出了编码规则空间服从均匀分布时，成功伪造攻击概 率和成功替换攻击概率，分别为 片= 鬲i k ，p s = 三 ( 1 1 7 ) 以及参数为 k = 9 2 t ，b = ( q 一1 ) q 2 俨3 ， = q 耻2( 1 1 8 ) 2 0 0 9 上海大学硕士学位论文 5 的系统认证码，并且给出了编码规则空间服从均匀分布时，成功伪造攻击 概率和成功替换攻击概率，分别为 b = 言，b = 再1 ( 1 1 9 ) 口口一l 1 9 9 4 年，t j o h a n s o n ，g k a b a t i a n s k i i 和b ，s m e e t s 等人 2 4 】，利用代数几何的 手法建立了认证码理论与纠错码理论的内在联系在给定局，b 和编码规 则数的条件下，构造一个具有最大信源集的认证码，等价于，在给出定最小 距离条件下，构造一个具有最大基数和码长的纠错码即，假设存在一个参 数为( 扎，m ，d ) 的纠错码，使得如果c c 对于所有入日，有c + m c 那 么就存在一个对应参数为 蚓= m 口，i e i = 日= 昙，p s = l 一罢 ( 1 “o ) 的认证码 1 9 9 6 年，g k a b a t i a n s k i i 等人【1 5 】，进一步发展了这一结果 2 0 0 4 年，o g a t a 、k u r o s a w a 、s t i n s o n 和s a i d o 等人在研究b i b d 理论 2 2 】时，给出了分裂认证码在i s i = 七，i e i = l m i = b ，l e ( s ) l = r 确定且编码 规则概率空间服从均匀分布时的最大伪造概率下界公式为 毋( 口，r ) = 百k r ( 1 1 1 1 ) ”u n i v e r s a lh a s h i n g ”这个新的名词首先是由c a r t e r 和w e g m a n 6 】在1 9 7 9 年提出的h a s hf u n c t i o n 在信息认证领域如数字签名等有着广泛的用途， 它与认证码也有着很重要的联系在【7 】，p 1 8 中，a v iw i g d e r s o n 形象的把 u n i v e r s a lh a s h i n g 称为每个计算科学家都应掌握的最基本的技巧在1 9 8 0 年，d v s a r w a t e 1 0 把p l o t k i n 界引入到g u ( ；n ，m ) h a s h 族中，得到了 而n - m (12)1 11 21 了_ = 百( m i n j 在1 9 9 4 年，d r s t i n s o n 1 9 在研究一u ( ；n ，m ) h a s h 族时，得到了 而舀 ( 1 1 1 3 ) 在1 9 9 5 年，d r s t i n s o n 8 1 在研究e 一u ( ；佗，仇) h a s h 族时，得到了 = 凳杀面，(1114)m 1一几十m ( 几一j 2 0 0 9 上海大学硕士学位论文 6 并且在研究一s u ( n ；n ，m ) h a s h 族时，又得到了 1 + 而氅若三( 1 1 1 5 1 ) 仃屺l n j 十m n 1 2 本文主要工作 本文主要做了以下几方面的工作 一在3 1 中，在分裂系统码的基础上，提出了强分裂系统码，通过平衡 化方法证明了，在参数i s i = 膏，i e i = b ，i m i = 钞，e l q - c 2 + + = 仇( i ，( 岛) l = g ，i = 1 ，2 ，k ) 下，并且编码规则概率空间服从均匀分布时的最大伪造概 率的下界： rb1 芹( 七，6 ， ，m ) ：罕 ( 1 2 1 ) 二在3 2 中，又进一步提出了( c 1 ，c 2 ，c k ) 型强分裂系统码，其中q = l f ( s i ) l ，通过新的平衡化方法证明了在上述参数下，且x 0 = m a x m i n ( x ，x 2 ， ) i z l c l l _ - x l c 2 + + x k c k = 口；x i n ，i = 1 ，七) 时的最大伪造概率的下 界为 r 土1 砰( ，b ， ，m ) ( c 1 忽，c 。) = 半 ( 1 2 2 ) 三在3 3 中，令e 1 ( 扎，m ) = 而不( 。n - 2 _ r n l 。2 9 ) 。( i o n g + m 两n - l n ) ) 巧而，e 2 ( n ，m ) = 莉n - m ， e 3 ( n ，m ) = 篙幂瓷高等警写写麓宁，还有方程2 m 一1 ) z 2 一【仇m 一1 ) ( 1 0 9 2 n 一 3 ) + 6 扎一2 m 一4 】z + ( m 一2 ) ( n m 一2 n + 1 ) + ( n m ) l 0 9 2 佗= 0 的两个解中更 小的解为e 4n ，仇) 我们把s i n g l e t o n 界引入到一u ( ；n ，m ) h a s h 族中，得到了 n l o g m n - 1 ( 1 2 3 ) e 通过比较1 1 1 2 与1 2 3 ，得到了当l l ( n ，m ) 时，新的界更好 同时，又把s i n g l e t o n 界引入到一u ( ；n ，m ) h a s h 族中，得到了 葺等 ( 1 2 4 ) m z 十z 通过比较1 1 1 3 与1 2 4 ，得到了当1 3 ( 扎，m ) 时，新的界更好，而当 e a ( n ，m ) 击时。旧的界更好 2 0 0 9 上海大学硕士学位论文 7 另外，还把s i n g l e t o n 界引入到一s u ( n ；n ，m ) h a s h 族中，得到了 罱 m z il 一) ( 1 2 5 ) 通过比较1 1 1 4 与1 2 5 ，得到了当1 e a ( n ，m ) 时，新的界更好，而当 e 4 ( n ，仇) e2 示1 时，旧的界更好 2 0 0 9 上海大学硕士学位论文8 第二章预备知识 这一章我们首先给出关于经典纠错码理论的基本知识和简介然后对 认证码，系统认证码，系统分裂码的基本情况给出介绍，并列举例子 2 1 经典的纠错码理论简介 编码理论仍然是一门年轻的学科它导源于现代通信技术与电子计算 机技术中差错控制研究的实际需要美国数学家仙农( c e s h a n n o n ) 在 1 9 4 8 年发表的著名论文。通信的数学理论”开创了一门在现代科学技术中 具有重大意义的崭新学科，即信息论编码理论是信息论的一个专门分支 汉明( r w h a m m i n g ) 在1 9 5 0 年发表的论文“检错码与纠错码”是开 拓编码理论研究的第一篇论文以后，纠错码受到了越来越多的通信和教学 工作者，特别是代数学家的重视，使纠错码无论在理论还是在实际中都得 到飞速发展 5 0 年代至8 0 年代，是纠错码理论飞速发展的重要时期，并在实用中也 取得了巨大成功如美国在7 0 年代初发射的。旅行者”号飞船中，成功的 应用了纠错码技术，使宇宙飞船在极其遥远的距离( 3 0 亿公里) ，向地面传 回了天王星、海王星等星体的天文图片，发现了天王星的9 个卫星和光环 以及海王星的6 个卫星和光环等许多极其宝贵的资料若不应用纠错码， 这些成就的取得是不可想象的 自8 0 年代初以来，戈帕等从几何观点讨论分析码，利用代数曲线构造 了一类代数几何码。在这些码中，某些码的性能达到了香农码所能达到的性 能由于代数几何码是一类范围非常广的码，在理论上已证明它具有优越 的性能，因而一开始就受到了编码理论工作者，特别是代数几何学家的重 视，使代数几何码的研究得到了非常迅速的发展，取得了许多成果现在， 代数几何码的研究方兴未艾 目前，利用纠错码降低各类数字通信系统以及计算机存贮和运算系统 中的误码率，提高通信质量，延长计算机无故障运行时间等，在美国等西方 2 0 0 9 上海大学硕士学位论文9 国家中已作为一门标准技术而广泛采用而且纠错码技术还应用于超大规 模集成电路设计中，以提高集成电路芯片的成品率，降低芯片的成本不仅 如此，自7 0 年代末以来，纠错码技术已开始渗透到很多领域因此，可以 预料，随着科学的进步和实际的需要，纠错码理论必将进一步发展，它的应 用范围必将进一步扩大 下面我们给出编码理论中的一些基本概念设a 为q 元集合，信息流 m = m o m l m 2 a ，将信息流m 依次分成若干组，每组k 个比特，然后采 用某个编码规则，对每组进行编码编码的目的是使传送的信息能够抵抗 信道的干扰，收到者能正确译码 定义2 1 1 1 4 】记a n = ( 翮，x l ，) i 盈a ，i = 1 ，2 ，礼 ，对任意 z ，y a n ，称 d ( x ，y ) = i i l l i 礼，甄犰 i 为z 与秒之间的h a m m i n g 距离，称 u ( z ) = j i l l i n ，露o ) l 为z 的h a m m i n g 重量( 权) h a m m i n g 距离满足通常距离的基本性质：非负性，对称性和三角不等 式性 定义2 1 2 4 】a n 的每个非空子集c 叫做a 上一个码，印中元素叫 做字，c 中元素叫做码字，扎称为码字的长度，简称码长 如果i c i = 1 ，则称c 为平凡码，否则称c 为非平凡码假定c 为非平 凡码，记 冗：了l o g - qi c i ：扎一1l o g i qi c i 礼 d = m i n d ( x ，y ) l x ，y c ，z y ) 伽= m i n w ( x ) l x c ，z o ) p2 够够 d ( z ，c ) i z c c 则称冗，d ，w 和p 分别为码c 的码率，极小距离，极小权重和覆盖半径 定理2 1 3 1 4 1 如果码c 的极小距离为d ，则c 可以检测d 一1 个随机 错误，可以纠正 掣】个随机错误 2 0 0 9 上海大学硕士学位论文 1 0 每个数学分支都有主要的研究对象，研究这些对象的基本性质，并且研 究基本对象的分类的问题，要求同一类的对象具有相同的基本性质在纠错 码理论中，对于固定的q 元集合a ，我们也把所有g 元纠错码加以分类，使 得同一类中的纠错码有相同参数n ，m ，d 最容易想出的是以下三类变换 4 】 ( 1 ) 分量置换设c 是q 元码( n ，m ，d ) ，对于集合 o ，1 ，2 ，钆一1 ) 的每 个置换仃，我们把c 中每个码字c = ( c 1 ，c , 2 ，c r i ) 变成 仃( c ) = ( ( 1 ) ，( 2 ) ，c a ( n ) ) a n 即把码字c 的各分量作置换盯，新的集合 盯( c ) = 口( c ) i c c ) 给出具有相同参数( 扎，m ，d ) 的q 元码 ( 2 ) 元素置换设，是集合a 到a 的一一映射( a 中留个元素的一个 置换) ，f ( 0 ) = 0 于是每个码c a 竹，将码字c = ( c 1 ，c 2 ，c n ) c 变成 ，( c ) = ( ，( c 1 ) ，( c ，1 ) ) a n ，易知新的码 f ( c ) = ，( c ) i c c ) 与c 具有相同的参数死，m ，d ( 3 ) 码的平移设c 小，对每个 a n ，新的码 = c + t ，= c + v l c c ) 与c 具有相同的参数他，m ，d 定义2 1 4 【4 】设c 和c 是两个q 元码，如果通过有限次上述三种变换 把c 变成，称c 和是等价的码 一个q 元( 礼，m ) 码可以排成一个m 扎阶矩阵，其每一行是一个码 字以后我们经常会用这种矩阵的形式来表示一个口元( n ，m ) 码第( 1 ) 种 变换对应于将矩阵中的列进行重新排列；第( 2 ) 种变换对应于将矩阵中某 一固定列中的字符进行置换不难看出，在上述三种置换运算下，码字之 间的h a m m i n g 距离保持不变因此，两个等价的码c 和有相同的参数 ( n ，m ，d ) ，它们可以检查和纠正相同数目的错误 2 0 0 9 上海大学硕士学位论文 1 1 定理2 1 5 ( s i n g l e t o n 界) 【3 】如果存在q 元( n ，m ，d ) 码，1 d n 一1 ， 则 m q n - d + 1 定义2 1 6 3 】设c 是q 元( n ，m ，d ) 码，如果m = q n - d + l ( 即n = k + d - 1 ) 当d = 扎一k + l 时，则c 叫做极大距离可分码，简称为m d s ( m a x i m a l d i s t a n c e s e p a r a b l e ) 码 关于m d s 码的概念和性质，我们将在2 5 和2 6 节给出详细介绍 下面由p l o t k i n 给出的界只对二元码有效 定理2 1 7 ( 二元码的p l o t k i n 界) 3 】如果存在参数为( n ，m ，d ) 的二元 码，并且2 d 扎，则 m ， p f ( k ，b ，t ，) = m i n p z ( c ) ic a s ( k ，b ，口) ) 定理2 2 4 2 5 l p z ( k ，6 ，秒) = f k b v b 2 3 系统认证码的基本概念和性质 定义2 3 1 当一个认证码( s ，e ，m ，妒) 除了满足定义2 2 1 中的( a ) ( b ) 外 还满足 ( c ) 妒( s 1 ，e 1 ) = 妒( s 2 ，e 2 ) ，则8 1 = 8 2 ，v s l ，8 2 s 则称此认证码为系统码 定义2 3 2 设c i a ( k i ，b ，m i ) 且c i = ( s i ，e ，m d ，其中i = 1 ，t ，s = u s i ，m = u m i ( u 表示不相交的并) ，则称c = ( s ，e ，m ) 为码c 1 ，c 2 ，c 的 并，记为c = uc i 注当= 1 ( i = b ，t ) ，c 显然为系统码 对于系统码c = ( s ，e ，m ) a s ( k ，b ，u ) ，令s = 8 1 ，s 知) ，m i = e ( s i ) l e e ) ，c i = ( s d ，e ，姚) ，则c i a ( 1 ，b ，m i ) 且s = u s i ) ，m = u m , ，c = uc i ，p z ( c ) = m a x ip i ( c i ) p z ( c i ) 记h ( c ) = i m i ( c ) i ( i = 1 ，七) ，为方便起 见，不妨设t l ( c ) st d c ) 且令k ( c ) = t 1 ( c ) ，t m ( c ) = t k ( c ) 例2 3 3 若s = a ，b ，c ) ，e = 0 ，1 ，8 ) ，m = l ，2 ，9 ) 则有对应参数的 系统码c 3 a s ( 3 ，9 ，9 ) 如下： 2 0 0 9 上海大学硕士学位论文 1 5 lo lo l0 01 01 o1 oo 0 0 0 0 01 00 00 01 00 o0 l l 1o 10 由系统码定义中的条件( c ) 可知，对应的设计表每列中的元素必须相 同而且，对应于同一个源语句的任意两列之间无交，如第1 列至第3 列 p i ( c 3 ) = 1 3 ，p s ( c 3 ) = 1 3 我们记； p s ( k ，b ，”) = m i n p s ( c ) ic a ( k ，b ，可) ， p 善( 七，b ，口) = m i n p s ( c ) ic a s ( k ，b ，钉) 定理2 3 4 2 5 】 p f ( k ，b ，t ，) = f b t l v l k l b 2 4 分裂系统码的基本概念和性质 定义2 4 1 设s 、e 、m 是非空有限集合，分别为源码集合、密钥集合 和密文集合妒为sxe p ( m ) 的一个映射，其中p ( m ) 为m 的幂集如 果妒满足下列条件t ( a ) 对于任意的和任意的； ( b ) u ( 叩) s x e 妒( 8 ，e ) = 肛 则称c = ( s e ，m ，妒) 是一个分裂认证码特别当l 妒( s ，e ) i = 1 ，则c = ( s ，e ，m ，妒) 为认证码 定义2 4 2 当一个认证码( s ，e ，m ，妒) 除了满足定义2 4 1 中的( a ) 、( b ) 外，还满足( c ) v s i ，s 2 s ，8 1 8 2 ，p ( s 1 ) n , ( s 2 ) = d ，其中弘( s ) = u e 6 e e ( s ) ，则 称此分裂认证码为分裂系统码 2 0 0 4 年，o g a t a 、k u r o s a w a 、s t i n s o n 和s a i d o 等人在研究b i b d 理论【2 2 1 o 0 l 0 1 o 1 o 0 o 1 0 1 o 0 o o 1 1 0 0 0 o 1 0 1 0 o 0 1 o 0 l 0 o 1 o l 0 o 1 o 0 l o 2 0 0 9 上海大学硕士学位论文1 6 时，给出了分裂认证码在i s i = k ，i e i = i m i = b ，i e ( s ) i = r 确定且编码规则概 率空间服从均匀分布时的最大伪造概率下界公式为 毋( 蛐，叩) = 等 ( 2 4 1 ) 令l 勺( s t ) i = r i j ，记r = 【r i j k b ，且记a ( k ，b ，口，r ) = c ic 为具有参数k ，6 ，v ，r 的分裂认证码) 如果r i j = l ( v i ，歹) ，显然为认证码，则简记a ( k ，6 ，可，r ) = a ( k ，b ，口) 记a s ( k ，b ，秽，r ) = cjc 为具有参数k ，b ，口，r 的分裂系统认证码) 定 义p l ( k ，b ，t ，r ) = m i n p 1 ( c ) ic a ( k ，b ，口，r ) ，尸穸( 七，b ，r ) = m i n p z ( c ) ic a s ( k ，b ，移，冗) 定理2 4 3 2 6 】 r 圣；三! 圣垒! 鱼1 局( 七，b ，t ，r ) = l 卜j 定理2 4 4 2 6 】 定理2 4 5 2 6 】 1 ，忌) ，则有 当f 勺( s ) f = r ，r = r j 时，且满足r ks 钉，r k v ，则有 p f ( k , b , v , r ) = 竿 当i 勺( s t ) i = r i ( i = 1 ，七) 时，且满足氅1r i v r i ( i = 芹( k , b , v , r ) ：学k 2 0 0 9 上海大学硕士学位论文 1 7 第三章强分裂系统码 本章从分裂认证码出发，构造了一种新的码：强系统认证码利用这种 特殊的码与一般系统认证码的关系，得到了这种码的最大模仿概率芹的 下界公式；另外，还进一步探讨了c i ( i = 1 ，2 ，k ) 固定的( c 1 ，c 2 ，) 型 强分裂系统码的印的下界公式，并且如何把一个已知的( c 1 ，c 2 ，强) 型强 分裂系统码转变到芹。最小的( c l ，0 2 ，c k ) 型强分裂系统码 3 1 强分裂统统码 定义3 1 1设se ，m 是三个非空有限集合( 分别称为源语句集合， 编码规则集合，信息集合) ，妒：e s _ p ( m ) ( m 的幂集) 是一个映射， 这里把妒( ，8 ) ( f e ，s s ) 记为，( s ) ，又设c l ，e 2 ，依为正整数，m ( s ) = u ，e ，( s ) ( s s ) ，若满足： ( 1 ) 1 u 。s u ，e ，( s ) = m ，且至少有一个s s 满足l ，( s ) l 1 ； ( 2 ) f ( 8 i ) n f ( s j ) = 囝( 8 i ) ； 则称( s e ，m ，妒) 为一个分裂码 注t 若在上面( 1 ) 中，对任意8 s 都有i ，( s ) j = 1 ，则称其为认证码 若进一步满足； ( 3 ) m ( 魂) nm ( s j ) = i z i( 8 i s j ；8 i ，勺s ) ； 则称其为分裂系统码如果还满足； ( 4 ) m ( s ) = u 鐾1a ；，其中a ；na ；= d ( i j ) 且i ，( s ) na 引= 1( s s ) ； ( 5 ) i a 奢i = i a i 伤j 2 ；j l ，力= 1 ，2 ，c ) ； 则称其为( c 1 ，c 2 ，c 知) 型强分裂系统码 注：由上可知i f ( s i ) l = c i ( i = 1 ，七) 在下文中，我们记a ( k ，b ，t ，m ) ( c 。 c 2 a ) 为具有参数 s f = k ，f e i = b ， m f = t ，的所有( c l ，c 2 ，c k ) 型强分裂系统码的集合，其中m = c 1 + c 2 + + e k 并记a ( k ，b ，秽，m ) = u c 。m ，c k ) 肿( m ) a ( 七，b ，u ，m ) ( c 1 恕，c i ) ，其中n 奄( m ) = ( c 1 ，c 2 ，银) ic i n “= 1 ，七) ，c 1 + c 2 + + 铅= 仇) ，若c a ( k ，b ，钉，m ) ， 2 0 0 9 上海大学硕士学位论文 1 8 则称c 为参数是( 七，b ， t 3 ，m ) 的强分裂系统码 定义8 1 1 2 对于强分裂系统码c a ( k ，b ，可，m ) ，其最大的伪造概率定 义如下： 辟( c ) = 嬲m 掣竹l tu 另外，定义 芹。( 七，6 ， ，m ) = m i n 芹+ ( c ) ic a ( 尼，b ，可，m ) ) ； 芹( 七，b ，口，m ) ( 。，。：，。) = m i n p 穸( d ) ic a ( k ，b ， ，m ) ( c 。，c 2 ，) ) 定理3 1 3 【2 5 】对于参数为( 七，6 ，口) 的系统认证码，有 芹( 蛐，移) ：盥b 定理3 1 4对参数为( 七，6 ，t ，m ) ( m 七) 的强分裂系统码，有 吼蛐 m ) = 卓 证明对于参数为( m ，b ，t ，) 的系统认证码，由定理3 1 3 知芹( m ，b ，t ，) = 世卫b 址，于是存在系统认证码d ( 雪，亩，厨) 满足砰( d ) = 倒i 迦bl l ，其中闻= m ，l e l = b ，l m l = t ， 令移= m r + t ( r t z + ；0 t 0 由文献 2 5 】知，此时v s 雪，有i m ( s ) i = r ，或者l m ( s ) l = r + 1 设 a = s 雪ll 必( s ) j = r ) ，b = s 雪li m ( s ) = r + 1 ) ，则i a l = m t ，i b l = t ( 1 ) 若m t 后一1 ，取c l = 1 ，c 2 = 1 ，一2 = 1 ，c 七一1 = m - t 一( 七一2 ) ，= t ， 则c 1 + c 2 + + = m 此时可设a 为 si = 1 ，七一1 ；j = 1 ，q ，b 为 s 幻l 歹= 1 ，t ) ( 2 ) 若m t 七，取c l = c 2 = = 一1 = 1 ，镪= m 一七十1 则c 1 + c 2 + + = m 此时可设a 为 sli = 1 ，m t ；j = 1 ) ，b 为 s 莳sii = m t + 1 ，k ；j = 1 ，c 令= s l ，s 2 ，乳) ，= ，ll ( s i ) = 蛎二1 ，( s 玎) ) ，m 7 = 肪，钙= 厨( s j ) ，m ( s 1 ) = u 各1a ，则( s ，m ) 为一个强分裂系统码事实上，此 时有m ( s i ) nm ( ) = d ( i 歹) ，这就说明了c ( ，m ) a ( k ，b ， ，m ) 且有 吼：宇 2 0 0 9 上海大学硕士学位论文 1 9 设c ( s ，e ，m ) 为参数为( 七，b ，秒，m ) ( 。，。：，a ) 的强分裂系统码，其中i f ( s i ) l = c i ( i = 1 ，七) ，s ( s i ) = 佻1 ，m i 2 ，m i q ) 可构造一个普通的系统认证码 o ( d ，雪，廊) ，其中= li = 1 ，髓歹= 1 ，q ) ，雪= ，i ，( ) = ，( 吼) j ( 表示s ( 8 t ) 的第j 个分量) ，f e ，砑= m 由强分裂系统码的定义可知， 0 ( ，窗，财) 为参数为( c l + c 2 + + c k ，b ，”) 的系统认i i e t i 马 由于 即) ：枷m a x 嘣m ) _ 枷m a x ，蠹，嘣肛糌掣，