一類新的2-階完善分裂認(rèn)證碼

梁 淼

(蘇州市職業(yè)大學(xué) 數(shù)理部，江蘇 蘇州 215104)

一類新的2-階完善分裂認(rèn)證碼

梁 淼

(蘇州市職業(yè)大學(xué) 數(shù)理部，江蘇 蘇州 215104)

帶約束的強(qiáng)部分平衡t-設(shè)計(jì)是在研究帶仲裁的認(rèn)證碼時(shí)首先提出的，利用帶約束的強(qiáng)部分平衡t-設(shè)計(jì)可以給出t-階完善分裂認(rèn)證碼的組合刻畫，因此只需構(gòu)造帶約束的強(qiáng)部分平衡t-設(shè)計(jì)即可得到t-階完善分裂認(rèn)證碼.通過研究區(qū)組長(zhǎng)度為4×2的最優(yōu)帶約束的強(qiáng)部分平衡2-設(shè)計(jì)的存在性，得到一類區(qū)組長(zhǎng)度為4×2的最優(yōu)帶約束的強(qiáng)部分平衡2-設(shè)計(jì)，從而得到一類新的4個(gè)信源的2-階完善2-分裂認(rèn)證碼.

分裂認(rèn)證碼；帶仲裁的認(rèn)證碼；帶約束的強(qiáng)部分平衡t-設(shè)計(jì)

1 背景介紹

認(rèn)證碼由信源集合S、報(bào)文集合M 和編碼規(guī)則集合E組成.一個(gè)編碼規(guī)則e∈E，是S到2M中的一個(gè)映射.一個(gè)信源可對(duì)應(yīng)多個(gè)報(bào)文.在通信之前，發(fā)方從E中秘密選出一個(gè)編碼規(guī)則e通過安全信道傳送給收方.當(dāng)發(fā)方要向收方送一個(gè)信源s∈S時(shí)，先將s用e進(jìn)行編碼，得到報(bào)文m=e(s)，然后將該報(bào)文通過一個(gè)公共信道發(fā)送給收方.認(rèn)證碼稱為分裂的，如果某一信源s∈S，在同一編碼規(guī)則e∈E下，能用多個(gè)報(bào)文對(duì)其進(jìn)行編碼.此時(shí)，用m=e(s，l)來計(jì)算報(bào)文m∈M，其中l(wèi)是某一特定有限集L中的隨機(jī)數(shù).對(duì)任一編碼規(guī)則e∈E和任一信源s∈S，定義e(s)={m∈M∶存在l∈L使m=e(s，l)}，則認(rèn)證碼稱為分裂的，即對(duì)某一編碼規(guī)則e∈E和某一信源s∈S有|e(s)|>1.為了確保收方能夠解密收到的報(bào)文，要求對(duì)任一編碼規(guī)則e∈E，若s≠s'，有e(s)∩e(s')= .收方接受m為有效報(bào)文當(dāng)且僅當(dāng).分裂認(rèn)證碼稱為c-分裂的，如果對(duì)于任意e∈E和任意s∈S有|e(s)|=c.若敵方觀察發(fā)方在同一編碼規(guī)則下發(fā)出的r個(gè)不同的報(bào)文m1，m2，…，mr后，向收方發(fā)出不同于這r個(gè)報(bào)文的偽造報(bào)文m，稱該攻擊為r階欺騙攻擊.若收方接受該報(bào)文為有效報(bào)文且該報(bào)文用于傳遞不同于mi(1≤i≤r)所傳遞的信源，則敵方攻擊成功.以Pr表示r階欺騙攻擊的成功概率.在文獻(xiàn)[1]中發(fā)現(xiàn)，Pei Dingyi[2]中給出的認(rèn)證碼的r階欺騙攻擊的成功概率和編碼規(guī)則個(gè)數(shù)的信息論下界，對(duì)于分裂認(rèn)證碼也成立.

定義Mr={mr=(m1，m2，…，mr):mi∈M，1≤i≤r}，分別以E和Mr表示編碼規(guī)則和r個(gè)報(bào)文的隨機(jī)變量，它們分別從E和Mr中取值.

引理1.1 在分裂認(rèn)證碼中，對(duì)任一整數(shù)r≥0，有Pr≥2(H(E│M(r+1))-H(E|Mr))[1].

引理1.2 在分裂認(rèn)證碼中，編碼規(guī)則個(gè)數(shù)|E|≥(P0P1…Pt-1)-1[1].

