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

孟素蘭）