王秀麗，曹 苗，王利娜

1.中國民航大學理學院，天津300300

2.北京師范大學靜海附屬學校中學部, 天津301600

隨著信息技術的快速發(fā)展，信息安全問題在人們的生活中變得越來越重要.信息安全的兩個主要研究內容是信息的保密和認證.信息保密是通過對所需傳送的信息進行加密來保護信息，防止信息被他人竊取.信息認證的目的在于防止非法用戶進入認證系統(tǒng)，防止接收不明身份的信息，使接收方在收到信息后能夠確認信息的來源是正確的.此后，對兩個方面進行認證：對信息的發(fā)送者和接收者的身份進行驗證；對信息的完整性進行驗證，驗證信息在信道傳輸過程中，是否有被篡改或延遲的情況發(fā)生.

在研究保密問題中，Shannon[1]于20世紀40年代首次利用信息論的方法并提出了完善保密系統(tǒng)的概念.Simmons[2]在研究信息的認證問題時也應用了信息論的方法.這些工作為信息認證奠定了理論基礎.1985年，Simmons[2]首次提出了認證碼的概念，現(xiàn)在認證碼已成為研究認證理論的重要問題之一.1974年，Gilbert 等[3]第一次進行認證碼的構造.

有限幾何是研究認證碼的有力工具.2014年，邱雙月[4]利用有限域上參數(shù)δ=0 的奇異酉空間構造了Cartesian 認證碼，但這種方法對于參數(shù)δ=1 的奇異酉空間計算較為復雜.2015年，邱雙月等[5]對此進行了改進，在參數(shù)δ=1 的奇異酉空間中構造了Cartesian 認證碼.此外，陳尚弟等[6]利用有限域上的酉幾何構造了具有可信仲裁的認證碼.代數(shù)組合方法是研究認證碼的重要方法.2010年，李殿龍[7]利用代數(shù)學中的立方冪零矩陣的若爾當標準型構造了Cartesian 認證碼，該方法在同等條件下能夠認證更多的信源，從而節(jié)省了通信成本，并且認證碼的安全性得到進一步提升.2009年，裴定一[8-9]在消息認證碼中詳細介紹了完善認證系統(tǒng)和組合設計之間的關系，并給出了最優(yōu)認證碼、完善認證碼的定義及實例.2015年，Safavi-Naini 等在文獻[10]中討論了敵方對接收方進行攻擊的最優(yōu)策略，給出了認證碼欺騙成功概率的下界，得到了最優(yōu)認證碼的組合特征.

在傳統(tǒng)的認證碼中，主要考慮模仿攻擊和替換攻擊成功的概率，但是在實際通信中，收發(fā)雙方一般是彼此不信任的[11]，Simmons[12]提出了認證碼的擴展-帶仲裁的認證碼，而分裂認證碼是研究帶仲裁的認證碼的一種重要手段.Simmons[12]首次提出分裂認證碼的定義，后來眾多學者嘗試利用各種方法構造性能優(yōu)良的分裂認證碼.Kurosawa 和王永傳等[13-14]給出了分裂認證碼和帶仲裁認證碼之間的對應關系.

組合設計作為一種重要的組合結構，在構造認證碼和分裂認證碼[15-16]中也被廣泛采用.其中用帶約束的部分平衡t-設計（restricted strongly partially balanced design, RSPBD）構造帶仲裁的認證碼，是由裴定一等[17]首次提出和運用的，而在利用分裂不平衡區(qū)組設計（splitting balanced incomplete block design,SBIBD）構造分裂認證碼方面，Huder 和Ogata等[15,18]都進行了開創(chuàng)性的研究并得到了重要的成果.2012年，Liang 等[19]利用可裂設計研究了三重完善分裂認證碼.近年來，關于分裂認證碼的新成果也很豐碩：2015年，Chen[20]利用射影空間中的特殊子空間及線和面的關聯(lián)關系，構造了分裂認證碼；Matsubara 等在文獻[21]中主要研究了可裂平衡區(qū)組設計（splitting block design, SBD）的可分解性，提供了具有可分辨性的SBD與其他組合設計的一些等價性，還提供了可解的SBD與其他組合設計的一些等價性.2017–2018年，Liang[22]、Li[23]和王利娜[24]繼續(xù)利用特殊的組合設計分別構造了幾類新的最優(yōu)分裂認證碼，但所用到的理論稍顯復雜，組合技巧不易掌握.

本文所構造的認證碼創(chuàng)新性主要體現(xiàn)在：基于有限域Fq上的二維向量空間，巧妙地借助線性方程組的理論，構造了帶約束的強部分平衡設計；相對于文獻[22-23]，本文所用理論簡單易懂，模擬仿真易于實現(xiàn)；本文是文獻[24]研究方法的繼續(xù)，研究結果同時也將文獻[8]中關于完善認證碼的構造推廣至完善c-分裂認證碼；通過舉例與文獻[15]的相關結果對比發(fā)現(xiàn)，在編碼規(guī)則數(shù)目相同的前提下，本文的信源數(shù)目大于文獻[15]的信源數(shù)目；本文所構造的認證碼的各階攻擊成功概率都達到了最小.

1 預備知識

本節(jié)給出認證碼的相關概念，組合設計和分裂認證碼的相關定義，兩者的關系以及所需結論.

1.1 分裂認證碼及Cartesian 認證碼的定義

定義1[11]對于一個認證碼(S,E,M,f)，若編碼規(guī)則e將信源s編碼成多個消息m，則稱之為分裂認證碼.

此時，對任意消息m ∈M，有m=e(s,r)，其中r ∈R，R是特殊的有限集合.對于?s ∈S,?e ∈E，定義

分裂是指對于某些信源s ∈S和編碼規(guī)則e ∈E，有|e(s)| >1.為了能夠順利譯碼，規(guī)定若則有

定義2[11]對于每一個信源s ∈S和每一個編碼規(guī)則e ∈E，如果|e(s)|=c，那么這個分裂認證碼就稱為c-分裂認證碼.

定義3[8]對于任意信源s ∈S，令M(s)={m ∈M|?e ∈E,e(s)=m}，M(s)是能代表s的所有報文的集合.如果對于任意兩個不同的信源s1和s2，M(s1)與M(s2)沒有公共元，那么這時認證碼(S,M,E)就稱為Cartesian 認證碼.

1.2 帶約束的部分平衡t-設計

定義4[20]設v,b,k,c,λ,t為正整數(shù)，tk.一個帶約束的部分平衡t-設計RPBDt ?(v,b,k×c;λ,0)是一個二元組(X,B), 其中X具有v個元素，B是區(qū)組集且滿足以下條件，

1）每個區(qū)組Bi ∈B(1i|B|=b)，都可以表示成長度為c的k個互不相交的子區(qū)組的并，即Bi=Bi,1∪Bi,2∪···∪Bi,k,其中|Bi,1|=|Bi,2|=···=|Bi,k|=c；

2）X中任意t子集{x1,x2,···,xt}，或在λ個區(qū)組Bi=Bi,1∪Bi,2∪···∪Bi,k中同時出現(xiàn)，且xm ∈Bi,jm(jm=1,2,···,k)，其中j1,j2,j3,···,jt互不相同，或它們不在任一區(qū)組中出現(xiàn).

定義5[20]一個帶約束的部分平衡t?(v,b,k×c;λ,0)設計，如果同時也是帶約束的部分平衡r ?(v,b,k×c;λr,0)設計，1rt ?1，則稱(X,B)為帶約束的強部分平衡t-設計（RSPBD），記為t ?(v,b,k×c;λ1,λ2,···,λt,0).

定理1[20]假設存在一個RSPBDt ?(v,b,k×c;λ1,λ2,···,λt?1,1,0)設計，其中t2，則對于k個等可能出現(xiàn)的信源，存在一個t-階完善c-分裂認證碼，具有v個信息和b個編碼規(guī)則的.相反，如果有一個具有k個信源，v個信息和b個編碼規(guī)則的t-階完善c-分裂認證碼，那么也就存在一個RSPBDt ?(v,b,k×c;λ1,λ2,···,λt?1,1,0)，其中λr=(PrPr+1···Pt?1)?1，1rt ?1.

