岳孟田，李增提

（1.廊坊師范學(xué)院 科研處，河北 廊坊 065000；2.廊坊師范學(xué)院 數(shù)信學(xué)院，河北 廊坊 065000）

Johnson圖相關(guān)聯(lián)的一類新的認(rèn)證碼

岳孟田1，李增提2

（1.廊坊師范學(xué)院 科研處，河北 廊坊 065000；2.廊坊師范學(xué)院 數(shù)信學(xué)院，河北 廊坊 065000）

利用Johnson圖J（dm，d）得到了新的認(rèn)證碼，并進(jìn)一步得到了這類碼的參數(shù).在假定編碼規(guī)則按等概率分布選取時(shí)，計(jì)算出這類碼的模仿攻擊成功和替換攻擊成功的概率.

Johnson圖；認(rèn)證碼；團(tuán)

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）稱為認(rèn)證碼.

令四元組（S，E，M；f）為認(rèn)證碼，M，S與E分別叫做信息集，信源集與編碼規(guī)則集；f叫做編碼映射.s∈S，e∈E，m∈M，如果m＝f（s，e），稱信源s為編碼規(guī)則e之下加密為信息m，｜S｜，｜E｜與｜M｜分別叫做碼（S，E，M；f）的參數(shù).

文獻(xiàn)［1-4］中萬哲先，高鎖剛，高有等利用有限域上的辛空間和偽辛空間上的子空間構(gòu)造Cartesian認(rèn)證碼.本文中，用Johnson圖J（dm，d）得到了新的認(rèn)證碼，進(jìn)一步得到了這類碼的參數(shù)及攻擊成功的概率.

1 距離正則圖

了解一些關(guān)于更多的有關(guān)距離正則圖知識，請讀者參考Brouwer等著作［5］.

令Γ＝（X，R）為連通圖.u與v是X中的任意2點(diǎn)，u與v的距離用?（u，v）表示.u與v是鄰接的，若?（u，v）＝1.對于任意頂點(diǎn)u，設(shè)

給定一個(gè)基數(shù)為n（n≥2d）的集合，設(shè)X＝｛A?V‖A｜＝d｝.又設(shè)J（n，d）表示定義在X上的Johnson圖，且A和B是鄰接的當(dāng)且僅當(dāng)｜A∩B｜＝d-1.Johnson圖是一個(gè)距離正則圖.

命題1 設(shè)Johnson圖J（dm，d）的基數(shù)為l的d-團(tuán)的個(gè)數(shù)為u（m，d；l），則

證明考慮從dm個(gè)元素中取dl個(gè)元素的排列個(gè)數(shù).

首先取基數(shù)為l的d-團(tuán)的個(gè)數(shù)為u（m，d；l），然后得所有d-團(tuán)的排列個(gè)數(shù)l！，最后得到d-團(tuán)中元素排列個(gè)數(shù)（d！）l，所以從dm個(gè)元素中取dl個(gè)元素的排列個(gè)數(shù)為u（m，d；l）l！（d?。﹍.于是

2 Johson圖相關(guān)聯(lián)的認(rèn)證碼

假定Γ＝（X，R）是一個(gè)Johnson圖J（dm，d），m≥2.

定理1 構(gòu)造Ⅰ（S，E，M：f）是一個(gè)認(rèn)證碼.

證明根據(jù)以上構(gòu)造可知f（s，x）＝ex（s），s∈S，x∈E是一個(gè)映射.

對任意y∈M，取x∈E，得到一個(gè)雙射ex：S→Γd（x）.那么存在s∈S，使得ex（s）＝y(tǒng)，所以f是一個(gè)滿射.

對于任意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）為認(rèn)證碼.

定理2 構(gòu)造Ⅰ（S，E，M；f）是一個(gè)認(rèn)證碼，其參數(shù)分別為

那么成功的模仿攻擊概率和成功的替換攻擊概率分別為

［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

國家自然科學(xué)基金資助項(xiàng)目（10971052）

岳孟田（1973-），男，河北廊坊人，廊坊師范學(xué)院副教授，主要從事代數(shù)組合方向研究.E-mail：lfsyky＠163.com

孟素蘭）