On codes for traceability schemes: constructions and bounds

Abstract

A traceability or fingerprinting scheme is a cryptographic scheme that facilitates the identification of the source of leaked information. In a fingerprinting setting, a distributor delivers copies of a given content to a set of authorized users. If there are dishonest members (traitors) among them, the distributor can deter plain redistribution of the content by delivering a personalized, i.e., marked, copy to each user. The set of all user marks is known as a fingerprinting code. There is, however, another threat. If several traitors collude to create a copy that is a combination of theirs, then the pirated copy generated will contain a corrupted mark, which may obstruct the identification of traitors. This dissertation is about the study and analysis of codes for their use in traceability and fingerprinting schemes, under the presence of collusion attacks. Moreover, another of the main concerns in the present work will be the design of identification algorithms that run efficiently, i.e., in polynomial time in the code length. In Chapters 1 and 2, we introduce the topic and the notation used. We also discuss some properties that characterize fingerprinting codes known under the names of separating, traceability (TA), and identifiable parent property (IPP), which will be subject of research in the present work. Chapter 3 is devoted to the study of the Kötter-Vardy algorithm to solve a variety of problems that appear in fingerprinting schemes. The concern of the chapter is restricted to schemes based on Reed-Solomon codes. By using the Kötter-Vardy algorithm as the core part of the identification processes, three different settings are approached: identification in TA codes, identification in IPP codes and identification in binary concatenated fingerprinting codes. It is also discussed how by a careful setting of a reliability matrix, i.e., the channel information, all possibly identifiable traitors can be found. In Chapter 4, we introduce a relaxed version of separating codes. Relaxing the separating property lead us to two different notions, namely, almost separating and almost secure frameproof codes. From one of the main results it is seen that the lower bounds on the asymptotical rate for almost separating and almost secure frameproof codes are greater than the currently known lower bounds for ordinary separating codes. Moreover, we also discuss how these new relaxed versions of separating codes can be used to show the existence of families of fingerprinting codes of small error, equipped with polynomial-time identification algorithms. In Chapter 5, we present explicit constructions of almost secure frameproof codes based on weakly biased arrays. We show how such arrays provide us with a natural framework to construct these codes. Putting the results obtained in this chapter together with the results from Chapter 4, shows that there exist explicit constructions of fingerprinting codes based on almost secure frameproof codes with positive rate, small error and polynomial-time identification complexity. We remark that showing the existence of such explicit constructions was one of the main objectives of the present work. Finally, in Chapter 6, we study the relationship between the separating and traceability properties of Reed-Solomon codes. It is a well-known result that a TA code is an IPP code, and that an IPP code is a separating code. The converse of these implications is in general false. However, it has been conjectured for some time that for Reed-Solomon codes all three properties are equivalent. Giving an answer to this conjecture has importance in the field of fingerprinting, because a proper characterization of these properties is directly related to an upper bound on the code rate i.e., the maximum users that a fingerprinting scheme can allocate. In this chapter we investigate the equivalence between these properties, and provide a positive answer for a large number of families of Reed-Solomon codes.

