TU Darmstadt / ULB / TUbiblio

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

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):

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.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

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: 28 Oktober 2003
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen