楊名慧, 文潔晶, 馮克勤

(1. 中國科學(xué)院 信息工程研究所, 北京 100193; 2. 南開大學(xué) 陳省身數(shù)學(xué)研究所, 天津 300071; 3. 清華大學(xué) 數(shù)學(xué)科學(xué)系, 北京 100084)

外差組及其通信應(yīng)用

楊名慧1, 文潔晶2, 馮克勤3*

(1. 中國科學(xué)院 信息工程研究所, 北京 100193; 2. 南開大學(xué) 陳省身數(shù)學(xué)研究所, 天津 300071; 3. 清華大學(xué) 數(shù)學(xué)科學(xué)系, 北京 100084)

組合設(shè)計(jì)在通信中有著廣泛的應(yīng)用.綜述近年來基于同步通信，防欺騙數(shù)字簽名和認(rèn)證、密秘共享等方面應(yīng)用背景而提出的一些新型組合設(shè)計(jì)：外差組以及它的各種推廣和變種.解釋這些組合設(shè)計(jì)和通信應(yīng)用的聯(lián)系，介紹它們的構(gòu)作方法和存在性方面的已知結(jié)果,以及未解決的問題.

差集合; 無逗號碼; AMD碼; 認(rèn)證碼; 分圓類; 分圓數(shù)

和組合數(shù)學(xué)許多分支一樣,組合設(shè)計(jì)起源于一些游戲(歐拉36軍官問題、晚宴請客……).由于工業(yè)產(chǎn)品制作和質(zhì)量控制等方面的實(shí)驗(yàn)需要,組合設(shè)計(jì)從20世紀(jì)50年代開始發(fā)展.數(shù)字通信技術(shù)的進(jìn)步促使組合設(shè)計(jì)在信息理論和工程方面有許多應(yīng)用和密切聯(lián)系.本文綜述近年來由同步通信、秘密共享、數(shù)字簽名和認(rèn)證等方面的新問題所提出來的一種新型組合結(jié)構(gòu)——外差組(EDF)及其各種推廣(強(qiáng)外差組、廣義強(qiáng)外差組).關(guān)于組合設(shè)計(jì)的基本知識可參見文獻(xiàn)[1].

1 外差組及其推廣

定義 1.1 設(shè)(G,+)是n階交換(加法)群,D為G的一個(gè)k元子集合,D叫作是G中一個(gè)(n,k,λ)-差集合(DS),是指對G中每個(gè)非零元素g,方程g=x-y在D中恰好有λ組解(x,y)(x,y∈D).如果記如下的“多重”集合

Δ(D,D)={x-y:x,y∈D},

則x-y=0在D中恰好有|D|=k個(gè):(x,y)=(a,a),a∈D,從而D為(n,k,λ)-差集合也可以表示成

Δ(D,D)=k{0}+λ(G-{0})，

(1)

這里,等式兩邊均表示為群環(huán)Z[G]中的元素.Z[G]中元素唯一表示成

其中

Z[G]對于上述運(yùn)算為交換環(huán).

例 1.1G=(Z7,+),則D={1,2,4}是G的(n,k,λ)=(7,3,1)-差集合.事實(shí)上,Δ(D,D)={1-1,1-2,1-4,2-1,2-2,2-4,4-1,4-2,4-4}=3·{0}+(Z7-{0}).

差集合的參數(shù)滿足k(k-1)=λ(n-1).特別地,(n-1)/k(k-1)為正整數(shù).當(dāng)它不是正整數(shù)時(shí),人們放寬一些條件,給出差集合的一些變種.下面是本文要用到的一個(gè)變種.

定義 1.2 設(shè)G為n階交換群,D為G的k元子集合,并且0?D.稱D為G的(n,k,λ,μ)-部分差集合(PDS),是指

Δ(D,D)=k·{0}+λD+μ(G-D-{0}).

(2)

也就是說,D中每個(gè)元素在Δ(D,D)中均恰好出現(xiàn)λ次,G中其它非零元素在Δ(D,D)中均恰好出現(xiàn)μ次.由(2)式知參數(shù)滿足條件k(k-1)=λk+μ(n-k-1).

例 1.2G=(Z13,+),D={1,3,4,9,10,12}.可驗(yàn)證D為G的(13,6,2,3)-PDS.

另一種推廣是把一個(gè)集合D改用m個(gè)集合A1,A2,…,Am構(gòu)成的集組.