Pr為r-階最佳欺騙攻擊成功的概率，r-欺騙攻擊是指敵方在觀察方使用相同的編碼規(guī)則，取M為認證碼的信息的集合，也是區(qū)組設計中樣本的集合.取信源S=Fq，在觀察到發(fā)方發(fā)送r(r0)個消息后，敵方在信道中放入不同于發(fā)方發(fā)送的r個虛假消息，試圖使收方接收，并認為它們是真實可靠的.

定義6[8]設Mi1,···,it={mt=(m1,m2,···,mt)|mr ∈M(sir),1rt}，在一個t-階完善Cartesian 碼中，假設存在信源集S的一個固定子集si1,···,sit，使任一mt ∈Mi1,···,it，其中Mi1,···,it={mt=(m1,m2,···,mt)|mr ∈M(sir),1rt}，都有|E(mt)|=1，那么稱這個認證碼是I 型完善認證碼，否則為II 型完善認證碼.

定義7[8]設t為正整數(shù)，當編碼規(guī)則的數(shù)目|E|達到下界(P0P1···Pt?1)?1，即|E|=(P0P1···Pt?1)?1，這個認證系統(tǒng)稱為t-階完善認證系統(tǒng).

對于認證碼的構造，主要考慮下述問題：1）Pr盡可能小，保證安全性；2）編碼規(guī)則盡可能少，減少傳輸過程中的存儲量；3）信源數(shù)目盡可能多，增大傳輸?shù)男畔⒘浚?）與普通認證碼相比，可裂認證碼需增加一定的變量，對消息進行合理的劃分，這樣有利于實現(xiàn)對高階攻擊的保護.而利用帶約束的強部分平衡t-設計構造分裂認證碼的關鍵問題是：樣本中任意t個元素恰好出現(xiàn)在所構造出來的區(qū)組中的λ個中，且這t個元素中的每一個又恰好分別出現(xiàn)在這λ個區(qū)組劃分出來的不同的t個子區(qū)組中.

2 在有限域Fq 上的二維向量空間中構造分裂認證碼

本節(jié)研究分裂認證碼的構造.根據(jù)1.2 節(jié)所述，一個完善認證系統(tǒng)與一個帶約束的強部分平衡t-設計有一一對應關系，也就是構造完善分裂認證碼等價于構造一個帶約束的強部分平衡t-設計.本文就是在有限域Fq上的二維向量空間中構造一個帶約束的強部分平衡t-設計，從而由這種設計構造兩個完善分裂認證碼.下面給出分裂認證碼的具體構造.

2.1 分裂認證碼的構造I

在Fq上的二維向量空間中，利用線性方程組的知識，將

作為編碼函數(shù)，常數(shù)變量λj用來實現(xiàn)可裂.

2.1.1 一種帶約束的強部分平衡t-設計的構造

設Fq為含有q個元素的有限域，t為正整數(shù)且t < q，取樣本集X為{(x,y)|x,y ∈Fq}.對Fq上的任意t元組(at?1,at?2,···,a0)，取定任一λj ∈ Fq，定義區(qū)組為其中u=1,2,···,q;j=1,2,···,c，且滿足c

記B為Fq上的任意t元組(at?1,at?2,···,a0)的集合，即為區(qū)組的集合，這樣的t元數(shù)組數(shù)目為qt，即|B|=qt.

每一個區(qū)組Bi可以表示為互不相同的長度為c的q個子區(qū)組的并Bi=Bi1∪Bi2∪···∪Biq，其中

對于每一個區(qū)組B(at?1,at?2,···,a0)，取Fq中t個互不相同的元素x1,x2,···,xt，對于M中任意t個點

它們滿足

方程組(5)看作以at?1,at?2,···,a0為未知數(shù)的線性方程組，其系數(shù)矩陣為

