**Prolific Codes with the Identifiable Parent Property**

*Simon R. Blackburn and Tuvi Etzion and Siaw-Lynn Ng*

**Abstract: **Let C be a code of length n over an alphabet of size q. A word
d is a descendant of a pair of codewords x,y if
d_i lies in \{x_i ,y_i \} for 1 <= i <= n. A code C
is an identifiable parent property (IPP) code if the following
property holds. Whenever we are given C and a descendant d of
a pair of codewords in C, it is possible to determine at least one
of these codewords.

The paper introduces the notion of a prolific IPP code. An IPP code is prolific if all q^n words are descendants. It is shown that linear prolific IPP codes fall into three infinite (`trivial') families, together with a single sporadic example which is ternary of length 4. There are no known examples of prolific IPP codes which are not equivalent to a linear example: the paper shows that for most parameters there are no prolific IPP codes, leaving a relatively small number of parameters unsolved. In the process the paper obtains upper bounds on the size of a (not necessarily prolific) IPP code which are better than previously known bounds.

**Category / Keywords: **combinatorial cryptography

**Date: **received 18 Jul 2007

**Contact author: **s blackburn at rhul ac uk

**Available format(s): **PDF | BibTeX Citation

**Version: **20070807:151337 (All versions of this report)

**Short URL: **ia.cr/2007/276

[ Cryptology ePrint archive ]