Parent-identifying codes

被引:28
作者
Alon, N [1 ]
Fischer, E
Szegedy, M
机构
[1] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, Israel
[2] NEC Res Inst, Princeton, NJ 08540 USA
[3] Inst Adv Study, Sch Math, Princeton, NJ 08540 USA
基金
以色列科学基金会;
关键词
D O I
10.1006/jcta.2001.3177
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a set C of words of length 4 over an alphabet of size n, and for a, b is an element of C, let D (a, b) be the set of all descendants of a and b, that is, all words x of length 4 where x(i) is an element of {a(i), b(i)} for all 1 less than or equal to i less than or equal to 4. The code C satisfies the Identifiable Parent Property if for any descendant of two code-words one can identify at least one parent. The study of such codes is motivated by questions about schemes that protect against piracy of software. Here we show that for any epsilon > 0, if the alphabet size is n > n(0)(epsilon) then the maximum possible cardinality of such a code is less than epsilonn(2) and yet it is bigger than n(2-epsilon). This answers a question of Hollmann, van Lint, Linnartz, and Tolhuizen. The proofs combine graph theoretic tools with techniques in additive number theory. (C) 2001 Academic Press.
引用
收藏
页码:349 / 359
页数:11
相关论文
共 5 条
[1]   THE ALGORITHMIC ASPECTS OF THE REGULARITY LEMMA [J].
ALON, N ;
DUKE, RA ;
LEFMANN, H ;
RODL, V ;
YUSTER, R .
JOURNAL OF ALGORITHMS, 1994, 16 (01) :80-109
[3]   On codes with the identifiable parent property [J].
Hollmann, HDL ;
van Lint, JH ;
Linnartz, JP ;
Tolhuizen, LMGM .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1998, 82 (02) :121-133
[4]   SOLVING A LINEAR-EQUATION IN A SET OF INTEGERS-I [J].
RUZSA, IZ .
ACTA ARITHMETICA, 1993, 65 (03) :259-282
[5]  
Szemeredi E., 1976, C INTERCNRS NO 260 P, P399