顯然，式(6)的行列式不為0.因此秩為t，故線性方程組(5)有唯一解，那么這t個點就被包含在由at?1,at?2,···,a0所定義的唯一區(qū)組里.根據(jù)Bi=Bi1∪Bi2∪···∪Biq的定義可知：(xu,yuj)恰好出現(xiàn)在Bi=Bi1∪Bi2∪···∪Biq的某個子區(qū)組Biu(=1,2,···,q)中.因此二元組(M,B)是一個RPBDt ?(q2,qt,q×c;1,0).

對于M中的任意s(1st ?1)個點，

如果它們在一個區(qū)組B(at?1,at?2,···,a0)中，則有以at?1,at?2,···,a0為變量的方程組

由于方程組(8)的系數(shù)矩陣中存在s階范德蒙德矩陣，所以秩是s，從而該方程組剛好有qt?s個解，這就意味著|λs|=qt?s.

因此二元組(M,B)是一個RSPBDt ?(q2,qt,q×c;λ1,λ2,···λt?1,1,0)，其中λs=qt?s(1st ?1).

2.1.2 分裂認證碼的構造

本節(jié)研究目標是利用2.1.1 節(jié)中所構造的帶約束的強部分平衡t-設計構造分裂認證碼.設認證碼的信源集合為S=Fq，消息集合M，編碼規(guī)則的集合E分別為上述設計中樣本的集合X和區(qū)組的集合B.對于每一個區(qū)組B(at?1,at?2,···,a0)和Fq中給定的λj ∈Fq ,可定義一個編碼規(guī)則e ∈E，使得

因此，編碼規(guī)則e的數(shù)目|E|取決于t元數(shù)組(a0,a1,···,at?1)的數(shù)目.這樣的t元組數(shù)目為qt，即|E|=qt.由2.1.1 節(jié)可知：對任意s個消息有效的密鑰數(shù)為|E(ms)|=λs=qt?s.

根據(jù)定理1，由2.1.1 節(jié)中所構造的

可以得到一類t-階完善c-分裂認證碼，其中信源數(shù)|S|=q，消息數(shù)|M|=q2，編碼規(guī)則數(shù)|E|=qt.假設編碼規(guī)則E和信源S具有一致分布，則有

通過消息(xu,yuj)就可以知道對應的信源xu，所以這個碼是一個Cartesian 認證碼.因此這個Cartesian 認證碼是t-階完善c-分裂認證碼.

如果s=t，那么方程組(8)存在唯一的解，由定義6 可得，該碼是I 型的完善認證碼.

2.2 分裂認證碼構造II

式中，u=1,2,···,q, j=1,2,···,c，滿足c

對于每一個區(qū)組(at?1,at?2,···,a0)，定義一個編碼規(guī)則，使得

即一個信源xu被加密成消息(xu,yuj)，j=1,2,···,c，編碼規(guī)則的數(shù)目即為Fq中t元組(at?1,at?2,···,a0), at?10的數(shù)目.這樣的t元組的數(shù)目為(q ?1)qt?1，所以編碼規(guī)則數(shù)目=(q ?1)qt?1.

對于區(qū)組(at?1,at?2,···,a0), at?10,在Fq中取t個互不相同的元素x1,x2,···,xt，對于M中任意t個點

適合下列方程組

在方程組(16)中，未知量為at?1,at?2,···,a0.設

有|E(ms)|=qt?1?s(q ?1).

故(M,B)是一個RSPBDt?(q2,(q ?1)qt?1,q×c;λ1,λ2,···,λt?1,1,0)，根據(jù)定理1，一

個新的t-階完善c-分裂Cartesian 認證碼可以被得到.

假定編碼規(guī)則E和信源Sr滿足等概率分布，可以得到

與構造I 類似，該碼也是一個t-階完善c-分裂Cartesian 認證碼.根據(jù)定義6，該認證碼是II 型的完善認證碼.

2.3 實例驗證和性能分析

在構造I 中，令q=3, c=2, t=2.由構造可知其中x ∈F3.λj分別取1 和2，信源S={s1,s2,s3}=F3.對應的設計為RSPBD 2-(9,9,3×2;3,3,10)，所構造的分裂認證碼的編碼矩陣如表1所示.

表1 分裂認證碼構造I 的編碼矩陣Table 1 Coding matrix of splitting authentication code I

