一类新的2-阶完善分裂认证码

梁 淼

(苏州市职业大学 数理部，江苏 苏州 215104)

一类新的2-阶完善分裂认证码

梁 淼

(苏州市职业大学 数理部，江苏 苏州 215104)

带约束的强部分平衡t-设计是在研究带仲裁的认证码时首先提出的，利用带约束的强部分平衡t-设计可以给出t-阶完善分裂认证码的组合刻画，因此只需构造带约束的强部分平衡t-设计即可得到t-阶完善分裂认证码.通过研究区组长度为4×2的最优带约束的强部分平衡2-设计的存在性，得到一类区组长度为4×2的最优带约束的强部分平衡2-设计，从而得到一类新的4个信源的2-阶完善2-分裂认证码.

分裂认证码；带仲裁的认证码；带约束的强部分平衡t-设计

1 背景介绍

认证码由信源集合S、报文集合M 和编码规则集合E组成.一个编码规则e∈E，是S到2M中的一个映射.一个信源可对应多个报文.在通信之前，发方从E中秘密选出一个编码规则e通过安全信道传送给收方.当发方要向收方送一个信源s∈S时，先将s用e进行编码，得到报文m=e(s)，然后将该报文通过一个公共信道发送给收方.认证码称为分裂的，如果某一信源s∈S，在同一编码规则e∈E下，能用多个报文对其进行编码.此时，用m=e(s，l)来计算报文m∈M，其中l是某一特定有限集L中的随机数.对任一编码规则e∈E和任一信源s∈S，定义e(s)={m∈M∶存在l∈L使m=e(s，l)}，则认证码称为分裂的，即对某一编码规则e∈E和某一信源s∈S有|e(s)|>1.为了确保收方能够解密收到的报文，要求对任一编码规则e∈E，若s≠s'，有e(s)∩e(s')= .收方接受m为有效报文当且仅当.分裂认证码称为c-分裂的，如果对于任意e∈E和任意s∈S有|e(s)|=c.若敌方观察发方在同一编码规则下发出的r个不同的报文m1，m2，…，mr后，向收方发出不同于这r个报文的伪造报文m，称该攻击为r阶欺骗攻击.若收方接受该报文为有效报文且该报文用于传递不同于mi(1≤i≤r)所传递的信源，则敌方攻击成功.以Pr表示r阶欺骗攻击的成功概率.在文献[1]中发现，Pei Dingyi[2]中给出的认证码的r阶欺骗攻击的成功概率和编码规则个数的信息论下界，对于分裂认证码也成立.

定义Mr={mr=(m1，m2，…，mr):mi∈M，1≤i≤r}，分别以E和Mr表示编码规则和r个报文的随机变量，它们分别从E和Mr中取值.

引理1.1 在分裂认证码中，对任一整数r≥0，有Pr≥2(H(E│M(r+1))-H(E|Mr))[1].

引理1.2 在分裂认证码中，编码规则个数|E|≥(P0P1…Pt-1)-1[1].

定义1.3 编码规则个数|E|达到下界，即|E|=(P0P1…Pt-1)-1的分裂认证码称为t-阶完善分裂认证码.

定义1.4 设v，b，k，c，λ，t为正整数，t≤k，带约束的部分平衡t-设计RPBD t-(v，b，k×c；λ，0)是一个二元组(X，B)，其中X是v元集(称为点集)，B是X的大小为kc的子集的集合(称为区组集)，且满足下列条件:

1)每个区组B∈B都可以表示成k个长为c的互不相交的子区组的并，即B=B1∪B2∪…∪Bk；

2)X中任意t元点集{x1，x2，…，xt}或在λ个区组B=B1∪B2∪…∪Bk中同时出现，且x1∈Bi1，x2∈Bi2，…，xt∈Bit(i1，i2，…，it两两不同)或不在任一区组中出现.

本文中RPBD t-(v，b，k×c；λ，0)的区组记作，称|X|=v为带约束的部分平衡t-设计的阶.

定义1.5 一个带约束的部分平衡t-设计RPBD t-(v，b，k×c；λt，0)，如果同时也是带约束的部分平衡s-设计RPBD s-(v，b，k×c；λs，0)，0

易见，带约束的强部分平衡t-设计同时也是一个1-设计，即λ1=r，是包含某一固定点的区组的个数.

带约束的强部分平衡t-设计是由Pei Dingyi、Li Yuqiang、Wang Yejing等[3]在研究带仲裁的认证码时首先引入，Liang Miao、Li Mingchao和Du Beiliang[4]利用具有特殊性质的带约束的强部分平衡t-设计给出了几类t>2的t-阶完善带仲裁的认证码，2012年Liang Miao和Du Beiliang[5]证明了t-阶完善分裂认证码可由带约束的强部分平衡t-设计刻画.

定理1.6 假设存在RSPBD t-(v，b，k×c；λ1，λ2，…，λt-1，1，0)，t≥2，则存在k个信源、v个消息和b个编码规则的t-阶完善c-分裂认证码.反之，若存在k个信源、v个消息和b个编码规则的t-阶完善c-分裂认证码，则存在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 一个带约束的强部分平衡t-设计RSPBD t-(v，b，k×c；λ1，λ2，…，λt，0)称为最优的，若它的区组数b在所有带约束的强部分平衡t-设计RSPBD t-(v，b，k×c；λ1，λ2，…，λt，0)s中达到最大值(或者它的每个点出现次数rv在所有带约束的强部分平衡t-设计RSPBD t-(v，b，k×c；λ1，λ2，…，λt，0)s中达到最大值)，记为t-ORSPBD(v，b，k×c；λ1，λ2，…，λt，0).特别地，最优的带约束的强部分平衡2-设计简记为ORSPBD(v，k×c，λ).

很多学者已经研究了t-ORSPBD(v，b，k×c；λ1，λ2，…，λt，0)s(见文献[6]-[13]).文献[14]确定了当k×c=2×2、2×3 时，ORSPBD(v，k×c，1)的存在性.文献[13]、[15]给出了一类3-ORSPBD(v，b，3×2；λ1，λ2，1，0)，建立一类3个信源的3-阶完善2-分裂认证码.本文将研究ORSPBD(v，4×2，1)的构造方法和存在性并利用该设计建立新的4个信源的2-阶完善2-分裂认证码.

定理1.8 当v≡13 (mod 48)且v≥61时，存在ORSPBD(v，4×2，1).

由定理1.5得到定理1.9.

定理1.9 当v≡13 (mod 48)且v≥61时，存在4个信源、v个消息和个编码规则的2-阶完善2-分裂认证码，且

2 若干辅助设计

本节将定义一些辅助设计和基本结果，以供后面使用.

设v与λ为正整数，K与M为由某些正整数组成的集合，可分组设计GD[K，λ，M；v]是一个三元组(X，G，B )，其中:X为v元集(称为点集)；G为长度取自M的X的非空子集的集合(称为组集)；B为X的长度至少为2且长度取自K的子集的集合(称为区组集)，且满足下列3个条件:

1)G构成X的一个划分；

2)对任意B∈B与任意G∈G，都有|B∩G|≤1；

3)X中任意一对属于不同组的元素恰好包含在λ个区组中.

若G包含ti个大小为mi的组，1≤i≤s且，则称此可分组设计的型为.为方便起见，用GD[k，1，m；v]表示GD[{k}，1，{m}；v]，用记号K-GDD来表示GD[K，1，M；v].

关于可分组设计，有如下存在性结果.

引理2.1 存在型为gt的4-GDD当且仅当t≥4，g(t-1)≡0(mod 3)，g2t(t-1)≡0(mod 12)，且除了(g，t)∈{(2，4)，(6，4)}这两个例外[16].

设v，k，c 为正整数，M为由某些正整数组成的集合，分裂可分组设计SGD[k×c，1，M；v]是一个三元组(X，G，B)，其中:X为v元集(称为点集)；G为长度取自M的X的非空子集的集合(称为组集)；B为X的长度为kc的子集的集合(称为区组集)，且满足下列4个条件:

1)G构成X的一个划分；

2)任一区组B∈B，均可表示成k个长为c的互不相交的子区组的并，即B=B1∪B2∪…∪Bk；

3)对任意B∈B与任意G∈G，都有B∩G至多包含一个子区组；

