距離正則圖相關聯的兩類認證碼

岳孟田，李增提

（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-），男，河北廊坊人，副教授，碩士，主要從事代數組合方面的研究。