Back to search

University of Waterloo

Fingerprinting Codes and Related Combinatorial Structures

Abstract

dc:description.abstract

Fingerprinting codes were introduced by Boneh and Shaw in 1998 as a method of copyright control. The desired properties of a good fingerprinting code has been found to have deep connections to combinatorial structures such as error-correcting codes and cover-free families. The particular property that motivated our research is called "frameproof". This has been studied extensively when the alphabet size q is at least as large as the colluder size w. Much less is known about the case q < w, and we prove several interesting properties about the binary case q = 2 in this thesis. When the length of the code N is relatively small, we have shown that the number of codewords n cannot exceed N, which is a tight bound since the n = N case can be satisfied a trivial construction using permutation matrices. Furthermore, the only possible candidates are equivalent to this trivial construction. Generalization to a restricted parameter set of separating hash families is also given. As a consequence, the above result motivates the question of when a non-trivial construction can be found, and we give some definitive answers by considering combinatorial designs. In particular, we give a necessary and sufficient condition for a symmetric design to be a binary 3-frameproof code, and provide example classes of symmetric designs that satisfy or fail this condition. Finally, we apply our results to a problem of constructing short binary frameproof codes.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Guo, Chuan

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/9260

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Guo, Chuan. Fingerprinting Codes and Related Combinatorial Structures. University of Waterloo, 2015. http://hdl.handle.net/10012/9260