Rigorously Analyzed Algorithms for the Discrete Logarithm Problem in Quadratic Number Fields

Vollmer, Ulrich (2004)
Rigorously Analyzed Algorithms for the Discrete Logarithm Problem in Quadratic Number Fields.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

URL / URN: urn:nbn:de:tuda-tuprints-4947

Kurzbeschreibung (Abstract)

The purpose of this thesis is to study the complexity of the discrete logarithm problem (DLP) and related problems in quadratic orders. The significance of these problems stems in large part from their application in quadratic number field cryptography (QNFC). QNFC was proposed by Buchmann and Williams [Buchmann/Williams, 1988], [Buchmann/Williams, 1990], and relies on the fact that the DLP in quadratic orders is hard. The question whether QNFC is secure at all, and the choice of cryptographically secure key-sizes, if it is, requires the study of the difficulty of the DLP. This thesis takes a rigorous theoretical approach to this question. In the case of the probabilistic algorithms the analysis relies on the well-established Generalized Riemann Hypothesis (GRH). Starting point for the proposed deterministic algorithms were the works of Shanks [Shanks, 1971], [Shanks, 1972] and the variant of Shanks' idea for general groups suggested by Terr [Terr, 2000]. We give a detailed analysis of the run-time of our algorithms and indicate apart from the square root of the regulator at which (minimzed) power the logarithm of the discriminant enters the run-time bound. Starting point for the proposed probabilistic algorithms were the work of Hafner and McCurley [Hafner/McCurley, 1989] for negative discriminants and of Buchmann [Buchmann, 1990] for positive ones. The heart of the presented approach lies in the restriction of the computations to essential data (in particular partial instead of full relation lattice and sparse bases) and the use of fast sub-algorithms. One of these sub-algorithms is a newly developed algorithm for the computation of the Hermite Normal Form (HNF) of an integer matrix in cubic time. In summary we obtain the currently fastest deterministic and probabilistic algorithms for the problems at hand, and gives a rigorous analysis of their properties. Thus we establish an upper bound for the complexity of the DLP.

Typ des Eintrags:

Dissertation

Erschienen:

2004

Autor(en):

Vollmer, Ulrich

Art des Eintrags:

Erstveröffentlichung

Titel:

Rigorously Analyzed Algorithms for the Discrete Logarithm Problem in Quadratic Number Fields

Sprache:

Englisch

Referenten:

Stevenhagen, Prof. Dr. Peter

Berater:

Buchmann, Prof. Dr. Johannes

Publikationsjahr:

27 Oktober 2004

Ort:

Darmstadt

Verlag:

Technische Universität

Datum der mündlichen Prüfung:

28 Oktober 2003

URL / URN:

urn:nbn:de:tuda-tuprints-4947

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

Das Ziel der vorliegenden Arbeit besteht in der Analyse der Komplexität des Diskreten-Logarithmus-Problems (DLP) und verwandter Probleme in quadratischen Ordnungen. Die Bedeutung dieser Probleme entspringt in erster Linie ihrer Anwendung für die Quadratische-Zahlkörper-Kryptographie (QNFC). QNFC wurde von Buchmann und Williams [Buchmann/Williams,1988], [Buchmann/Williams, 1990] vorgeschlagen und beruht auf der Annahme, daß das DLP in quadratischen Ordnungen schwer zu lösen ist. Wenn wir die Frage beantworten wollen, ob und ab welcher Schlüsselgröße QNFC sicher ist, müssen wir die Komplexität des DLP studieren. Diese Promotionsarbeit verfolgt einen rigorosen theoretischen Ansatz. Im Falle der probabilistischen Algorithmen legt die Analyse die wohlfundierte und weithin akzeptierte Verallgemeinerte Riemannsche Hypothese zugrunde. Ausgangspunkt für die vorgestellten deterministischen Algorithmen waren die Arbeiten von Shanks [Shanks,1971], [shanks,1972] und die Abwandlung der Shanksschen Idee für allgemeine Gruppen durch Terr [Terr, 2000]. Die Analyse der Laufzeit ist detailliert und weist neben der dominierenden Wurzel des Regulators die geringstmögliche Potenz aus, mit welcher der Logarithmus der Diskriminante in die Laufzeitschranke eingeht. Ausgangspunkt für die vorgestellten probabilistischen Algorithmen waren die Arbeit von Hafner und McCurley [Hafner/McCurley, 1989] für negative Diskriminanten und die Arbeit von Buchmann [Buchmann, 1990] für positive. Der Kern des verfolgten Ansatzes liegt in der Beschränkung der Berechnungen auf die essentiellen Daten (insbesondere partielle statt voller Relationengitter und beweisbar dünn besetzte Basen) und dem Einsatz schnellerer Teilalgorithmen. Ein solcher Teilagorithmus ist ein neu entwickelter Algorithmus für die Berechnung der Hermite-Normalform (HNF) einer ganzzahligen Matrix in kubischer Zeit. In der Konsequenz erhalten wir die derzeit schnellsten deterministischen und probabilistischen Algorithmen für die untersuchten Probleme und eine obere Schranke für die Komplexität des DLP.

Deutsch

Freie Schlagworte:

Quadratic number field, Cryptology, Probabilistic Algorithm, Deterministic algorithm, Discrete logarithm, Class group, Class number, Unit group, Regulator

Sachgruppe der Dewey Dezimalklassifikatin (DDC):

000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik

Fachbereich(e)/-gebiet(e):

20 Fachbereich Informatik

Hinterlegungsdatum:

17 Okt 2008 09:21

Letzte Änderung:

20 Mai 2018 21:23

PPN:

Referenten:

Stevenhagen, Prof. Dr. Peter

Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: