距离正则图相关联的两类认证码

岳孟田，李增提

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

距离正则图相关联的两类认证码

岳孟田1，李增提2

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

利用了序为（s，t）的距离正则图和直径为d的对极的距离正则图构造了2类Cartesian认证码，并且计算了它们的参数及模仿攻击成功的概率PI和替换攻击成功的概率PS。

距离正则图；认证码；团

设S，E和M是3个非空有限集，f：S×E→M是一个映射，且满足下面的条件：

1）映射f是满射；

2）对任给的m∈M和e∈E，如果存在一个s∈S，使得f（s，e）＝m，这样的s是被m和e所唯一确定的，则称四元组（S，E，M；f）是一个认证码。

设（S，E，M；f）是一个认证码，S，E和M分别称为信源集、编码规则集和信息集；f称为编码映射。对s∈S，e∈E，m∈M，若m＝f（s，e），则称信源s在编码规则e下加密成信息m，或简单的说m包含编码规则e，也说s是相应于信息m的信源，基数｜S｜，｜E｜和｜M｜称为这个码的参数。

在文献［1］－文献［5］中，万哲先、高锁刚等已经利用有限典型群几何的子空间构造了认证码，并计算了它们的参数和成功地模仿攻击和替换攻击概率。在本文中，利用序为（s，t）的距离正则图和直径为d的对极的距离正则图构造了2类Cartesian认证码，并且计算了它们的参数及模仿攻击成功的概率PI和替换攻击成功的概率PS。

1 距离正则图

关于距离正则图的概念及有关知识，详见文献［6］。

设Γ＝（X，R）是一个连通图，对于X中的任意u和v，设∂（u，v）表示u和v之间的距离，称u和v是邻接的，如果∂（u，v）＝1，对于任意顶点u，设

Γ的距离函数的最大值称为Γ的直径，X的一个l-子集A称为Γ的大小为l的团，如果A中任意的2个不同顶点是邻接的，X的一个l-子集A称为Γ的大小为l的d-团，如果A中任意的2个不同顶点的距离是d，空集Ø规定是大小为0的团（或d-团）。

2 序为（l，t）距离正则图相关联的认证码

在此，假定Γ＝（X，R）是有n个点的序为（l，t）的距离正则图，设C表示Γ所有团的集合。

构作Ⅰ 设信源集S是Γ中的（t＋1）l点，对任意x∈X，设ex是一个从S到Γ（x）的双射，E＝M＝X。对任意信源s和编码规则x，定义f（s，x）＝ex（s），那么（S，E，M；f）是一个认证码。

3 对极距离正则图相关联的认证码

在此利用距离正则图的子图构作了2类较优的认证码，丰富和发展了距离正则图的应用。

［1］WAN Z.Furhter construction of cartesian authentiction codes from symplectic geomety［J］.Northeastern Mathematical Journal，1992，8：4-20.

［2］GAO S，GAO Y.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］WAN Z.Construction of cartesian authentication codes from unitary geometry［J］.Designs，Codes and Cryptology，1992，2：333-356.

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

［5］高锁刚.利用有限域上酉几何构作两类Cartesian认证码［J］.高校应用数学学报 A辑（中文版）（Applied Mathematic-A Journal），1996，11（3）：343-345.

［6］BROUWER A E，COHEN A M，NEUMAIER A.Distance-Regular Graphs［M］.Berlin：Springer Verlag，1989.

Two kinds of authentication codes associated with distance-regular graphs

YUE Meng-tian1，LI Zeng-ti2
（1.Department of Science and Study，Langfang Normal College，Langfang Hebei 065000，China；2.Department of Mathematics，Langfang Normal College，Langfang Hebei 065000，China）

Two kinds of Cartesian codes are constructed by using a distance-regular graph of order（s，t）and antipodal distanceregular graphs of diameterd，respectively.Moreover，their parameters and the probability of successful impersonation attack and substitution attack are computed，respectively.

distance-regular graph；authentication code；clique

O157.4

A

1008-1542（2012）01-0011-03

2011-09-06；

2011-11-20；责任编辑：李 穆

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

岳孟田（1973-），男，河北廊坊人，副教授，硕士，主要从事代数组合方面的研究。