定義1.3 編碼規(guī)則個(gè)數(shù)|E|達(dá)到下界，即|E|=(P0P1…Pt-1)-1的分裂認(rèn)證碼稱為t-階完善分裂認(rèn)證碼.

定義1.4 設(shè)v，b，k，c，λ，t為正整數(shù)，t≤k，帶約束的部分平衡t-設(shè)計(jì)RPBD t-(v，b，k×c；λ，0)是一個(gè)二元組(X，B)，其中X是v元集(稱為點(diǎn)集)，B是X的大小為kc的子集的集合(稱為區(qū)組集)，且滿足下列條件:

1)每個(gè)區(qū)組B∈B都可以表示成k個(gè)長(zhǎng)為c的互不相交的子區(qū)組的并，即B=B1∪B2∪…∪Bk；

2)X中任意t元點(diǎn)集{x1，x2，…，xt}或在λ個(gè)區(qū)組B=B1∪B2∪…∪Bk中同時(shí)出現(xiàn)，且x1∈Bi1，x2∈Bi2，…，xt∈Bit(i1，i2，…，it兩兩不同)或不在任一區(qū)組中出現(xiàn).

本文中RPBD t-(v，b，k×c；λ，0)的區(qū)組記作，稱|X|=v為帶約束的部分平衡t-設(shè)計(jì)的階.

定義1.5 一個(gè)帶約束的部分平衡t-設(shè)計(jì)RPBD t-(v，b，k×c；λt，0)，如果同時(shí)也是帶約束的部分平衡s-設(shè)計(jì)RPBD s-(v，b，k×c；λs，0)，0

易見，帶約束的強(qiáng)部分平衡t-設(shè)計(jì)同時(shí)也是一個(gè)1-設(shè)計(jì)，即λ1=r，是包含某一固定點(diǎn)的區(qū)組的個(gè)數(shù).

帶約束的強(qiáng)部分平衡t-設(shè)計(jì)是由Pei Dingyi、Li Yuqiang、Wang Yejing等[3]在研究帶仲裁的認(rèn)證碼時(shí)首先引入，Liang Miao、Li Mingchao和Du Beiliang[4]利用具有特殊性質(zhì)的帶約束的強(qiáng)部分平衡t-設(shè)計(jì)給出了幾類t>2的t-階完善帶仲裁的認(rèn)證碼，2012年Liang Miao和Du Beiliang[5]證明了t-階完善分裂認(rèn)證碼可由帶約束的強(qiáng)部分平衡t-設(shè)計(jì)刻畫.

定理1.6 假設(shè)存在RSPBD t-(v，b，k×c；λ1，λ2，…，λt-1，1，0)，t≥2，則存在k個(gè)信源、v個(gè)消息和b個(gè)編碼規(guī)則的t-階完善c-分裂認(rèn)證碼.反之，若存在k個(gè)信源、v個(gè)消息和b個(gè)編碼規(guī)則的t-階完善c-分裂認(rèn)證碼，則存在RSPBD t-(v，b，k×c；λ1，λ2，…，λt-1，1，0)，其中λr=(PrPr+1…Pt-1)-1，1≤r≤t-1[5].

定義1.7 一個(gè)帶約束的強(qiáng)部分平衡t-設(shè)計(jì)RSPBD t-(v，b，k×c；λ1，λ2，…，λt，0)稱為最優(yōu)的，若它的區(qū)組數(shù)b在所有帶約束的強(qiáng)部分平衡t-設(shè)計(jì)RSPBD t-(v，b，k×c；λ1，λ2，…，λt，0)s中達(dá)到最大值(或者它的每個(gè)點(diǎn)出現(xiàn)次數(shù)rv在所有帶約束的強(qiáng)部分平衡t-設(shè)計(jì)RSPBD t-(v，b，k×c；λ1，λ2，…，λt，0)s中達(dá)到最大值)，記為t-ORSPBD(v，b，k×c；λ1，λ2，…，λt，0).特別地，最優(yōu)的帶約束的強(qiáng)部分平衡2-設(shè)計(jì)簡(jiǎn)記為ORSPBD(v，k×c，λ).

很多學(xué)者已經(jīng)研究了t-ORSPBD(v，b，k×c；λ1，λ2，…，λt，0)s(見文獻(xiàn)[6]-[13]).文獻(xiàn)[14]確定了當(dāng)k×c=2×2、2×3 時(shí)，ORSPBD(v，k×c，1)的存在性.文獻(xiàn)[13]、[15]給出了一類3-ORSPBD(v，b，3×2；λ1，λ2，1，0)，建立一類3個(gè)信源的3-階完善2-分裂認(rèn)證碼.本文將研究ORSPBD(v，4×2，1)的構(gòu)造方法和存在性并利用該設(shè)計(jì)建立新的4個(gè)信源的2-階完善2-分裂認(rèn)證碼.