定義 1.3G為n階交換群,m≥2,A1,A2,…,Am為G的子集合,|Ai|=ki≥2(1≤i≤m),稱{A1,A2,…,Am}為G的(n,m;k1,k2,…,km;λ)-差集組(DF),是指

λ(G-{0}).

(3)

(注意群環(huán)中的元素Δ1+Δ2指并集Δ1∪Δ2).由(3)式給出

定義1.3中是每個(gè)Ai做Δ(Ai,Ai)然后將它們合并.本文要介紹的是另一種組合設(shè)計(jì),即不同Ai和Aj(i≠j)之間的元素相減.

Δ(Ai,Aj)={x-y:x∈Ai,y∈Aj},

然后把它們合并.

定義 1.4G為n階交換群,m≥2,A1,A2,…,Am為G的子集合,|Ai|=ki≥1(1≤i≤m),{A1,A2,…,Am}叫作G的一個(gè)(n,m;k1,k2,…,km;λ)-外差組(EDF),是指

(4)

由此式可知,A1,A2,…,Am必然兩兩不相交(因?yàn)?不屬于上式左邊),并且

λ(n-1).

如果k1=k2=…=km=k,則{A1,A2,…,Am}稱為正則的(n,m;k,λ)-EDF,這時(shí)(m2-m)k2=λ(n-1).

下面是比外差組更強(qiáng)的組合設(shè)計(jì).

定義 1.5 (G,+)為n階交換群,m≥2,A1,A2,…,Am為G的子集合,|Ai|=ki≥1(1≤i≤m).{A1,A2,…,Am}叫作是G的一個(gè)(n,m;k1,k2,…,km;λ1,λ2,…,λm)-廣義強(qiáng)外差組(GSEDF),是指對每個(gè)i(1≤i≤m)

(5)

對于這種設(shè)計(jì),A1,A2,…,Am必然兩兩不相交,并且對每個(gè)i(1≤i≤m)

ki(k-ki)=λi(n-1),k=k1+k2+…+km.

進(jìn)而由定義可知,如果{A1,A2,…,Am}是G的(n,m;k1,k2,…,km;λ1,λ2,…,λm)-GSEDF,則

從而{A1,A2,…,Am}也是G的(n,m;k1,k2,…,km;λ1+λ2+…+λm)-EDF.

如果k1=k2=…=km=k,則λ1=λ2=…=λm=λ,這時(shí)稱{A1,A2,…,Am}為G的一個(gè)(n,m;k,λ)-強(qiáng)外差組(SEDF).這時(shí)(m-1)k2=λ(n-1).

例 1.3 設(shè)G={g1,g2,…,gn},則{g1},{g2},…,{gn}為G的(n,n;1,1)-SEDF,這稱為G的平凡SEDF,以下只對非平凡SEDF有興趣.

例 1.4G=(Zn,+),n=ab+1.令A(yù)1={0,1,…,a-1},A2={a,2a,…,ba}.易證{A1,A2}為G的(n=ab+1,2;k1=a,k2=b;λ1=1,λ2=1)-GSEDF.

(注意對于m=2情形,{A1,A2}為G的(n,2;k1,k2;λ1,λ2)-GSEDF,必然λ1=λ2=λ,并且Δ(A1,A2)=Δ(A2,A1)=λ(G-{0})).這時(shí)k1k2=λ(n-1),特別地,當(dāng)a=b時(shí),即G=(Zn,+),n=a2+1,則A1={0,1,…,a-1}和A2={a,2a,…,a2}為G的(n=a2+1,2;a,1)-SEDF.

例 1.5G=(Z7,+),A1={1},A2={2},A3={4},A4={0,3,5,6},則{A1,A2,A3,A4}為G的(7,4;1,1,1,4;1,1,1,2)-GSEDF.

此外還有更廣的組合設(shè)計(jì),如有界廣義強(qiáng)外差組(BoundGSEDF)等,為了節(jié)省篇幅,這里從略.

2 外差組(EDF)的通信應(yīng)用

外差組最早由V.I.Levenshtein[2]于1971年提出,不過在文獻(xiàn)[2](以及其后不少文獻(xiàn))中采用名稱為DSS,其背景是為解決同步通信問題用來構(gòu)作最優(yōu)的無逗點(diǎn)碼.后來又發(fā)現(xiàn)EDF及其推廣GEDF可用于認(rèn)證碼和秘密分享[3],其中一類特殊的防欺騙認(rèn)證碼,叫作AMD碼,是由R.Cramer等[4-5]提出.外差族(EDF)、強(qiáng)外差組(SEDF),及其推廣GSEDF可用來構(gòu)作最優(yōu)的AMD碼.關(guān)于這些組合設(shè)計(jì)和AMD碼之間的聯(lián)系在文獻(xiàn)[6]中有系統(tǒng)闡述.

這里簡要地介紹EDF和SEDF及其推廣的組合設(shè)計(jì)和CF碼以及AMD碼之間的聯(lián)系.

2.1 EDF和CF碼[7] 設(shè)G是一個(gè)q元集合,q≥2,n≥1.Gn是由n-數(shù)組a=(a1,a2,…,an)(ai∈G)構(gòu)成的集合,|Gn|=qn.Gn中a和b=(b1,b2,…,bn)的漢明距離定義為

dH(a,b)=|{i|1≤i≤n,ai≠bi}|.

Gn中每個(gè)子集合C均叫作一個(gè)q元碼長為n的糾錯(cuò)碼,C中n-數(shù)組c=(c1,c2,…,cn)叫作碼字,每個(gè)碼字代表某個(gè)信息經(jīng)過信道由Bob發(fā)給Alice.不在C中的向量不代表任何信息.碼字個(gè)數(shù)|C|=K≥2,通常小于qn,即C比Gn小.Gn中許多向量不是碼字,目的是為了糾錯(cuò).

除了碼長n,集合S中元素個(gè)數(shù)q和碼字個(gè)數(shù)K之外,另一個(gè)重要參數(shù)是碼C的最小距離d=d(C),它定義為不同碼字之間漢明距離的最小值,即

d=d(C)=min{dH(c,c′):c,c′∈C,c≠c′}.

綜合上述,要構(gòu)作碼長n的q元糾錯(cuò)碼C,碼字個(gè)數(shù)K=|C|≥2,最小距離d=d(C),這些參數(shù)表示成(n,K,d)q.希望對固定的q和n,K愈大愈好(表示傳輸信息量大),d愈大愈好(糾錯(cuò)能力強(qiáng)).以上是糾錯(cuò)碼的基本原理.

V.I.Levenshtein[2]研究信息傳輸中遇到的同步問題.考慮Bob將2個(gè)信息a=(a1,a2,…,an)和b=(b1,b2,…,bn)依次傳給Alice:(a1,a2,…,an,b1,b2…,bn…),a,b∈C.但是傳輸中并沒有an和b1之間的逗號,即Alice收到一串符號之后,不知是從何處分組,如果從a2開始的n-數(shù)組a2…anb1也是碼字,Alice就譯錯(cuò)了信息.所以,為了決定分組的逗號位置,要求對任意2個(gè)碼字a=(a1,a2,…,an)和b=(b1,b2,…,bn)∈C(可以a=b),不適宜的分組ai+1,…,an,b1,b2,…,bi(1≤i≤n-1)均不是碼字.滿足此要求的碼C叫作是無逗號碼.進(jìn)一步還希望:不僅不適宜的分組ai+1,…,an,b1,b2,…,bi(1≤i≤n-1)都不是碼字,而且和任何碼字的漢明距離都很大,即定義C的Comma-free指數(shù)為

ρ=ρ(C)=

min{dH(c,ai+1,…,an,b1,b2,…,bi):

c=(c1c2…cn),a=(a1a2…an),

b=(b1b2…bn)∈C,1≤i≤n-1}.

對于給定的q,n和ρ,希望K愈大愈好.令n-r=logqK,r=n-logqK叫碼C的冗余度,希望r愈小愈好.但是文獻(xiàn)[2]給了一個(gè)下界

如果r達(dá)到此下界,則CF碼C叫作是最優(yōu)的.

設(shè)G為n階交換群,A1,A2,…,Aq(q≥2)為G的兩兩不相交集合.|Ai|=ki≥1(1≤i≤m).如果{A1,A2,…,Aq}是G的一個(gè)(n,q;k1,k2,…,kq;ρ)-EDF,則文獻(xiàn)[2]中由此可構(gòu)作一個(gè)參數(shù)(n,K,ρ)q的CF碼,其中K=qn-r,而r=k1+k2+…+kq(≤n),并且這個(gè)CF碼是最優(yōu)的,當(dāng)且僅當(dāng)k1=k2=…=kq=k,即{A1,A2,…,Aq}是正則的(n,q;k,ρ)-EDF,其中

r=qk,k2q(q-1)=ρ(n-1).

于是

即CF碼是最優(yōu)的.

這就是外差組(EDF)這種設(shè)計(jì)最早的應(yīng)用背景.

2.2 外差組和AMD碼AMD碼是一類防欺騙的無條件安全的認(rèn)證碼.這里的認(rèn)證碼是(S,G,E),其中S為信息集合,|S|=m.不妨設(shè)S={1,2,…,m}.G為n階交換群.E為編碼函數(shù),對每個(gè)i,E(i)為G的一個(gè)子集合,并且E(i)(1≤i≤m)兩兩不相交.

令A(yù)i=E(i),則A1,A2,…,Am為G的兩兩不相交的子集合.|Ai|=ki(1≤i≤m),則k1+k2+…+km≤n.

設(shè)Bob把信息i發(fā)給Alice,Bob在集合Ai中隨機(jī)(等概率)地取t∈Ai=E(i),叫作tag(標(biāo)簽),把(i,t)發(fā)給Alice,t即是Bob對信息i所做的簽名.Alice收到(i,t)之后,計(jì)算t是否屬于Ai=E(i).由此來認(rèn)證消息是否由Bob發(fā)出的,如果t∈E(i),則Alice認(rèn)為消息是由Bob發(fā)出,i是Bob發(fā)給她的“真實(shí)”信息.編碼函數(shù)E由Bob和Alice約定,對外人保密.

現(xiàn)在,Tom想把一個(gè)偽造的信息i′發(fā)給Alice.Tom隨機(jī)取元素t′∈G,然后將(i′,t′)發(fā)給Alice.Alice收到后,恰好t′∈Ai′=E(i′),則Alice便認(rèn)為i′這是來自Bob的信息.又若i′≠i,則Alice相信了假的信息i′.所以在t′∈E(i′)并且i≠i′,Tom便成功欺騙了Alice.Alice和Bob希望設(shè)計(jì)編碼函數(shù)E使得欺騙成功概率達(dá)到最小(事實(shí)上,認(rèn)證碼采用許多編碼函數(shù)EK,其中K為密鑰,定期更換密鑰).

AMD碼是R.Cramer等[5]于2008年提出來的,后來的研究有文獻(xiàn)[8]等工作.在這種認(rèn)證碼中,Tom的欺騙方式為采用如下簡單的法則:隨機(jī)選取一個(gè)固定元素g∈G,然后將Bob的每個(gè)對i的簽名t都改成i′的簽名t+g.

AMD碼有2種欺騙策略,如果Tom只知Bob發(fā)出的tagt而事先不知Bob發(fā)給Alice的信息i,這時(shí)Tom發(fā)(i′,t′=t+g)給Alice,只有當(dāng)t′∈E(i′)并且i≠i′時(shí)才欺騙成功,這叫做是弱AMD碼.如果Tom知道i和t,這時(shí)向Alice發(fā)送(i′,t′),其中t′=t+g,由于Tom已知i,可取i′≠i保證i′為假信息.從而只需要t′∈E(i′)便欺騙成功.這叫作強(qiáng)AMD碼.文獻(xiàn)[6]中對弱AMD碼和強(qiáng)AMD碼都給出了欺騙成功的2種下界:G-下界和R-下界.達(dá)到這些下界的AMD碼分別叫作是G-最優(yōu)的和R-最優(yōu)的.

下面是強(qiáng)外差族這種組合設(shè)計(jì)和最優(yōu)AMD碼之間的關(guān)系.

設(shè)(S,G,E)為一個(gè)AMD碼,S={1,2,…,m},Ai=E(i)1≤i≤m為G中兩兩不相交的子集合,|Ai|=ki,文獻(xiàn)[6]中證明了:

定理 2.1 1) 如果{A1,A2,…,Am}為群G的(n,m;k1,k2,…,km;λ1,λ2,…,λm)-GSEDF,則(S,G,E)為R-最優(yōu)的強(qiáng)AMD碼和R-最優(yōu)的弱AMD碼.