Un sistema de trazabilidad o de fingerprinting es un mecanismo criptogr afi co que permite identi car el origen de informaci on que ha sido fi ltrada. En el modelo de aplicación de estos sistemas, un distribuidor entrega copias de un determinado contenido a un conjunto de usuarios autorizados. Si existen miembros deshonestos (traidores) entre ellos, el distribuidor puede disuadir que realicen una redistribuci on ingenua del contenido entregando copias personalizadas, es decir, marcadas, a cada uno de los usuarios. El conjunto de todas las marcas de usuario se conoce como c ódigo de fingerprinting. No obstante, existe otra amenaza m as grave. Si diversos traidores confabulan para crear una copia que es una combinación de sus copias del contenido, entonces la copia pirata generada contendr a una marca corrompida que di ficultar a el proceso de identificaci on de traidores. Esta tesis versa sobre el estudio y an alisis de c odigos para su uso en sistemas de trazabilidad o de fi ngerprinting bajo la presencia de ataques de confabulaci on. Otra de las cuestiones importantes que se tratan es el diseño de algoritmos de identi caci on e ficientes, es decir, algoritmos que se ejecuten en tiempo polin omico en la longitud del c odigo. En los Cap tulos 1 y 2 presentamos el tema e introducimos la notaci on que utilizaremos. Tambi en presentaremos algunas propiedades que caracterizan los c odigos de fi ngerprinting, conocidas bajo los nombres de propiedad de separaci on, propiedad identi cadora de padres (IPP) y propiedad de trazabilidad (TA), que est an sujetas a estudio en este trabajo. El Cap tulo 3 est a dedicado al estudio del algoritmo de decodi caci on de lista con informaci on de canal de Kötter-Vardy en la resoluci on de determinados problemas que aparecen en sistemas de fingerprinting. El ambito de estudio del cap ítulo son sistemas basados en c odigos de Reed-Solomon. Empleando el algoritmo de Kötter-Vardy como parte central de los algoritmos de identifi caci on, se analizan tres propuestas en el cap ítulo: identi caci on en c odigos TA, identifi caci on en c odigos IPP e identifi caci on en c odigos de fingerprinting binarios concatenados. Tambi en se analiza c omo mediante un cuidadoso ajuste de una matriz de abilidad, es decir, de la informaci on del canal, se pueden encontrar a todos los traidores que es posible identi car e ficientemente. En el Capí tulo 4 presentamos una versi on relajada de los c odigos separables. Relajando la propiedad de separaci on nos llevar a a obtener dos nociones diferentes: c odigos cuasi separables y c odigos cuasi seguros contra incriminaciones. De los resultados principales se puede observar que las cotas inferiores de las tasas asint oticas para c odigos cuasi separables y cuasi seguros contra incriminaciones son mayores que las cotas inferiores actualmente conocidas para c odigos separables ordinarios. Adem as, tambi en estudiamos como estas nuevas familias de c odigos pueden utilizarse para demostrar la existencia de familias de c odigos de ngerprinting de baja probabilidad de error y dotados de un algoritmo de identi caci on en tiempo polin omico. En el Capí tulo 5 presentamos construcciones expl citas de c odigos cuasi seguros contra incriminaciones, basadas en matrices de bajo sesgo. Mostramos como tales matrices nos proporcionan una herramienta para construir dichos c odigos. Poniendo en com un los resultados de este cap tulo con los del Capí tulo 4, podemos ver que, bas andonos en c odigos cuasi seguros contra incriminaciones, existen construcciones expl ícitas de c odigos de fi ngerprinting de tasa positiva, baja probabilidad de error y con un proceso de identi caci on en tiempo polin omico. Demostrar que existen dichas construcciones expl citas era uno de los principales objetivos de este trabajo. Finalmente, en el Capí tulo 6, estudiamos la relaci on existente entre las propiedades de separaci on y trazabilidad de los c odigos de Reed-Solomon. Es un resultado bien conocido el hecho que un c odigo TA es un c odigo IPP, y que un c odigo IPP es un c odigo separable. Las implicaciones en el sentido opuesto son falsas en general. No obstante, existe una conjetura acerca de la equivalencia de estas tres propiedades en el caso de cóodigos de Reed-Solomon. Obtener una respuesta a esta conjetura es de una importancia relevante en el campo del fi ngerprinting, puesto que la caracterización de estas propiedades est a directamente relacionada con una cota superior en la tasa del c odigo, es decir, con el n umero de usuarios que puede gestionar un sistema de fi ngerprinting. En este cap ítulo investigamos esta equivalencia y proporcionamos una respuesta afirmativa para un gran n umero de familias de c odigos de Reed-Solomon. Los resultados obtenidos parecen sugerir que la conjetura es cierta.