Johnson图相关联的一类新的认证码

岳孟田，李增提

（1.廊坊师范学院 科研处，河北 廊坊 065000；2.廊坊师范学院 数信学院，河北 廊坊 065000）

Johnson图相关联的一类新的认证码

岳孟田1，李增提2

（1.廊坊师范学院 科研处，河北 廊坊 065000；2.廊坊师范学院 数信学院，河北 廊坊 065000）

利用Johnson图J（dm，d）得到了新的认证码，并进一步得到了这类码的参数.在假定编码规则按等概率分布选取时，计算出这类码的模仿攻击成功和替换攻击成功的概率.

Johnson图；认证码；团

MSC 2010：05E99

令S，E与M为非空有限的集合，f∶S×E→M为S到M映射，若以下条件成立：1）f为S到M满射；

2）任意m∈M与e∈E，若有s∈S，满足f（s，e）＝m，且s被m与e确定.把四元组（S，E，M；f）称为认证码.

令四元组（S，E，M；f）为认证码，M，S与E分别叫做信息集，信源集与编码规则集；f叫做编码映射.s∈S，e∈E，m∈M，如果m＝f（s，e），称信源s为编码规则e之下加密为信息m，｜S｜，｜E｜与｜M｜分别叫做码（S，E，M；f）的参数.

文献［1-4］中万哲先，高锁刚，高有等利用有限域上的辛空间和伪辛空间上的子空间构造Cartesian认证码.本文中，用Johnson图J（dm，d）得到了新的认证码，进一步得到了这类码的参数及攻击成功的概率.

1 距离正则图

了解一些关于更多的有关距离正则图知识，请读者参考Brouwer等著作［5］.

令Γ＝（X，R）为连通图.u与v是X中的任意2点，u与v的距离用∂（u，v）表示.u与v是邻接的，若∂（u，v）＝1.对于任意顶点u，设

给定一个基数为n（n≥2d）的集合，设X＝｛A⊂V‖A｜＝d｝.又设J（n，d）表示定义在X上的Johnson图，且A和B是邻接的当且仅当｜A∩B｜＝d-1.Johnson图是一个距离正则图.

命题1 设Johnson图J（dm，d）的基数为l的d-团的个数为u（m，d；l），则

证明考虑从dm个元素中取dl个元素的排列个数.

首先取基数为l的d-团的个数为u（m，d；l），然后得所有d-团的排列个数l！，最后得到d-团中元素排列个数（d！）l，所以从dm个元素中取dl个元素的排列个数为u（m，d；l）l！（d！）l.于是

2 Johson图相关联的认证码

假定Γ＝（X，R）是一个Johnson图J（dm，d），m≥2.

定理1 构造Ⅰ（S，E，M：f）是一个认证码.

证明根据以上构造可知f（s，x）＝ex（s），s∈S，x∈E是一个映射.

对任意y∈M，取x∈E，得到一个双射ex：S→Γd（x）.那么存在s∈S，使得ex（s）＝y，所以f是一个满射.

对于任意x1，x2∈M和y∈E，如果s1，s2∈S，使得f（s1，y）＝f（s2，y），即ey（s1）＝ey（s2），考虑ey为一一映射，有s1＝s2.因此（S，E，M；f）为认证码.

定理2 构造Ⅰ（S，E，M；f）是一个认证码，其参数分别为

那么成功的模仿攻击概率和成功的替换攻击概率分别为

［1］ WAN Zhexian.Furhter construction of Cartesian authentiction codes from symplectic geometry［J］.Northeastern Mathematical Journal，1992（8）：4-20.

［2］ GAO Suogang，GAO You.Using a class of 1-dimensional non-isotropic subspaces in pseudo-sympletic geometry over a Finite Field to Construct PBIB Designs［J］.Northeastern Mathematical Journal，1996（2）：34-42.

［3］ GAO Suogang.Two constructions of Cartesian authentictioncodes from uintary geomety over a finite field［J］.Applied Mathematics A Journal of Chinese Universities，1996（3），343-354.

［4］ YOU Hong，GAO You.Some new construction of Cartesian authentication codes from symplectic geometry［J］.System Sciences and Mathmatical Sciences，1994（4）：317-327.

［5］ BROUWER A E，COHEN A M，NEUMAIER A.Distance-regular graphs［M］.Berlin，Heidelberg：Springer Verlag，1989.

One familie new authentication codes associated with Johnson graph

YUE Mengtian1，LI Zengti2
（1.Department of Scientific Research，Langfang Normal College，Langfang 065000，China；2.Mathematics and Information College，Langfang Normal College，Langfang 065000，China）

Construct one familie new authentication code from a Johnson graph.Moreover we computed its parameters.Assuming that the encoding rules are chosen according to a uniform probability distribution，the probability of successful impersonation attack and substitution attack are also computed.

distance-regular graph；authentication code；clique

O157.4

A

1000-1565（2012）05-0464-03

2012-05-20

国家自然科学基金资助项目（10971052）

岳孟田（1973-），男，河北廊坊人，廊坊师范学院副教授，主要从事代数组合方向研究.E-mail：lfsyky＠163.com

孟素兰）