2) 當(dāng)k1=k2=…=km=k,從而λ1=λ2=…=λm=λ時(shí),{A1,A2,…,Am}為(n,m;k,λ)-EDF,當(dāng)且僅當(dāng)(S,G,E)為R-最優(yōu)的弱AMD碼.

而G-最優(yōu)的弱AMD碼和強(qiáng)AMD碼相當(dāng)于BoundedGSEDF這類組合設(shè)計(jì),這里從略,可參見文獻(xiàn)[6].

基于上述應(yīng)用,近年來人們對于EDF、GEDF、GSEDF這幾種組合設(shè)計(jì)的構(gòu)造方法和存在性問題做出了一系列研究,下面將綜述這方面的進(jìn)展和一些待研究的問題.

3 設(shè)計(jì)的構(gòu)作和存在性問題

Cλ=θλC, 0≤λ≤e-1,C0=C, |Cλ|=f,

叫作是有限域Fq的e階分圓類,當(dāng)λ≡λ′(mode)時(shí),Cλ=Cλ′.

定義 3.1 對于0≤i,j≤e-1.以(i,j)e表示方程x-y=1,x∈Ci,y∈Cj的解數(shù),即(i,j)e=|(Cj+1)∩Ci|,叫作是Fq上的e階分圓數(shù).當(dāng)i≡i′,j≡j′(modee)時(shí),(i′,j′)e=(i,j)e.

下面列出分圓數(shù)的基本性質(zhì),多數(shù)性質(zhì)可由分圓數(shù)的定義直接推出,詳見文獻(xiàn)[17].

引理 3.2 設(shè)q-1=ef,(i,j)=(i,j)e為Fq上的e階分圓數(shù).Cλ(0≤λ≤e-1)為Fq中的e階分圓類,則對于0≤i,j≤e-1.

3) (i,j)=(-i,j-i).

分圓數(shù)可以用數(shù)論中一批重要的特征和(雅可比和、高斯和)來表示,從而分圓數(shù)的計(jì)算依賴于數(shù)論中這些特征和的計(jì)算問題,這是數(shù)論本身的一個(gè)重要課題.目前對于e=2,3,4,5,6,…等小值,人們計(jì)算出e階分圓數(shù)的值(可見文獻(xiàn)[17]).這里只舉一個(gè)簡單情形作為例子.

例 3.1 設(shè)q=pr,p為奇素?cái)?shù),e=2,q-1=2f,則Fq上的2階分圓數(shù)(i,j)=(i,j)2(0≤i,j≤1)為

由引理3.2的5),當(dāng)q≡3(mod4)時(shí),

當(dāng)q≡1(mod4)時(shí),

3.2 EDF的構(gòu)造 在EDF的構(gòu)作方面,分圓方法的起點(diǎn)是下面的結(jié)果.

定理 3.3 設(shè)q為素?cái)?shù)冪,q-1=ef,Cλ(0≤λ≤e-1)為Fq中的e階分圓類,則{C0,C1,…,Ce-1}為群(Fq,+)中(n,m;k,λ)=(q,e;f,q-f-1)-EDF.

證明 由引理3.2的5)有(記(i,j)=(i,j)e)

于是

Δ(Fq-{0},Fq-{0})-

(q-f-1)(Fq-{0}).

證畢.

進(jìn)一步,可以取Ai(1≤i≤m)為e階分圓類的一部分,也可取Ai為某些e階分圓類之并集.在某些條件下,也可得到{A1,A2,…,Am}為(Fq,+)的GEDF和EDF,并且有更靈活的參數(shù)，參見文獻(xiàn)[4，12，14，18].

除了分圓方法之外,構(gòu)作EDF還有利用完全非線性函數(shù)[10],以及其它組合方法[11,14].

3.3 SEDF的構(gòu)造 強(qiáng)外差組(SEDF)和它的推廣:廣義強(qiáng)外差組(GSEDF)是2016年提出的組合設(shè)計(jì)[6].至今只有為數(shù)不多的工作[19-23].GSEDF的構(gòu)作基于以下2個(gè)結(jié)果.首先在文獻(xiàn)[6]中證明了以下結(jié)果.

定理 3.4(文獻(xiàn)[6]的定理2.4) 設(shè)A1,A2,…,Am(m≥2)是交換群(G,+)的分拆(即A1,A2,…,Am彼此不相交,其并集為G)，則{A1,A2,…,Am}為G中的(n,m;k1,k2,…,km;λ1,λ2,…,λm)-GSEDF,當(dāng)且僅當(dāng)每個(gè)Ai均為G中的(n,ki,ki-λi)-DS(差集合).

