Mathematik
Refine
Year of publication
- 1997 (8) (remove)
Document Type
- diplomthesis (4)
- Doctoral Thesis (4)
Language
- German (8) (remove)
Has Fulltext
- yes (8) (remove)
Is part of the Bibliography
- no (8)
Keywords
- Cauchy-Anfangswertproblem (1)
- Dimension 2 (1)
- Dirichletsche L-Reihe; Nullstelle (1)
- Funktionenkörper ; Arithmetische Gruppe ; Auflösbare Gruppe ; Endlichkeit (1)
- Gitter <Mathematik> ; Basis <Mathematik> ; Reduktion ; Algorithmus ; Laufzeit ; L-unendlich-Norm ; Rucksackproblem ; Kryptosystem (1)
- Iteration (1)
- Laplace-Differentialgleichung (1)
Institute
- Mathematik (8)
Der Begriff der editierfreundlichen Kryptographie wurde von Mihir Bellare, Oded Goldreich und Shafi Goldwasser 1994 bzw. 1995 eingeführt. Mit einem editierfreundlicher Verschlüsselungs- oder Unterschriftenverfahren kann man aus einer Verschlüsselung bzw. Unterschrift zu einer Nachricht schnell eine Verschlüsselung oder Unterschrift zu einer ähnlichen Nachricht erstellen. Wir geben eine Übersicht über die bekannten editierfreundlichen Verfahren und entwickeln sowohl ein symmetrisches als auch ein asymmetrisches editierfreundliches Unterschriftenverfahren (IncXMACC und IncHSig). Wir zeigen, wie man mit editierfreundlichen Schemata überprüfen kann, ob die Implementierung einer Datenstruktur korrekt arbeitet. Basierend auf den Ideen der editierfreundlichen Kryptographie entwickeln wir effiziente Verfahren für spezielle Datenstrukturen. Diese Ergebnisse sind in zwei Arbeiten [F97a, F97b] zusammengefaßt worden.
In der vorliegenden Diplomarbeit beschäftigen wir uns mit kryptographisch sicheren Pseudozufallsgeneratoren. Diese e±zienten Algorithmen erzeugen zu zufälliger Eingabe deterministisch eine längere Bitfolge, die praktisch von einer Folge zufälliger Münzwürfe nicht unterscheidbar ist. Wir geben die Definitionen von A. Yao sowie M. Blum und S. Micali, beweisen die Äquivalenz und charakterisieren den Unterschied zur klassischen Sichtweise von Zufallsgeneratoren. Mit der Blum-Micali-Konstruktion zeigen wir, wie man aus einer Oneway-Permutation und zugehörigem Hardcore-Prädikat einen kryptographisch sicheren Pseudozufallsgenerator konstruiert: Man wendet auf einen zufälligen Startwert iterativ die Oneway-Funktion an und gibt jeweils das Hardcore-Prädikat des Urbilds aus. Wir stellen das allgemeine Hardcore- Prädikat inneres Produkt modulo 2 von L.A. Levin und O. Goldreich vor und beweisen mit Hilfe des XOR-Lemmas von U.V. Vazirani und V.V. Vazirani die Verallgemeinerung zu einer Hardcore-Funktion, die statt eines Prädikats mehrere Bits ausgibt. Man geht davon aus, daß die Verschlüsselungsfunktionen des RSA- und des Rabin-Public- Key-Kryptosystems Oneway-Permutationen sind. Basierend auf dem Rabin-System haben L. Blum, M. Blum und M. Shub den x2-mod-N-Generator aufgebaut, W. Alexi, B. Chor, O. Goldreich und C.P. Schnorr haben den RSA-Generator konstruiert und den Sicherheitsbeweis zum x2-mod-N-Generator verbessert. Diese Generatoren basieren auf der Blum-Micali-Konstruktion mit dem Hardcore-Prädikat des untersten Bits. Durch neue Ideen können wir die beweisbare Sicherheit der Generatoren deutlich erhöhen, so daß in der Praxis kleinere Schlüssellängen genügen. Bisher war zum Beispiel für den x2-mod-N-Generator bekannt, daß man mit einem Algorithmus A, der das unterste Bit der Wurzel modulo einer n-Bit- Blumzahl mit Wahrscheinlichkeit 1 2 + ² in Zeit |A| = ¡n3¢ berechnet, den Modul in Zeit O¡n3² 9|A|¢ mit Wahrscheinlichkeit ²2 64 faktorisieren kann. Wir verbessern die Laufzeit zu O¡n² 4 log2(n² 1)|A|¢ und Wahrscheinlichkeit 1 9 . Diese neuen Resultate wurden auf der Eurocrypt-Konferenz im Mai 1997 in Konstanz vorgestellt, D.E. Knuth hat sie bereits in die neue Auflage seines Standardwerks The Art of Computer Programming aufgenommen.
In der vorliegenden Arbeit untersuchen wir die Verteilung der Nullstellen Dirichletscher L-Reihen auf oder in der Nähe der kritischen Geraden. Diese Funktionen und ihre Nullstellen stehen im Mittelpunkt des Interesses bei einer Vielzahl klassischer zahlentheoretischer Fragestellungen; beispielsweise besagt die Verallgemeinerte Riemannsche Vermutung, daß sämtliche Nullstellen dieser Funktionen auf der kritischen Geraden liegen. Unsere Ergebnisse gehen unter anderem über die besten bislang bekannten Abschätzungen - für den Anteil der Nullstellen der Dirichletschen L-Reihen, die auf der kritischen Geraden liegen, - für den Anteil einfacher beziehungsweise m-facher Nullstellen sowie - über Nullstellen in der Nähe der kritischen Geraden hinaus. Wir setzen hiermit Arbeiten von A. Selberg, N. Levinson, J. B. Conrey und anderen fort und verallgemeinern Ergebnisse, die für die Riemannsche #-Funktion gültig sind, auf alle Dirichletschen LReihen beziehungsweise verbessern bisherige Resultate. Nach einer ausführlicheren Darstellung der Hintergründe zeigen wir einen Satz über Mittelwerte "geglätteter" L-Reihen, d.h. mit einem geeigneten Dirichlet-Polynom multiplizierte L-Reihen. Solche Mittelwertsätze stellen ein wesentliches Hilfsmittel zur Untersuchung der Nullstellenverteilung dar. Die in unserem Hauptsatz gegebene asymptotische Darstellung dieses Mittelwertes können wir dann nutzen, um die genannten Ergebnisse herzuleiten.