Martirosyan, Sosina:

Perfect hash families, identifiable parent property codes and covering arrays

Duisburg-Essen (2003), VI, 115 S.
Dissertation / Fach: Mathematik
Fakultät für Mathematik
Dissertation
Abstract:
In letzter Zeit haben einige kombinatorische Strukturen und Codes eine Vielzahl verschiedener Anwendungen in der Kommunikationstechnik, Kryptographie, Netzwerktechnik und der Informatik gefunden. Der Zweck dieser Dissertation ist, offene Probleme im Zusammenhang mit verschiedenen kombinatorischen Objekten zu lösen, welche durch praktische Anwendungen im Bereich der Informatik und Kryptographie motiviert sind. Genauer gesagt, untersuchen wir perfect hash families, identifiable parent property codes und covering arrays. Perfect hash families sind kombinatorische Strukturen, die verschiedene praktische Anwendungen haben, so wie Compilerbau, Probleme der Komplexität von Schaltkreisen, Datenbank-Verwaltung, Betriebssysteme, derandomization probabilistischer Algorithmen und broadcast encryption. Wir konzentrieren uns auf explizite Konstruktionsverfahren für perfect hash families. Erstens liefern wir eine explizite rekursive Konstruktion einer unendlichen Klasse von perfect hash families mit dem besten bekannten asymptotischen Verhalten unter allen ähnlichen, bekannten Klassen. Zum zweiten stellen wir ein neues rekursives Konstruktionsverfahren vor, mit dessen Hilfe man ‘gute’ perfect hash families für kleine Parameter erzeugen kann. Durch diese Methode erhalten wir eine unendliche Klasse von perfect hash families, die eine sehr große Menge von Parameter-Werten abdeckt. Weiterhin leiten wir eine neue untere Schranke für die minimale Anzahl von Hash-Funktionen her. Ein Vergleich der existierenden Schranken zeigt, dass unsere Schranke für einige Parameter-Bereiche schärfer ist als andere bekannte Schranken. Identifiable parent property codes (IPP) wurden entwickelt für die Anwendung in Verfahren, die urheberrechtlich geschützte digitale Daten gegen unerlaubte Kopien schützen, die gemeinsam von mehreren berechtigten Nutzern hergestellt werden. TA codes sind eine gut erforschte Teilmenge der IPP-Codes. Wir stellen zwei neue Konstruktionen für IPP-Codes vor. Unsere erste Konstruktion bietet eine unendlichen Klasse von IPP-Codes mit dem besten bekannten asymptotischen Verhalten unter allen ähnlichen Klassen in der Literatur. Weiterhin beweisen wir, dass diese Codes ein Verfahren zum Finden von Verrätern mit im Allgemeinen Laufzeit O(M) erlauben, wobei M die Code-Größe ist. Man beachte, dass vorher außer den TA-Codes keine IPP-Codes mit dieser Eigenschaft bekannt waren. Für einige unendliche Unterklassen dieser Codes kann man sogar noch schnellere Verfahren zum Aufspüren von Verrätern finden, mit Laufzeit poly(logM). Außerdem wird eine neue unendliche Klasse von IPP-Codes konstruiert, die ‘gute’ IPP-Codes für nicht zu große Werte von n liefert, wobei n die Code-Länge bezeichnet. Diese Klasse von IPP-Codes deckt einen großen Bereich von Parameter-Werten ab. Weiterhin konstruieren wir eine große Klasse von w-TA-Codes, die eine positive Antwort auf ein offenes Existenzproblem geben. Covering arrays sind von vielen Wissenschaftlern intensiv untersucht worden, aufgrund ihrer zahlreichen Anwendungen in der Informatik, so wie Software- oder Schaltkreis-Testen, switching networks, Datenkompressions-Probleme, und etliche mathematische Anwendungen, so wie Differenz-Matrizen, Such-Theorie und Wahrheits-Funktionen. Wir untersuchen explizite Konstruktions-Methoden für t-covering arrays. Zuerst benutzen wir den Zusammenhang zwischen perfect hash families und covering arrays, um unendliche Familien von t-covering arrays zu finden, für die wir beweisen, dass sie besser sind als die augenblicklich bekannten probabilistischen Schranken für covering arrays. Diese Familien haben ein sehr gutes asymptotisches Verhalten. Zum zweiten liefern wir, angeregt durch ein Ergebnis von Roux und auch von einem kürzlich erzielten Ergebnis von Chateauneuf und Kreher für 3-covering arrays, verschiedene neue Konstruktionen für t-covering arrays, t >_ 4, die als eine Verallgemeinerung dieser Ergebnisse gesehen werden können.