Prolific Codes with the Identifiable Parent Property

Simon R.  Blackburn; Tuvi Etzion; Siaw-Lynn Ng

Paper 2007/276 Original: eprint.iacr.org/2007/276 ↗

Prolific Codes with the Identifiable Parent Property

Simon R. Blackburn

Tuvi Etzion

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.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2007-08-07: last updated; 2007-08-07: published
Short URL: https://ia.cr/2007/276
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2007/276,
      author = {Simon R.  Blackburn and Tuvi Etzion and Siaw-Lynn Ng},
      title = {Prolific Codes with the Identifiable Parent Property},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/276},
      year = {2007},
      url = {https://eprint.iacr.org/2007/276}
}