论文部分内容阅读
为了尽可能地缩短多媒体指纹码的码长，但同样又具有抗合谋攻击的能力，程民权和蒋静等人分别提出了多媒体父辈认证码和强多媒体父辈认证码.这两类指纹码受到组合界的高度关注.但因其结构复杂，目前的结果还比较少.因此本文侧重于研究这两类指纹码. 为了介绍多媒体父辈认证码和强多媒体父辈认证码的概念，先介绍如下记号.设n，M，q是正整数，Q是字母表且|Q|=q.称集合C={c1，c2，…，cM}(∈)Qn为(n, M，q)码，其中c=(c(1)，c(2)，…，c(n))T称为C的码字.如果把每个码字看成一个列向量，则码C可以看作一个矩阵.不失一般性，设Q={0，1，…，q-1}.当Q={0，1}时，C通常称为二元码.对任意的C0(∈)C，C0的第i行（1≤i≤n）坐标集记为: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}. 因为t-(n，M，q)SMIPPC中参数M的值对应的是合法用户的数量，对于给定的码长n，所以我们的码字个数M尽可能的大.令MS(t，n，q)=max{M|存在一个t-(n，M，q)SMIPPC}.对于一个t-(n，M，q)SMIPPC，若M=MS(t,n，q)，我们称它是最优的.对于一个无穷类t-(n，M，q)SMIPPC,若lim q→∞ M/(Ms(t，n，q)=1，我们称它是渐进最优的. 定义1设C是（n，M，q）码，对任意的码字子集C0且满足1≤|C0|≤t. 若∩C∈Pt(C0)C≠(0)恒成立，其中Pt(C0)={C(∈)C|desc(C)=desc(C0)，1≤|C|≤t}，则称C是多媒体父辈认证码(multimedia identifiable parent property code)，简记为t-(n，M，q)MIPPC. 若∩C∈P(c0)C≠(O)恒成立，其中P(C0)={C(∈)C|desc(C)=desc(C0)}则称C是强多媒体父辈认证码(strong multimedia identifiable parent property code)，简记为t-(n,M，q)SMIPPC.由于多媒体父辈认证码和强多媒体父辈认证码的结构比较复杂，目前关于码长为2和3的结果还比较少.因此本文仅针对码长为2和3的情况进行研究，分别得到如下结果: 定理1设C是一个(2，M，q)码.C是一个t-(2，M，q)SMIPPC当且仅当C不包含下列模式(a1 a1 a2 a2… ai aib1 b2 b2 b3… bi b1)(1)其中1≤i≤t且对任意的1≤j1，j2≤i，有aj1≠aj2，bj1≠bj2. 定理2存在一个t-(2，M，q)SMIPPC的充要条件是存在一个girth为2(t+1)的二部图G(q，q)且e(G)=M. 定理3对任意t-(2，M，q)SMIPPC恒有M≤{+2qc t是奇数，q1/2q t+2/2t+2qc t是偶数，q1/2qt+2/2t+2qc t是偶数，其中常数c的值只与t有关. 定理4对任意素数幂k，存在渐近最优5-(2，M，q)SMIPPC，其中q=(1+k)(1+k2+k4)，M=（1+k）(1+k)(1+k2+k4). 定理5设C是一个(2，M，q)码.C是一个t-(2，M，q)SMIPPC当且仅当C是一个t-(2，M，q)MIPPC. 定理6设C是2-(3，M，q)FPC.C是一个3-(3，M，q)MIPPC当且仅当下面的▽不是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. 第一章分别介绍相关知识和主要结果;第二章利用二部图的相关知识给出了t-(2，M，q)SMIPPC的码字个数的上界，并利用广义六边形得到渐近最优的5-(2，M，q)SMIPPC;第三章分别研究了t-(2，M，q)MIPPC和3-(3，M，q)MIPPC;第四章为小结和可进一步研究的问题.