Degree Name

Doctor of Philosophy


School of Information Technology & Computer Science - Faculty of Informatics


In this thesis, we consider the traitor tracing problem. We study codes with different traceability properties and public key traitor tracing schemes. We study maximal codes with 2-identifiable parent property. Using graph theoretic techniques, we determine the structure of the graph representation of maximal codes of length three having 2-identifiable parent property, and derive the number of codewords in such codes. Maximal 2-identifiable parent property codes of length four have recently been studied. It is still an open problem to determine the size and structure of a maximal 2-identifiable parent property code of length greater than four. We present a direct construction of 2-secure frameproof codes with logarithmic length. This is the only known direct construction with logarithmic length codes. All other known constructions of short codes use recursive techniques. We introduce a new combinatorial object called difference function families which is a generalization of difference matrices. Using difference function families, we present recursive constructions that we can apply to small codes to obtain larger codes with the same security property. Our recursive techniques generalize some of the known recursive techniques and give better results. The most important advantage of our technique is that it can be applied to all secure codes and hash families. That is, it can be applied to frameproof codes, secure frameproof codes, IPP codes, TA codes, separating hash families, perfect hash families. No other known techniques have this property. We give a linear attack on the first traitor tracing scheme that uses bilinear pairing. We generalize this attack to all traitor tracing schemes in which decryption keys satisfy a linear equation. We show that in these schemes the length of the decryption key must depend on the collusion threshold in order to resist the linear attack. We derive a lower bound on the size of the decryption key length in terms of the number of colluders. We propose three new public key traitor tracing schemes based on bilinear maps. The first scheme is a modification of the Mitsunari et al's scheme. The second scheme is a generalization of the first scheme in which we use linear codes. And the final scheme has the revocation capacity by using Shamir's secret sharing technique. The security of all three schemes are provable and it is based on the decisional bilinear Diffie--Hellman assumption. These are the only known traitor tracing schemes using bilinear maps which have not been broken. We extend a result due to Kurosawa and Yoshida and show that public-key traitor tracing schemes with revocation can be constructed from linear codes. It means that we can have revocation for the Boneh-Franklin scheme, the corrected Kurosawa-Desmedt scheme and the linear-coded Kurosawa--Desmedt scheme. We also look at the problem of permanently removing a user to make the system scalable. We prove that it is impossible to obtain a remove-user procedure for the Boneh-Franklin scheme where all the secret part of user keys are kept unchanged and only the public encryption key and the public part of user keys are modified. We show an attack on the Dodis et al's scheme in which two users who had been removed in two different sessions can collaborate to obtain valid keys for future sessions.

02Whole.pdf (1206 kB)