證畢.

熟知若A為G中的(n,k,λ)-DS,則它的補(bǔ)集合G-A為G中的(n,n-k,n-2k+λ)-DS.于是由定理3.4得到m=2的GSEDF.

系 3.5 設(shè)A為G中的(n,k,λ)-DS,則{A,G-A}為G的(n,2;k,n-k;k-λ,k-λ)-GSEDF.

類似于定理3.4,在文獻(xiàn)[23]中證明了如下結(jié)果.

熟知若A∈G,0?A,A為G的(n,k,λ,μ)-PDS,則當(dāng)-A=A時(shí)A′=G-A-{0}為G的(n,n-k-1,λ′,μ′)-PDS,其中,λ′=n-2k+μ-2,μ′=n-2k+λ.若λ=μ-1,則λ′=μ′-1.于是定理3.6給出:

系 3.7(文獻(xiàn)[23]的引理2.5) 設(shè)(G,+)為n階交換群,A為G中的(n,k,λ,μ)-PDS,0?A,-A=A,則{A,G-A-{0}}為G的(n,2;k,n-k-1;k-λ-1,k-λ-1)-GSEDF.

例 3.2 設(shè)q-1=2f,C0,C1為Fq的2階分圓類.

對于e=2,4,6,8,文獻(xiàn)[17]中已計(jì)算出有限域上的e階分圓數(shù),從而對某些e階分圓類,Cλ或Cλ+{0}為Fq的差集合,由此因定理3.4可以構(gòu)作Fq中的一些GEDF[19,20,23].另一方面,滿足λ=μ-1的(n,k,λ,μ)-PDS是很少的.因?yàn)槲墨I(xiàn)[24](還可見文獻(xiàn)[25]的定理13.1)中證明了,若D為有限交換群G的(n,k;λ,μ)-PDS,λ=μ-1并且0∈D,D=-D,則參數(shù)必然為

(II) (n,k,λ,μ)=(243,22,1,2).

另一方面,構(gòu)作m≥3的SEDF似乎是困難的,文獻(xiàn)[6]中提出一個(gè)公開問題:是否存在m≥3的SEDF?不久文獻(xiàn)[17]中證明了不存在m=3和m=4的SEDF,文獻(xiàn)[19-20]又給出進(jìn)一步的不存在性結(jié)果,但是當(dāng)m≥5時(shí)是否存在SEDF一直是這些工作中不斷提出的公開問題.

[1] 萬哲先. 設(shè)計(jì)理論[M]. 北京:高等教育出版社,2009.

[2]LEVENSHTEINVI.Onemethodofconstructingquasilinearcodesprovidingsynchronizationinthepresenceoferrors[J].ProbInformTransm,1971,7:215-222.

[3]OGATAW,KURSAWAK,STINSONDR,etal.Newcombinatorialdisignsandtheirapplicationstoauthenticationcodesandsecretsharingshemes[J].DiscreteMath,2004,279(1):383-405.

[4]CHANGY,DINGC.Constructionsofexternaldifferencefamiliesanddisjointdifferencefamilies[J].DesCodesCryptogr,2006,40(2):167-185.

[5]CRAMERR,DODISY,FEHRS,etal.Detectionofalgebraicmanipulationwithapplicationstorobustsecretsharingandfuzzyextractors[J].LectureNotesinComputSci,2008,4965:471-488.

[6]PATERSONMB,STINSONDR.Combinatorialcharacterizationsofalgebraicmanipulationdectectioncodesinvolvinggeneralizeddifferencefamilies[J].DiscreteMath,2016,339(12):2891-2906.

[7]TONCHEVVD.Partitionsofdifferncesetsandcodesynchronization[J].FiniteFieldsandTheirAppl,2005,11(3):601-621.

[8]CRAMERR,FEHRS,PADROC.Algebraicmanipulationdetectioncodes[J].SciChinaMath,2013,56(7):1349-1458.

[9]DAVISJA,HUCZYNSKAS,MULLENGL.Near-completeexternaldifferencefamilies[J].DesCodesCryptogr,doi:10.1007/s10623-016-0275-7,2016.

[10]DINGC.Optimalandperfectdiffencesystemsofsets[J].JCombinTheory,2009,A116(1):109-119.