4)任意取自不同组的点对{x，y}恰包含在唯一的一个区组B=B1∪B2∪…∪Bk中，且x∈Bi，y∈Bj(i≠j).

分裂可分组设计的型和可分组设计的型同样表示.用k×c-SGDD来表示SGD[k×c，1，M；v].

关于分裂可分组设计，建立如下结果.

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

证明 直接构作点集X=Z8，区组集B={{0，1；2，3；4，5；6，7}}.

引理2.3 如果存在下述设计:型为g1g2…gu的K-GDD，对每个k'∈K，存在型为hk'的k×c-SGDD，则存在型为(hg1)(hg2)…(hgu)的k×c-SGDD[1].

本文使用的主要技术为“填洞”构作.由于“填洞”构作通常涉及邻接s个无穷远点到分裂可分组设计上，需要带子设计的带约束的强部分平衡2-设计概念.特别地，记ORSPBD(v，w；k×c，1)为一个三元组(X，Y，B )，其中:X为v元集(称为点集)；Y X为w元集(称为洞)；B 为X的长度为kc的子集的集合(称为区组集)，且满足下列4个条件:

1)任一区组 B∈B，均可表示成k个长为c的互不相交的子区组的并，即B=B1∪B2∪…∪Bk；

2)对于XY中的每个点对{x，y}，或者恰包含在唯一的一个区组B=B1∪B2∪…∪Bk中，且x∈Bi，y∈Bj(i≠j)，或者不包含于任一区组B=B1∪B2∪…∪Bk中，且x∈Bi，y∈Bj(i≠j)；

3)对于Y中的每个点对{x，y}，不包含于任一区组B=B1∪B2∪…∪Bk中，且x∈Bi，y∈Bj(i≠j)；

4)X中每个点均恰包含在rv个区组中，其中rv是在所有RSPBD 2-(v，b，k×c；λ1，1，0)中包含某一固定点的最大区组数.

显然，它也是一个ORSPBD(v，k×c，1).

现在给出本文的主要构作“填洞”构作.

构作2.4 假设存在型为gt的4×2-SGDD，其中g≡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)出发，其中G={G1，G2，…，Gt}，|Gi|=g，1≤i≤t.对每个组Gi，1≤i≤t，在(Gi∪W，Ai)上构作ORSPBD(g+w，w；4×2，1)，其中|W|=w且X∩W=，在该设计中每个点出现，则所需构作设计的点集为X*=X∪W，区组集为，易验证是 ORSPBD(gt+w，4×2，1)，每个点出现的次数为.

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

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

证明 直接构作所需设计如下:

点集X=Z48∪{∞1，∞2，…，∞13}，区组集B分为两部分(共61个).

第一部分由下列初始区组在+6 mod 48的作用下循环生成:{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}.

第二部分由下面区组组成:{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).

证明 直接构作ORSPBD(109；4×2，1)为点集X=Z109； 区组集B由下列初始区组在+1 mod 109 的作用下循环生成:{0，3；1，6；10，14；26，44}，{0，68；5，15；33，36；85，87}.

直接构作ORSPBD(157；4×2，1)为点集X=Z157； 区组集B由下列初始区组在+1 mod 157 的作用下循环生成: {0，32；1，71；73，75；78，88}，{0，14；6，23；48，50；68，147}，{0，78；12，29；64，110；129，131}.

下面将证明本文的主要结论，即定理1.8.

证明 对于v≤157，由引理3.1、3.2可知存在ORSPBD(v，4×2，1).对于剩下的其他v值，由引理2.1知存在型为24t的4-GDD，t≥4，对该设计每个点加权2，应用引理2.3在每个区组上输入型为24的4×2-SGDD(该设计的存在性见引理2.2)，可得型为48t的4×2-SGDD，t≥4.又由引理3.1知存在ORSPBD(61，13；4×2，1).运用构作2.4 即得所需结论.

[1] 梁淼. 认证码的组合构造[D]. 苏州:苏州大学，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.

(责任编辑:沈凤英)

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

国家自然科学基金资助项目（11301370）；苏州市职业大学青年基金资助项目（2012SZDQ30）

梁 淼（1981-），女，江苏昆山人，副教授，博士，主要从事组合设计与密码研究.