Paper 2009/549

Making Collusion-Secure Codes (More) Robust against Bit Erasure

Koji Nuida

Abstract

A collusion-secure code is called robust if it is secure against erasure of a limited number of undetectable bits, in addition to collusion attacks under Marking Assumption. In this article, we propose the first general conversion method of (non-robust) $c$-secure codes to robust $c$-secure codes. Also, the same method amplifies robustness of given robust $c$-secure codes. By applying our conversion to $c$-secure codes given by Nuida et al. (AAECC 2007), we present robust $c$-secure codes with code length of order $\Theta(c^2 \log^2 c)$ with respect to $c$. This code length improves preceding results by Sirvent (WCC 2007) and by Boneh and Naor (ACM CCS 2008) and is close to the one by Billet and Phan (ICITS 2008), although our construction is based on a weaker assumption than those preceding results. As an application, applying our resulting code to construction by Boneh and Naor also improves their traitor tracing scheme against imperfect decoders in efficiency of both key sizes and pirate tracing procedure.

Note: A preliminary version of this work is to be presented at The 4th International Conference on Information Theoretic Security (ICITS 2009), Shizuoka, Japan, December 3-6, 2009.