Generalized hashing and parent-identifying codes
Generalized hashing and parent-identifying codes
复制标题
DOI：
10.1016/j.jcta.2003.08.001
复制
发表时间：
2003-10
期刊：
影响因子：
--
通讯作者：
N. Alon;G. Cohen;Michael Krivelevich;S. Litsyn
中科院分区：
文献类型：
--
作者：
N. Alon;G. Cohen;Michael Krivelevich;S. Litsyn
设C是一个长度为n的代码，覆盖一个字母表，字母表中有q个字母。对于一对整数2 <$t<u，C是（t，u）-hashing，如果对于任意两个子集T，U <$C，满足T <$U，|不|=t，|U| =u，存在一个坐标1 <$i <$n使得对于任何x∈T，y∈U−x，x和y在第i个坐标中不同。这个定义，概括了一个标准的概念的t-哈希家庭，是由一个应用程序在设计所谓的父母识别码，用于数字指纹的动机。在本文中，我们针对固定的t、u和不断增长的n，提供了（t，u）-哈希族的最佳可能速率的下限和上限。我们还描述了一个明确的建设（t，u）-哈希家庭。应用所得到的（t，u）-hashing族的速率下界，得到了一个新的t-父识别码的速率下界。
Let C be a code of length n over an alphabet of q letters. For a pair of integers 2⩽t<u, C is (t,u)-hashing if for any two subsets T,U⊂C, satisfying T⊂U, |T|=t, |U|=u, there is a coordinate 1⩽i⩽n such that for any x∈T, y∈U−x, x and y differ in the ith coordinate. This definition, generalizing the standard notion of a t-hashing family, is motivated by an application in designing the so-called parent identifying codes, used in digital fingerprinting. In this paper, we provide lower and upper bounds on the best possible rate of (t,u)-hashing families for fixed t,u and growing n. We also describe an explicit construction of (t,u)-hashing families. The obtained lower bound on the rate of (t,u)-hashing families is applied to get a new lower bound on the rate of t-parent identifying codes.