強(qiáng)多媒體父輩認(rèn)證碼及其相關(guān)研究.pdf

1、為了盡可能地縮短多媒體指紋碼的碼長(zhǎng)，但同樣又具有抗合謀攻擊的能力，程民權(quán)和蔣靜等人分別提出了多媒體父輩認(rèn)證碼和強(qiáng)多媒體父輩認(rèn)證碼.這兩類指紋碼受到組合界的高度關(guān)注.但因其結(jié)構(gòu)復(fù)雜，目前的結(jié)果還比較少.因此本文側(cè)重于研究這兩類指紋碼.
　　為了介紹多媒體父輩認(rèn)證碼和強(qiáng)多媒體父輩認(rèn)證碼的概念，先介紹如下記號(hào).設(shè)n，M，q是正整數(shù)，Q是字母表且|Q|=q.稱集合C={c1，c2，…，cM}(∈)Qn為(n, M，q)碼，其中c=(c(1

2、)，c(2)，…，c(n))T稱為C的碼字.如果把每個(gè)碼字看成一個(gè)列向量，則碼C可以看作一個(gè)矩陣.不失一般性，設(shè)Q={0，1，…，q-1}.當(dāng)Q={0，1}時(shí)，C通常稱為二元碼.對(duì)任意的C0(∈)C，C0的第i行（1≤i≤n）坐標(biāo)集記為:C0(i)={c(i)∈Q| c=(c(1),c(2),…,c(n))T∈C0}.C0的后代碼記為:desc(C0)={(x(1),x(2),…, x(n))T∈Qn|x(i)∈C0(i),1≤i≤n}

3、.
　　因?yàn)閠-(n，M，q)SMIPPC中參數(shù)M的值對(duì)應(yīng)的是合法用戶的數(shù)量，對(duì)于給定的碼長(zhǎng)n，所以我們的碼字個(gè)數(shù)M盡可能的大.令MS(t，n，q)=max{M|存在一個(gè)t-(n，M，q)SMIPPC}.對(duì)于一個(gè)t-(n，M，q)SMIPPC，若M=MS(t,n，q)，我們稱它是最優(yōu)的.對(duì)于一個(gè)無(wú)窮類t-(n，M，q)SMIPPC,若lim q→∞ M/(Ms(t，n，q)=1，我們稱它是漸進(jìn)最優(yōu)的.
　　定義1設(shè)C是（n，

4、M，q）碼，對(duì)任意的碼字子集C0且滿足1≤|C0|≤t.
　　若∩C'∈Pt(C0)C'≠(0)恒成立，其中Pt(C0)={C'(∈)C|desc(C')=desc(C0)，1≤|C'|≤t}，則稱C是多媒體父輩認(rèn)證碼(multimedia identifiable parent property code)，簡(jiǎn)記為t-(n，M，q)MIPPC.
　　若∩C'∈P(c0)C'≠(O)恒成立，其中P(C0)={C'(∈)C|d

5、esc(C')=desc(C0)}則稱C是強(qiáng)多媒體父輩認(rèn)證碼(strong multimedia identifiable parent property code)，簡(jiǎn)記為t-(n,M，q)SMIPPC.由于多媒體父輩認(rèn)證碼和強(qiáng)多媒體父輩認(rèn)證碼的結(jié)構(gòu)比較復(fù)雜，目前關(guān)于碼長(zhǎng)為2和3的結(jié)果還比較少.因此本文僅針對(duì)碼長(zhǎng)為2和3的情況進(jìn)行研究，分別得到如下結(jié)果:
　　定理1設(shè)C是一個(gè)(2，M，q)碼.C是一個(gè)t-(2，M，q)SMIPP

6、C當(dāng)且僅當(dāng)C不包含下列模式(a1 a1 a2 a2… ai aib1 b2 b2 b3… bi b1)(1)其中1≤i≤t且對(duì)任意的1≤j1，j2≤i，有aj1≠aj2，bj1≠bj2.
　　定理2存在一個(gè)t-(2，M，q)SMIPPC的充要條件是存在一個(gè)girth為2(t+1)的二部圖G(q，q)且e(G)=M.
　　定理3對(duì)任意t-(2，M，q)SMIPPC恒有M≤{+2qc t是奇數(shù)，q1/2q t+2/2t+2qc

7、t是偶數(shù)，q1/2qt+2/2t+2qc t是偶數(shù)，其中常數(shù)c的值只與t有關(guān).
　　定理4對(duì)任意素?cái)?shù)冪k，存在漸近最優(yōu)5-(2，M，q)SMIPPC，其中q=(1+k)(1+k2+k4)，M=（1+k）(1+k)(1+k2+k4).
　　定理5設(shè)C是一個(gè)(2，M，q)碼.C是一個(gè)t-(2，M，q)SMIPPC當(dāng)且僅當(dāng)C是一個(gè)t-(2，M，q)MIPPC.
　　定理6設(shè)C是2-(3，M，q)FPC.C是一個(gè)3-(3，M，

8、q)MIPPC當(dāng)且僅當(dāng)下面的▽不是C的子集，其中▽=(a1 b1 c1 a1 b1 c1a2 b2 c2 b2 c2 a2a3 b3 c3 c3 a3 b3)，|{ai，bi，ci}|=3,i=1,2,3.
　　第一章分別介紹相關(guān)知識(shí)和主要結(jié)果;第二章利用二部圖的相關(guān)知識(shí)給出了t-(2，M，q)SMIPPC的碼字個(gè)數(shù)的上界，并利用廣義六邊形得到漸近最優(yōu)的5-(2，M，q)SMIPPC;第三章分別研究了t-(2，M，q)MIPPC和