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；……