值得說明的是，當λj分別取0,1 和0,2 時，又會得到其他兩種編碼矩陣.根據(jù)構造，對于固定的λj，由編碼矩陣也可看出，兩種攻擊成功概率都是.取λj=1，對編碼矩陣進行數(shù)值仿真，結果如圖1所示.

圖1 編碼矩陣仿真Figure 1 Coding matrix simulation

仿真分析：圖1以信源S作為橫坐標，編碼函數(shù)e(s)為縱坐標.任意選取消息（0,2），通過圖像可知，有三條線通過該點，即對消息（0,2）有效的編碼規(guī)則數(shù)目為3，總的線數(shù)即為編碼規(guī)則數(shù)目為9，從而模仿攻擊成功的概率為；任意選取兩個消息（0,2），（1,2），通過圖像可知，只有一條線通過這兩點，即對消息（0,2），（1,2）都有效的編碼規(guī)則數(shù)目為1，從而替換攻擊成功的概率為.通過仿真圖像所得的結論與構造方案結果一致，故本文的構造合理可行.

在構造I 的基礎上，要求a10可得到構造II，因此上例對應的構造II 的編碼矩陣如表2所示.

值得說明的是，當λj分別取0,1 和0,2 時，又會得到其他兩種編碼矩陣.根據(jù)構造，對于固定的λj，由編碼矩陣也可看出，兩種攻擊成功概率都是.取λj=1，對編碼矩陣進行數(shù)值仿真，結果如圖2所示.

表2 分裂認證碼構造II的編碼矩陣Table 2 Coding matrix of splitting authentication code II

圖2 編碼矩陣仿真Figure 2 Coding matrix simulation

仿真分析：圖2以信源S作為橫坐標，編碼函數(shù)e(s)為縱坐標，任意選取消息（0,2），通過圖像可知，有兩條線通過該點，即對消息（0,2）有效的編碼規(guī)則個數(shù)為2，此時編碼規(guī)則個數(shù)為6，從而模仿攻擊成功的概率為.任意選取兩個消息，通過圖像可知，只有一條直線通過這兩點，即對消息（0,2），（1,2）都有效的編碼規(guī)則個數(shù)為1，從而替換攻擊成功的概率為.通過仿真圖像所得的結論與構造方案結果一致，故本文的構造合理可行.

性能分析：

1）在上例中，將所構造的分裂認證碼的相關參數(shù)與文獻[15]中利用可裂設計構造的分裂認證碼進行比較可知，在編碼規(guī)則數(shù)目|E|=9 相同的前提下，本文的信源數(shù)目為3，大于文獻[15]的信源數(shù)目2.

2）本文以線性方程組的理論為基礎，構造了帶約束的強部分平衡設計，與文獻[15，21-23]相比，構造方法相對簡單易懂，編碼復雜度較低.

4）本文將文獻[8]中關于完善認證碼的構造推廣至完善c-分裂認證碼，即本文所構造的分裂認證碼滿足|E|=(P0P1···Pt?1)?1，達到了組合論中完善的界.

3 結 論

本文主要利用有限域上二維向量空間，借助線性方程組的理論，構造了帶約束的強部分平衡設計，在強部分平衡設計的基礎上構造了兩類t-階完善c-分裂認證碼.

優(yōu)點主要體現(xiàn)在三方面：1）用線性方程組求解等簡單的理論知識使編碼算法相對簡單，復雜度較??；2）在編碼規(guī)則數(shù)目相同的前提下，本文的信源數(shù)目大于文獻[5]的信源數(shù)目，有利于提高信息傳輸?shù)男剩?）認證碼的各階攻擊成功概率均達到了最小，且滿足完善性的條件，從信息安全性的角度來看，也是較好的.

不足主要體現(xiàn)在兩方面：1）在構造組合設計時樣本選擇的條件可以更嚴謹一些，在后續(xù)的研究中將繼續(xù)進行改進；2）Cartesian 認證碼對信源不具有保密性，用類似方法構造對信源具有保密功能的非Cartesian 認證碼，在后續(xù)的研究中將繼續(xù)進行探索.