岳孟田，李增提

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

距離正則圖相關(guān)聯(lián)的兩類(lèi)認(rèn)證碼

岳孟田1，李增提2

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

利用了序?yàn)椋╯，t）的距離正則圖和直徑為d的對(duì)極的距離正則圖構(gòu)造了2類(lèi)Cartesian認(rèn)證碼，并且計(jì)算了它們的參數(shù)及模仿攻擊成功的概率PI和替換攻擊成功的概率PS。

距離正則圖；認(rèn)證碼；團(tuán)

設(shè)S，E和M是3個(gè)非空有限集，f：S×E→M是一個(gè)映射，且滿足下面的條件：

1）映射f是滿射；

2）對(duì)任給的m∈M和e∈E，如果存在一個(gè)s∈S，使得f（s，e）＝m，這樣的s是被m和e所唯一確定的，則稱四元組（S，E，M；f）是一個(gè)認(rèn)證碼。

設(shè)（S，E，M；f）是一個(gè)認(rèn)證碼，S，E和M分別稱為信源集、編碼規(guī)則集和信息集；f稱為編碼映射。對(duì)s∈S，e∈E，m∈M，若m＝f（s，e），則稱信源s在編碼規(guī)則e下加密成信息m，或簡(jiǎn)單的說(shuō)m包含編碼規(guī)則e，也說(shuō)s是相應(yīng)于信息m的信源，基數(shù)｜S｜，｜E｜和｜M｜稱為這個(gè)碼的參數(shù)。

在文獻(xiàn)［1］－文獻(xiàn)［5］中，萬(wàn)哲先、高鎖剛等已經(jīng)利用有限典型群幾何的子空間構(gòu)造了認(rèn)證碼，并計(jì)算了它們的參數(shù)和成功地模仿攻擊和替換攻擊概率。在本文中，利用序?yàn)椋╯，t）的距離正則圖和直徑為d的對(duì)極的距離正則圖構(gòu)造了2類(lèi)Cartesian認(rèn)證碼，并且計(jì)算了它們的參數(shù)及模仿攻擊成功的概率PI和替換攻擊成功的概率PS。

1 距離正則圖

關(guān)于距離正則圖的概念及有關(guān)知識(shí)，詳見(jiàn)文獻(xiàn)［6］。

設(shè)Γ＝（X，R）是一個(gè)連通圖，對(duì)于X中的任意u和v，設(shè)?（u，v）表示u和v之間的距離，稱u和v是鄰接的，如果?（u，v）＝1，對(duì)于任意頂點(diǎn)u，設(shè)

Γ的距離函數(shù)的最大值稱為Γ的直徑，X的一個(gè)l-子集A稱為Γ的大小為l的團(tuán)，如果A中任意的2個(gè)不同頂點(diǎn)是鄰接的，X的一個(gè)l-子集A稱為Γ的大小為l的d-團(tuán)，如果A中任意的2個(gè)不同頂點(diǎn)的距離是d，空集?規(guī)定是大小為0的團(tuán)（或d-團(tuán)）。

2 序?yàn)椋╨，t）距離正則圖相關(guān)聯(lián)的認(rèn)證碼

在此，假定Γ＝（X，R）是有n個(gè)點(diǎn)的序?yàn)椋╨，t）的距離正則圖，設(shè)C表示Γ所有團(tuán)的集合。

構(gòu)作Ⅰ 設(shè)信源集S是Γ中的（t＋1）l點(diǎn)，對(duì)任意x∈X，設(shè)ex是一個(gè)從S到Γ（x）的雙射，E＝M＝X。對(duì)任意信源s和編碼規(guī)則x，定義f（s，x）＝ex（s），那么（S，E，M；f）是一個(gè)認(rèn)證碼。

3 對(duì)極距離正則圖相關(guān)聯(lián)的認(rèn)證碼

在此利用距離正則圖的子圖構(gòu)作了2類(lèi)較優(yōu)的認(rèn)證碼，豐富和發(fā)展了距離正則圖的應(yīng)用。

［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］高鎖剛.利用有限域上酉幾何構(gòu)作兩類(lèi)Cartesian認(rèn)證碼［J］.高校應(yīng)用數(shù)學(xué)學(xué)報(bào) 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；責(zé)任編輯：李 穆

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

岳孟田（1973-），男，河北廊坊人，副教授，碩士，主要從事代數(shù)組合方面的研究。