[11]FANCL,LEIJG,SHANXL.Constructionsofoptimaldifferencesystemsofsets[J].SciChinaMath,2011,54(1):173-184.

[12]FUJIWARAY,MOMIHARAK,YAMADAM.PerfectdifferencesystemsofsetsandJacobisums[J].DiscreteMath,2009,309(12):3954-3961.

[13]FUJIWARAY,TONCHEVV.D.Highrateself-synchronizingcodes[J].IEEETransInformTheory,2013,59(4):2328-2335.

[14]HUANGB,WUD.Cyclotomicconstructionsofexternaldifferencefamiliesanddisjointdifferencefamilies[J].JCombinDes,2009,17(4):334-341.

[15]LEIJ,FANC.Optimaldifferencesystemsofsetsandpartition-typecyclicdifferencepackings[J].DesCodesCryptogr,2011,58(2):135-153.

[16]NGSL,PATERSONMB.Disjointdifferencefamiliesandtheirapplications[J].DesCodesCryptogr,2016,78(1):103-127.

[17]STORERT.CyclotomyandDifferenceSets[M].Chicago:MarkhamPubCo,1967.

[18]MUTOHY,TOCHEVV.Differencesystemsofsetsandcyclotomy[J].DiscreteMath,2008,308(14):2959-2969.

[19]BAOJ,JIL,WEIR,etal.Newexistenceandnonexistenceresultsforstrongexternaldifferencefamilies[J/OL].arXiv:1612.08385,2016.

[20]HUCZYNSKAS,PATERSONMB.Existenceandnon-existenceresultsforstrongexternaldifferencfamilies[J/OL].arXiv:1611.05652,2016.

[21]MARTINW,STINSOND.Somenonexistenceresultsforstrongexternaldifferencefamiliesusingcharactertheory[J/OL].arXiv:1601.06432,2016.

[22]WENJ,YANGM,FENGK.The(n,m,k,λ)-strongexternaldifferencefamilywithm≥5exists[J/OL].arXiv:1612.09495,2017.

[23]WENJ,YANGM,FENGK.Cyclotomicconstructionofstrongexternaldifferencefamiliesinfinitefields[J/OL].arXiv:1701.01796,2017.

[24]ARASUKT,JUNGNICKELD,MASL,etal.StrongCayleygraphswithλ-μ=-1[J].JCombinTheory,1994,67(1):116-125.

[25]MASL.Asurveyofpartialdifferencesets[J].DesCodesCryptogr,1994,4(4):221-261.

[26]LEUNGKH,MASL.PartialdifferencesetsandPaleyparameters[J].BullLondMathSoc,1995,27(6):553-564.

[27]POLHILLJ.Paleypartialdifferencesetsingroupsofordern4and9n4foranyoddn > 1[J].JCobminTheory,2010,A117(8):1027-1036.

[28]JEDWABJ,LIS.Constructionandnonexistenceofstrongexternaldifferencefamilies[J].Preprint,2017.

2010 MSC：94B05

(編輯 李德華)

External Difference Families and Their Applications in Communication

YANG Minghui1, WEN Jiejing2, FENG Keqin3

( 1.StateKeyLaboratoryofInformationSecurity,InstituteofInformationEngineering,ChineseAcademyofSciences,Beijing100193; 2.ChernInstituteofMathematics,NankaiUniversity,Tianjin300071; 3.DepartmentofMathematicalScience,TsinghuaUniversity,Beijing10084)

Combinatorial designs have wide applications in communications. This paper is a survey on several new types of combinatorial designs including external difference family and its generalizations and variations, raised recently based on their applications in synchronization communication, authentication, secrete sharing schemes, etc. In this paper we explain the relationship between the new types of combinatorial designs and communication applications, introduce several construction method and existence results of these combinatorial designs and some unsolved problems.

difference set; generalized external difference family(GEDF); AMD code; authentication code; cyclotomic class; cyclotomic number

2017-03-02

國家自然科學(xué)基金(11571007和11471178)

O157.2

A

1001-8395(2017)04-0561-08

10.3969/j.issn.1001-8395.2017.04.021

*通信作者簡介:馮克勤(1941—),男,教授,主要從事代數(shù)、數(shù)論和編碼密碼學(xué)理論的研究,E-mail:kfeng@math.tsinghua.edu.cn