用射影幾何構作新的A2-碼

張曉寒,王文賢

(1.衡水職業技術學院基礎部,河北衡水 053000;2.河北師范大學數學與信息科學學院,河北石家莊 050016)

用射影幾何構作新的A2-碼

張曉寒1,王文賢2

(1.衡水職業技術學院基礎部,河北衡水 053000;2.河北師范大學數學與信息科學學院,河北石家莊 050016)

利用射影幾何構作了一個新的帶仲裁的認證碼,并計算了它的參數。進一步假設全部規則是按等概率分布選擇的,分別計算了5種攻擊成功的概率。

認證碼;帶仲裁的認證碼;射影幾何

為了防止發方與收方之間的相互欺騙,SIMMONS在普通認證碼的基礎上引入了帶仲裁的認證碼模型(簡記為A2-碼)[1],此模型涉及發方、收方、敵方以及仲裁4個參與方以及5種攻擊。敵方可對系統進行模仿攻擊(I)和替換攻擊(S),發方可進行模仿攻擊(T),收方可進行模仿攻擊(R0)和替換攻擊(R1)。關于這5種攻擊的定義見文獻[2],它們攻擊成功的概率分別記為 PI,PS,PT,PR0和 PR1。仲裁了解通信系統的全部但不參與通信活動,只有當發方與收方發生爭端時才出面解決爭端,因此假定仲裁是誠實的。下面給出 A2-碼的定義。

JOHANSSON在文獻[2]中用射影幾何 PG(3,Fq)構作了2個完備的 A2-碼,李瑞虎等在文獻[3]中用射影幾何 PG(n,Fq),n≥3構作了一類完備的 A2-碼,推廣了文獻[2]中的構作 Ⅰ。筆者用射影幾何PG(n,Fq),n≥5構作了一類新的帶仲裁的認證碼,計算了有關的參數,并證明了它在一定條件下是完備的。

1 射影幾何的預備知識

由文獻[4]可知下面的命題成立。

由文獻[5]對于 F(n)q的向量子空間可知下面的命題成立。

由命題2易得下面的推論。

2 A2-碼的構作

證 明 1)由dim(S∪ET)+dim(S∩ET)=dim S+dim ET可知,

dim(S∪ET)=dim S+dim ET-dim(S∩ET)=r+2,故S∪ET是一個信息。

2)設另有 S′,使 S′∪ET=M,則 S′? (M ∩P0),由維數關系 S′=M∩P0=S,唯一性得證。

定理1 上述構作是一個A2-碼。

證 明 1)f,g是滿射。

首先證 f是滿射。由引理1中的1)可知,f已是映射。設M是一個信息,則M∩P0=S是一個信源,由于dim M=r+2>dim S=r,在 M中存在一個2維子空間Q使得Q∩P0={0},于是 ET=Q∪U是一個4維子空間(3-面)且 ET∩P0=U,也就是說 ET是一個發方編碼規則,且S∪ET=M,因此 f是滿射。

再證 g是滿射。g顯然是一個映射。任取一個信源S,必有一個信息M使得M∩P0=S,由于dim M=r+2>dim S=r,所以必存在一個一維子空間W?M,但是W∩P0={0},這樣W∪U=ER是一個2-面,ER∩P0=U,即 ER是一個收方編碼規則,且 ER?M,故 g是滿射。

2)由引理1中的2)可知S由M和 ET唯一確定。

3)若 P(ET,ER)≠0(即 ER? ET)且 f(S,ET)=M,由 M=S∪ET,知 ER? M,因此 g(M,ER)=S,否則g(M,ER)={欺詐}。

定理2 上述構作所得A2-碼具有以下參數:

證 明 1)因為U?(ET∩ER),又 ET包含 ER,c相當于包含在一個給定2維空間中的1維子空間的個數,易得:

