TU Darmstadt / ULB / TUprints

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
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
thesis.pdf
Copyright Information: In Copyright.

Download (820kB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Rigorously Analyzed Algorithms for the Discrete Logarithm Problem in Quadratic Number Fields
Language: English
Referees: Stevenhagen, Prof. Dr. Peter
Advisors: Buchmann, Prof. Dr. Johannes
Date: 27 October 2004
Place of Publication: Darmstadt
Date of oral examination: 28 October 2003
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.

Alternative Abstract:
Alternative AbstractLanguage

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.

German
Uncontrolled Keywords: Quadratic number field, Cryptology, Probabilistic Algorithm, Deterministic algorithm, Discrete logarithm, Class group, Class number, Unit group, Regulator
Alternative keywords:
Alternative keywordsLanguage
Quadratic number field, Cryptology, Probabilistic Algorithm, Deterministic algorithm, Discrete logarithm, Class group, Class number, Unit group, RegulatorEnglish
URN: urn:nbn:de:tuda-tuprints-4947
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 17 Oct 2008 09:21
Last Modified: 07 Dec 2012 11:50
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/494
PPN:
Export:
Actions (login required)
View Item View Item