定理1.8 當(dāng)v≡13 (mod 48)且v≥61時(shí)，存在ORSPBD(v，4×2，1).

由定理1.5得到定理1.9.

定理1.9 當(dāng)v≡13 (mod 48)且v≥61時(shí)，存在4個(gè)信源、v個(gè)消息和個(gè)編碼規(guī)則的2-階完善2-分裂認(rèn)證碼，且

2 若干輔助設(shè)計(jì)

本節(jié)將定義一些輔助設(shè)計(jì)和基本結(jié)果，以供后面使用.

設(shè)v與λ為正整數(shù)，K與M為由某些正整數(shù)組成的集合，可分組設(shè)計(jì)GD[K，λ，M；v]是一個(gè)三元組(X，G，B )，其中:X為v元集(稱為點(diǎn)集)；G為長(zhǎng)度取自M的X的非空子集的集合(稱為組集)；B為X的長(zhǎng)度至少為2且長(zhǎng)度取自K的子集的集合(稱為區(qū)組集)，且滿足下列3個(gè)條件:

1)G構(gòu)成X的一個(gè)劃分；

2)對(duì)任意B∈B與任意G∈G，都有|B∩G|≤1；

3)X中任意一對(duì)屬于不同組的元素恰好包含在λ個(gè)區(qū)組中.

若G包含ti個(gè)大小為mi的組，1≤i≤s且，則稱此可分組設(shè)計(jì)的型為.為方便起見，用GD[k，1，m；v]表示GD[{k}，1，{m}；v]，用記號(hào)K-GDD來表示GD[K，1，M；v].

關(guān)于可分組設(shè)計(jì)，有如下存在性結(jié)果.

引理2.1 存在型為gt的4-GDD當(dāng)且僅當(dāng)t≥4，g(t-1)≡0(mod 3)，g2t(t-1)≡0(mod 12)，且除了(g，t)∈{(2，4)，(6，4)}這兩個(gè)例外[16].

設(shè)v，k，c 為正整數(shù)，M為由某些正整數(shù)組成的集合，分裂可分組設(shè)計(jì)SGD[k×c，1，M；v]是一個(gè)三元組(X，G，B)，其中:X為v元集(稱為點(diǎn)集)；G為長(zhǎng)度取自M的X的非空子集的集合(稱為組集)；B為X的長(zhǎng)度為kc的子集的集合(稱為區(qū)組集)，且滿足下列4個(gè)條件:

1)G構(gòu)成X的一個(gè)劃分；

2)任一區(qū)組B∈B，均可表示成k個(gè)長(zhǎng)為c的互不相交的子區(qū)組的并，即B=B1∪B2∪…∪Bk；

3)對(duì)任意B∈B與任意G∈G，都有B∩G至多包含一個(gè)子區(qū)組；

4)任意取自不同組的點(diǎn)對(duì){x，y}恰包含在唯一的一個(gè)區(qū)組B=B1∪B2∪…∪Bk中，且x∈Bi，y∈Bj(i≠j).

分裂可分組設(shè)計(jì)的型和可分組設(shè)計(jì)的型同樣表示.用k×c-SGDD來表示SGD[k×c，1，M；v].

關(guān)于分裂可分組設(shè)計(jì)，建立如下結(jié)果.

引理2.2 存在型為24的4×2-SGDD.

證明 直接構(gòu)作點(diǎn)集X=Z8，區(qū)組集B={{0，1；2，3；4，5；6，7}}.

引理2.3 如果存在下述設(shè)計(jì):型為g1g2…gu的K-GDD，對(duì)每個(gè)k'∈K，存在型為hk'的k×c-SGDD，則存在型為(hg1)(hg2)…(hgu)的k×c-SGDD[1].

本文使用的主要技術(shù)為“填洞”構(gòu)作.由于“填洞”構(gòu)作通常涉及鄰接s個(gè)無窮遠(yuǎn)點(diǎn)到分裂可分組設(shè)計(jì)上，需要帶子設(shè)計(jì)的帶約束的強(qiáng)部分平衡2-設(shè)計(jì)概念.特別地，記ORSPBD(v，w；k×c，1)為一個(gè)三元組(X，Y，B )，其中:X為v元集(稱為點(diǎn)集)；Y X為w元集(稱為洞)；B 為X的長(zhǎng)度為kc的子集的集合(稱為區(qū)組集)，且滿足下列4個(gè)條件:

1)任一區(qū)組 B∈B，均可表示成k個(gè)長(zhǎng)為c的互不相交的子區(qū)組的并，即B=B1∪B2∪…∪Bk；

2)對(duì)于XY中的每個(gè)點(diǎn)對(duì){x，y}，或者恰包含在唯一的一個(gè)區(qū)組B=B1∪B2∪…∪Bk中，且x∈Bi，y∈Bj(i≠j)，或者不包含于任一區(qū)組B=B1∪B2∪…∪Bk中，且x∈Bi，y∈Bj(i≠j)；

3)對(duì)于Y中的每個(gè)點(diǎn)對(duì){x，y}，不包含于任一區(qū)組B=B1∪B2∪…∪Bk中，且x∈Bi，y∈Bj(i≠j)；

4)X中每個(gè)點(diǎn)均恰包含在rv個(gè)區(qū)組中，其中rv是在所有RSPBD 2-(v，b，k×c；λ1，1，0)中包含某一固定點(diǎn)的最大區(qū)組數(shù).

顯然，它也是一個(gè)ORSPBD(v，k×c，1).

現(xiàn)在給出本文的主要構(gòu)作“填洞”構(gòu)作.

構(gòu)作2.4 假設(shè)存在型為gt的4×2-SGDD，其中g(shù)≡0(mod 48)，存在ORSPBD(g+w，w；4×2，1)，其中1≤w≤48且w≡1(mod 2)，則存在ORSPBD(gt+w，4×2，1).

證明 從型為gt的4×2-SGDD(X，G，B)出發(fā)，其中G={G1，G2，…，Gt}，|Gi|=g，1≤i≤t.對(duì)每個(gè)組Gi，1≤i≤t，在(Gi∪W，Ai)上構(gòu)作ORSPBD(g+w，w；4×2，1)，其中|W|=w且X∩W=，在該設(shè)計(jì)中每個(gè)點(diǎn)出現(xiàn)，則所需構(gòu)作設(shè)計(jì)的點(diǎn)集為X*=X∪W，區(qū)組集為，易驗(yàn)證是 ORSPBD(gt+w，4×2，1)，每個(gè)點(diǎn)出現(xiàn)的次數(shù)為.

3 ORSPBD(v，4×2，1)s的存在性

引理3.1 存在ORSPBD(61，13；4×2，1).

證明 直接構(gòu)作所需設(shè)計(jì)如下:

點(diǎn)集X=Z48∪{∞1，∞2，…，∞13}，區(qū)組集B分為兩部分(共61個(gè)).

第一部分由下列初始區(qū)組在+6 mod 48的作用下循環(huán)生成:{0，2；1，3；4，5；∞1，∞2}，{0，7；2，9；16，17；∞3，∞4}，{0，3；7，8；28，29；∞5，∞6}，{0，2；10，11；13，15； ∞7，∞8}，{0，1；14，21；40，41；∞9，∞10}，{0，3；19，34；35，44；∞11，∞12}，{0，9；22，23；38，43；26，∞13}.

第二部分由下面區(qū)組組成:{0，12；6，18；24，30；36，42}，{1，13；7，19；25，31；37，43}，{4，5；10，11；16，17；22，23}，{28，29；34，35；40，41；46，47}，{3，15；9，21；27，33；39，45}.

引理3.2 存在ORSPBD(109；4×2，1)和ORSPBD(157；4×2，1).

證明 直接構(gòu)作ORSPBD(109；4×2，1)為點(diǎn)集X=Z109； 區(qū)組集B由下列初始區(qū)組在+1 mod 109 的作用下循環(huán)生成:{0，3；1，6；10，14；26，44}，{0，68；5，15；33，36；85，87}.

直接構(gòu)作ORSPBD(157；4×2，1)為點(diǎn)集X=Z157； 區(qū)組集B由下列初始區(qū)組在+1 mod 157 的作用下循環(huán)生成: {0，32；1，71；73，75；78，88}，{0，14；6，23；48，50；68，147}，{0，78；12，29；64，110；129，131}.

下面將證明本文的主要結(jié)論，即定理1.8.

證明 對(duì)于v≤157，由引理3.1、3.2可知存在ORSPBD(v，4×2，1).對(duì)于剩下的其他v值，由引理2.1知存在型為24t的4-GDD，t≥4，對(duì)該設(shè)計(jì)每個(gè)點(diǎn)加權(quán)2，應(yīng)用引理2.3在每個(gè)區(qū)組上輸入型為24的4×2-SGDD(該設(shè)計(jì)的存在性見引理2.2)，可得型為48t的4×2-SGDD，t≥4.又由引理3.1知存在ORSPBD(61，13；4×2，1).運(yùn)用構(gòu)作2.4 即得所需結(jié)論.

[1] 梁淼. 認(rèn)證碼的組合構(gòu)造[D]. 蘇州:蘇州大學(xué)，2012.

[2] Pei Dingyi.Information-theoretic bounds for authentication codes and block designs[J]. J.Cryptology，1995，8(4):177-188.

[3] Pei Dingyi，Li Yuqiang，Wang Yejing，et al. Characterization of optimal authentication codes with arbitration[C]//Lecture Notes in ComputerScience.Berlin-Heidelberg-New York:Springer-Verlag，1999，1587:303-313.

[4] Liang Miao，Li Mingchao，Du Beiliang. A construction for t-fold perfect authentication codes with arbitration[J]. Des.Codes Cryptogr，2014，73(3):781-790.

[5] Liang Miao，Du Beiliang.A new class of 3-fold perfect splitting authentication codes[J]. Des.Codes Cryptogr，2012，62(1):109-119.

[6] Ogata W，Kurosawa K，Stinson D R，et al.New combinatorial designs and their applications to authentication codes and secret sharing schemes[J]. Discrete Math，2004，279(1/2/3):383-405.

[7] Du Beiliang.Splitting balanced incomplete block designs with block size 3×2[J]. J.Combin.Designs，2004，12(6):404-420.

[8] Du BBeiliang.Splitting balanced incomplete block designs[J].Australas.J.Combin，2005，31:287-298.

[9] Liang Miao，Du Beiliang. Splitting balanced incomplete block designs with block size 2×4[J].J.Combin.Math.Combin.Computing，2007，63:159-172.

[10] Ge G，Miao Ying，Wang Lihua.Combinatorial constructions for optimal splitting authentication codes[J].SIAM J.Discrete Math，2005，18(4): 663-678.

[11] Wang Jinhua.A new class of optimal 3-splitting authentication codes[J].Des.Codes Cryptogr，2006，38(3):373-381.

[12] Wang Jinhua，Su Renwang.Further results on the existence of splitting BIBDs and application to authentication codes[J].Acta Appl.Math，2010，109(3):791-803.

[13] Chee Y M，Zhang Xiande，Zhang Hui.Infinite families of optimal splitting authentication codes secure against spoofing attacks of higher order[J].Adv.Math.Commun，2011，5(1):59-68.

[14] Liang Miao，Du Beiliang. Existence of optimal restricted strong partially balanced designs[J]. Utilitas Math，2012，89:15-31.

[15] Liang Miao，Du Beiliang.A new class of splitting 3-designs[J].Des.Codes Cryptogr，2011，60(3):283-290.

[16] Browwer A，Schrijver A，Hanani H.Group divisible designs with block size 4[J].Discrete Math，1977，20(1):1-10.

(責(zé)任編輯:沈鳳英)

A New Class of 2-Fold Perfect Splitting Authentication Codes

LIANG Miao
(Department of Mathematics and Physics，Suzhou Vocational University，Suzhou 215104，China)

Restricted strong partially balanced t-designs were first formulated the in investigation of authentication codes with arbitration.It has been proved that t-fold perfect splitting authentication codes can be characterized in terms of restricted strong partially balanced t-designs.Then restricted strong partially balanced t-designs can be used to construct t-fold perfect splitting authentication codes.We investigate the existence of optimal restricted strong partially balanced 2-design with block size 4×2，and our investigation shows that there exists an infnite class of optimal restricted strong partially balanced 2-design with block size 4×2.As its application，we obtain a new infnite class of 2-fold perfect splitting authentication codes with four source states.

splitting authentication codes；authentication codes with arbitration；restricted strong partially balanced t-designs

O157.2

A

1008-5475(2014)04-0002-05

2014-08-05；

2014-08-25

國(guó)家自然科學(xué)基金資助項(xiàng)目（11301370）；蘇州市職業(yè)大學(xué)青年基金資助項(xiàng)目（2012SZDQ30）

梁 淼（1981-），女，江蘇昆山人，副教授，博士，主要從事組合設(shè)計(jì)與密碼研究.