2)因為U?(ET∩ER),d相當于求包含一個給定3維空間 ER的滿足ET∩P0=U的4維子空間的 ET的個數。由于一般線性群可遷地作用在同維子空間的集合上,這樣可以設:于是,滿足條件的子空間 ET的矩陣表示具有下面的形式:

其中:v1是任意的(r0-2)維行向量;v2是不為零的(n-r0)維行向量,故經簡單計算可得:

證 明 1)由題意得 ER?ET?M,不妨設U=(e1,e2)T,ER=(e1,e2,e3)T,P0=(e1,e2,e4,…,er0,er0+1)T,M=(e1,e2,e3,e4,…,er,er0+1,er0+2)T。

于是,滿足條件的子空間 ET的矩陣表示具有下面的形式:

其中:v1是任意的(r-3)維行向量;v2是 Fq中的任意元素,故易得所求個數為qr-2。

2)用同1)類似的方法計算即得。

引理4 若 M1與 M2是共同包含發方的一個編碼規則′的2個不同信息,S1與S2分別為 M1與 M2包含的信源,設S0=S1∩S2,dim S0=k,則2≤k≤r-1,并且有如下成立。

2)任取 ER?(M1∩M2),M1∩M2中包含 ER的 ET的個數為qk-2。

證 明 dim(M1∩M2)=dim(S1∩S2)+dim ET′-dim(S1∩S2∩ET′)=k+4-2=k+2,因為 M1∩M 2∩ER=U,dim(M1∩M2∩P0)=dim(S1∩S2)=k,用和引理3同樣的方法可得。

定理3 在構作所得的A2-碼中,若編碼規則按等概率分布選取,則各種攻擊成功的概率分別如下:

由定理2和定理3易知這個構作當 r=3時是完備的A2-碼。

[1] SIMMONS G J.Message authentication w ith arbitration of transmitter/receiver disputes[A].Chaum DPriceW L.Proc Eurocrypt′87[C].Berlin:Sp ringer Verlag,1988.151-165.

[2] JOHANSSON T.Lower bounds on the p robability of decep tion in authentication w ith arbitration[J].IEEE Transactions on Info rmation Theory,1994,40(5):1 573-1 585.

[3] 李瑞虎,李尊賢.利用射影幾何構作一類完備的A2-碼[J].通信保密(Communications Privacy),1997,37(3):72-76.

[4] WAN Zhe-xian.Geometry of Classical Groups over Finite Fields[M].2nd Ed.Beijing/New York:Science Press,2002.61-106.

[5] 郭 軍,霍元極,趙東明.有限向量空間中子空間的計數公式及其應用[J].河北師范大學學報(Journal of Hebei Normal University(Natural Science Edition)),2004,28(6):561-564.

[6] SIMMONS G J.Authentication theory/coding theory[A].Advances in Cryptology-Crypto’84,Lecture Notes in Computer Science 196[C].Berlin:Springer-Verlag,1985.411-431.

[7] 李 莉,霍麗君,李志梅.辛幾何上具有仲裁的認證碼的一類新構作[J].河北科技大學學報(Journal of Hebei University of Science and Technology),2010,31(4):294-299.

New construction of A2-codes based on p rojective geometry

ZHANG Xiao-han1,WANGWen-xian2

(1.Department of Basic Courses,Hengshui Vocational Technology Institute,Hengshui Hebei053000,China;2.Mathematics and Info rmation Science College,Hebei Normal University,Shijiazhuang Hebei050016,China)

In this paper,a new construction of A2-codes based on p rojective geometry is given,and the parameters are computed.Assuming that the p robability distribution of all the rules are unifo rm,the p robabilitiesof successful attacks are also computed.

authentication codes;authentication codes w ith arbitration;p rojective geometry

O157.4

A

1008-1542(2011)01-0011-04

2010-07-12;

2010-10-15;責任編輯:張 軍

河北省自然科學基金資助項目(A 2008000128);河北省教育廳自然科學基金資助項目(2007127)

張曉寒(1972-),女,河北武邑人,副教授,碩士,主要從事代數與代數組合論方面的研究。