Mathematik
Refine
Year of publication
Document Type
- Article (110)
- Doctoral Thesis (76)
- Preprint (44)
- diplomthesis (39)
- Book (25)
- Report (22)
- Conference Proceeding (18)
- Bachelor Thesis (8)
- Contribution to a Periodical (8)
- Diploma Thesis (8)
Has Fulltext
- yes (370)
Is part of the Bibliography
- no (370)
Keywords
- Kongress (6)
- Kryptologie (5)
- Mathematik (5)
- Stochastik (5)
- Doku Mittelstufe (4)
- Doku Oberstufe (4)
- Online-Publikation (4)
- Statistik (4)
- Finanzmathematik (3)
- LLL-reduction (3)
Institute
- Mathematik (370)
- Informatik (55)
- Präsidium (22)
- Physik (7)
- Psychologie (6)
- Geschichtswissenschaften (5)
- Sportwissenschaften (5)
- Biochemie und Chemie (3)
- Biowissenschaften (3)
- Geographie (3)
Die zentrale Frage dieser Studie lautet: Wann ist eine stetige Funktion auf einem kompakten Raum, welche Werte in einem lokalkonvexen Raum annimmt, (Pettis-)integrierbar?
Im ersten Kapitel wird definiert, was konvexe Kompaktheit ist. Es wird das Pettis-Integral vorgestellt, und der Zusammenhang zwischen der konvexen Kompaktheitseigenschaft (oder ccp) und dem Pettis-Integral wird erläutert. Außerdem stellt dieses Kapitel dar, inwiefern die ccp aus stärkeren Eigenschaften lokalkonvexer Räume folgt oder schwächere impliziert. Das zweite Kapitel beweist hauptsächlich den Satz von Krein, der einen Zusammenhang zwischen Vollständigkeit unter der Mackey-Topologie und der ccp unter der schwachen Topologie herstellt. Das dritte Kapitel erläutert mit Gegenbeispielen, inwiefern die in Kapitel 1 vorgestellten Vollständigkeitseigenschaften lokalkonvexer Räume notwendig gegeneinander abgegrenzt sind. Das vierte Kapitel stellt zuerst das Bochner-Integral und das starke OperatorIntegral vor, um dann die starke konvexe Kompaktheitseigenschaft oder sccp einzufuhren, eine Eigenschaft, welche der ccp verwandt ist. Es wird fur einen Raum beispielhaft bewiesen, daß er diese Eigenschaft besitzt. Zuletzt wird der Zusammenhang von sccp und ccp ausfuhrlicher dargestellt.
Diese Arbeit wendet sich an Leser, denen die Grundlagen der Theorie lokalkonvexer Räume schon vertraut sind. Insbesondere ist Vertrautheit mit den Begriffen tonneliert, ultrabornologisch, bornologisch, polare Topologie unterstellt. Man findet eine kurze und einfach verständliche Einfuhrung im Werk [RR]. Alle über diese Grundlagen hinausgehenden Resultate werden in dieser Arbeit mit Beweis ausgefuhrt, oder es wird mit Angabe der Fundstelle auf die Literatur verwiesen.
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.
In this short note on my talk I want to point out the mathematical difficulties that arise in the study of the relation of Wightman and Euclidean quantum field theory, i.e., the relation between the hierarchies of Wightman and Schwinger functions. The two extreme cases where the reconstructed Wightman functions are either tempered distributions - the well-known Osterwalder-Schrader reconstruction - or modified Fourier hyperfunctions are discussed in some detail. Finally, some perpectives towards a classification of Euclidean reconstruction theorems are outlined and preliminary steps in that direction are presented.
Given a real vector alpha =(alpha1 ; : : : ; alpha d ) and a real number E > 0 a good Diophantine approximation to alpha is a number Q such that IIQ alpha mod Zk1 ", where k \Delta k1 denotes the 1-norm kxk1 := max 1id jx i j for x = (x1 ; : : : ; xd ). Lagarias [12] proved the NP-completeness of the corresponding decision problem, i.e., given a vector ff 2 Q d , a rational number " ? 0 and a number N 2 N+ , decide whether there exists a number Q with 1 Q N and kQff mod Zk1 ". We prove that, unless ...
We address to the problem to factor a large composite number by lattice reduction algorithms. Schnorr has shown that under a reasonable number theoretic assumptions this problem can be reduced to a simultaneous diophantine approximation problem. The latter in turn can be solved by finding sufficiently many l_1--short vectors in a suitably defined lattice. Using lattice basis reduction algorithms Schnorr and Euchner applied Schnorrs reduction technique to 40--bit long integers. Their implementation needed several hours to compute a 5% fraction of the solution, i.e., 6 out of 125 congruences which are necessary to factorize the composite. In this report we describe a more efficient implementation using stronger lattice basis reduction techniques incorporating ideas of Schnorr, Hoerner and Ritter. For 60--bit long integers our algorithm yields a complete factorization in less than 3 hours.
We introduce the relationship between incremental cryptography and memory checkers. We present an incremental message authentication scheme based on the XOR MACs which supports insertion, deletion and other single block operations. Our scheme takes only a constant number of pseudorandom function evaluations for each update step and produces smaller authentication codes than the tree scheme presented in [BGG95]. Furthermore, it is secure against message substitution attacks, where the adversary is allowed to tamper messages before update steps, making it applicable to virus protection. From this scheme we derive memory checkers for data structures based on lists. Conversely, we use a lower bound for memory checkers to show that so-called message substitution detecting schemes produce signatures or authentication codes with size proportional to the message length.
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.
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.
We show lower bounds for the signature size of incremental schemes which are secure against substitution attacks and support single block replacement. We prove that for documents of n blocks such schemes produce signatures of \Omega(n^(1/(2+c))) bits for any constant c>0. For schemes accessing only a single block resp. a constant number of blocks for each replacement this bound can be raised to \Omega(n) resp. \Omega(sqrt(n)). Additionally, we show that our technique yields a new lower bound for memory checkers.
A memory checker for a data structure provides a method to check that the output of the data structure operations is consistent with the input even if the data is stored on some insecure medium. In [8] we present a general solution for all data structures that are based on insert(i,v) and delete(j) commands. In particular this includes stacks, queues, deques (double-ended queues) and lists. Here, we describe more time and space efficient solutions for stacks, queues and deques. Each algorithm takes only a single function evaluation of a pseudorandomlike function like DES or a collision-free hash function like MD5 or SHA for each push/pop resp. enqueue/dequeue command making our methods applicable to smart cards.
Gitter sind diskrete, additive Untergruppen des IRm, ein linear unabhängiges Erzeugendensystem eines Gitters heißt Gitterbasis. Die Anzahl der Basisvektoren eines Gitters ist eindeutig bestimmt und heißt Rang des Gitters. Zu jedem Gitter vom Rang n gibt es mehrere Gitterbasen, die man alle erhält, indem man eine Basismatrix B = [b1, · · · , bn] von rechts mit allen Matrizen aus der Gruppe GLn(ZZ) multipliziert. Eine wichtige Fragestellung der Gittertheorie ist es, zu einem gegebenen Gitter einen kürzesten, vom Nullvektor verschiedenen Gittervektor zu finden. Dieses Problem heißt das kürzeste Gittervektorproblem . Ein dazu verwandtes Problem ist das "nächste Gittervektorproblem", das zu einem beliebigen Vektor x aus IRm einen Gittervektor sucht, dessen Abstand zu x minimal ist. Aus dem "kürzesten Gittervektorproblem" entwickelte sich die Gitterbasenreduktion, deren Ziel es ist, eine gegebene Gitterbasis in eine Gitterbasis zu transformieren, deren Vektoren bzgl. der Euklidischen Norm kurz und möglichst orthogonal zueinander sind. Wichtig für die Güte einer Reduktion ist der Begriff der sukzessiven Minima ¸1(L), · · · , ¸n(L) eines Gitters L. Dabei ist ¸i(L) die kleinste reelle Zahl r > 0, für die es i linear unabhängige Vektoren cj 2 L gibt mit kcjk · r für j = 1, · · · , i. Man versucht, für ein Gitter L eine Gitterbasis b1, · · · , bn zu finden, bei der die Größe kbik / ¸i(L) für i = 1, · · · , n möglichst klein ist. Für Gitter vom Rang 2 liefert das Gauß'sche Reduktionsverfahren eine Gitterbasis mit kbik = ¸i(L) für i = 1, 2. Eine Verallgemeinerung der Gauß-Reduktion auf Gitter mit beliebigem Rang ist die im Jahre 1982 von Lenstra, Lenstra, Lovasz vorgeschlagene L3-Reduktion einer Gitterbasis, deren Laufzeit polynomiell in der Bitlänge der Eingabe ist. L3-reduzierte Gitterbasen approximieren die sukzessiven Minima bis auf einen (im Rang des Gitters) exponentiellen Faktor. Die vorliegende Arbeit besteht aus zwei Teilen. Im ersten Teil (Kapitel 1-6) wird ein neues Reduktionskonzept von M. Seysen aus der Arbeit "A Measure for the Non-Orthogonality of a Lattice Basis" behandelt und im zweiten Teil (Kapitel 7) ein aktuelles Ergebnis von M. Ajtai über die Faktorisierung ganzer Zahlen aus "The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions"[2]. Seysen führte in [13] zu einer gegebenen Gitterbasis b1, · · · , bn die Größe ¾(A) ein, die nur von den Einträgen der zugehörigen Gram-Matrix A = [b1, · · · , bn]T · [b1, · · · , bn] und der Inversen A 1 abhängt. Sie hat die Eigenschaft, daß für jede Gitterbasis b1, · · · , bn mit Gram-Matrix A gilt, daß ¾(A) ¸ 1, wobei die Gleichheit genau dann gilt, wenn b1, · · · , bn orthogonal ist. Aus dieser Defintion ergibt sich folgender Reduktionsbegriff: Eine Gitterbasis b1, · · · , bn mit Gram-Matrix A heißt genau dann ¿ -reduziert, wenn ¾(A) minimal für alle Basen des Gitters ist. Der wesentliche Unterschied der ¿-Reduktion zur L3-Reduktion ist, daß die Größe ¾(A) unabhängig von der Reihenfolge der Basisvektoren ist, so daß eine ¿ -reduzierte Gitterbasis bei beliebiger Permutation der Basisvektoren ¿ -reduziert bleibt. Die ¿-Reduktion reduziert also im Gegensatz zur L3-Reduktion die Basisvektoren gleichmäßig. Seysen zeigte, daß man zu jedem Gitter vom Rang n eine Gitterbasis mit Gram-Matrix A findet, so daß ¾(A) durch eO((ln n)2) beschränkt ist. Daraus läßt sich ableiten, daß ¿ -reduzierte Gitterbasen eines Gitters vom Rang n die sukzessiven Minima bis auf den Faktor eO((ln n)2) approximieren. Da es sich bei der ¿-Reduktion um einen sehr starken Reduktionsbegriff handelt, für den es schwer ist, einen effizienten Algorithmus zu finden, definiert man folgenden schwächeren Reduktionsbegriff: b1, · · · , bn heißt genau dann ¿2-reduziert, wenn keine Basistransformation der Form bj := bj +k · bi mit 1 · i 6= j · n und k 2 ZZ die Gr¨oße ¾(A) erniedrigt. Für n = 2 entspricht die ¿-Reduktion sowohl der ¿2- Reduktion als auch der Gauß-Reduktion. Für die ¿2-Reduktion findet man einen effizienten Algorithmus. Wendet man diesen Algorithmus auf Rucksackprobleme an, so ergibt sich, daß durch einen Algorithmus, bestehend aus ¿2-Reduktion und anschließender L3-Reduktion, bei großer Dichte und bei kleiner Dimension wesentlich mehr Rucksackprobleme gelöst werden als durch den L3-Algorithmus. Die Faktorisierung großer ganzer Zahlen ist ein fundamentales Problem mit großer kryptographischer Bedeutung. Schnorr stellte in [11] erstmals einen Zusammenhang zwischen Gitterbasenreduktion und Faktorisierung her, indem er das Faktorisieren ganzer Zahlen auf das "nächste Gittervektorproblem in der Eins-Norm" zurückführte. Adleman führte in [1] das Faktorisieren ganzer Zahlen sogar auf das "kürzeste Gittervektorproblem in der Euklidischen Norm" zurück, allerdings unter zahlentheoretischen Annahmen. In [2] stellte Ajtai ein neues Ergebnis vor, in dem er das Faktorisieren ganzer Zahlen auf das "kürzeste Gittervektorproblem in der Euklidischen Norm" ohne zusätzliche Annahmen zurückführte.
Epstein and Penner constructed in [EP88] the Euclidean decomposition of a non-compact hyperbolic n-manifold of finite volume for a choice of cusps, n >= 2. The manifold is cut along geodesic hyperplanes into hyperbolic ideal convex polyhedra. The intersection of the cusps with the Euclidean decomposition determined by them turns out to be rather simple as stated in Theorem 2.2. A dual decomposition resulting from the expansion of the cusps was already mentioned in [EP88]. These two dual hyperbolic decompositions of the manifold induce two dual decompositions in the Euclidean structure of the cusp sections. This observation leads in Theorems 5.1 and 5.2 to easily computable, necessary conditions for an arbitrary ideal polyhedral decomposition of the manifold to be a Euclidean decomposition.
Euklidische Zerlegungen nicht-kompakter hyperbolischer Mannigfaltigkeiten mit endlichem Volumen
(1998)
Epstein and Penner constructed in [EP88] the Euclidean decomposition of a non-compact hyperbolic n-manifold of finite volume for a choice of cusps, n >= 2. The manifold is cut along geodesic hyperplanes into hyperbolic ideal convex polyhedra. The intersection of the cusps with the Euclidean decomposition determined by them turns out to be rather simple as stated in Theorem 2.2. A dual decomposition resulting from the expansion of the cusps was already mentioned in [EP88]. These two dual hyperbolic decompositions of the manifold induce two dual decompositions in the Euclidean structure of the cusp sections. This observation leads in Theorems 5.1 and 5.2 to easily computable, necessary conditions for an arbitrary ideal polyhedral decomposition of the manifold to be a Euclidean decomposition.
Die Vorstellung, daß ein Quantensystem zu jedem Zeitpunkt einen bestimmten Zustand (aus einem "klassischen" Phasenraum) einnimmt, ist im Formalismus der Quantenmechanik nicht vorgesehen. Man kann eine solche Vorstellung zwar verträglich mit den Regeln der QM unterhalten, jedoch erweisen sich dann ganz verschiedene Wahrscheinlichkeitsverteilungen auf dem Phasenraum als experimentell ununterscheidbar; solche Modelle postulieren sozusagen die Existenz einer "verborgenenen Information" neben den prüfbaren Fakten. Es wird gezeigt, daß dies für alle Modelle gilt, die mit den von der QM für jede Observable vorhergesagten Wahrscheinlichkeitsverteilung im Einklang stehen, selbst wenn sie erlauben, daß nicht jede Verteilung auf dem Phasenraum durch makroskopische Aparaturen präpariert werden kann bzw. daß das Meßergebnis garnicht deterministisch vom Zustand des Quantensystems abhängt, sondern das Meßgerät selbst einem (vom zu messenden System unabhängigen) Zufall unterliegt. Dazu ist eine gründliche Auseinandersetzung mit der Theorie der Wahrscheinlichkeitsmaße auf distributiven und auf nicht-distributiven Verbänden nötig.
Über die Anzahlfunktion π(x)
(1999)
Bereits Euklid wusste, dass es unendlich viele Primzahlen gibt. Euler zeigte die qualitative Aussage ¼(x) x ! 0 bei x ! 1. Legendre definierte als erster die Anzahlfunktion ¼(x) als die Anzahl aller Primzahlen · x, (x 2 R) und vermutete irrtümlicherweise, dass ¼(x) = x log(x)¡B; wobei lim x!1 B(x) = 1; 083 66 : : : ist. Gauss vermutete, dass die Funktionen ¼(x) und li(x) := lim "!0 ">0 0@ u=1¡" Z u=0 du log(u) + u=x Z u=1+" du log(u)1A asymptotisch Äquivalent sind. Tschebyschew konnte die Legendresche Vermutung widerlegen; außerdem bewies er: Wenn der Grenzwert lim x!1 ¼(x) x log(x) existiert, so muss dieser gleich 1 sein. Dank wegweisender Vorarbeiten von Riemann, gelang es im Jahr 1896 unabhängig voneinander und nahezu zeitgleich Hadamard und De La Vallee Poussin, den Primzahlsatz analytisch zu beweisen. Beide verwendeten entscheidend die Tatsache, dass die Zetafunktion ³ in der Halbebene Re(s) ¸ 1 nicht verschwindet. Die Beweise waren zuerst so lang und kompliziert, dass sie heutzutage nur noch einen historischen Wert besitzen. Es dauerte weitere 84 Jahre bis der Beweis so vereinfacht werden konnte, dass er nur wenige Seiten in Anspruch nimmt. Ein wichtiger Verdienst kommt hierbei der Arbeit von Newman aus dem Jahre 1980 zu. Lange Zeit wurde es für kaum möglich gehalten, einen Beweis des Primzahlsatzes zu finden, der ohne eine gewisse Kenntnis der komplexen Nullstellen der Zetafunktion auskommt. Und doch glückte 1948 ein solcher Beweis durch Selberg und Erdös mit elementaren Mitteln. Erwähnenswert dabei, dass der Beweis noch lange nicht einfach ist. Uns schienen die analytischen Beweise durchsichtiger zu sein. Daher haben wir in dieser Arbeit auf einen elementaren Beweis verzichtet. Der analytischen Weg zum Primzahlsatz von Newman kommt einerseits mit Integration längs endlicher Wege (und der Tatsache ³(s) 6= 0 in ¾ ¸ 1) aus, umgeht also Abschätzungen bei 1; andererseits ist er frei von Sätzen der Fourier-Analysis. Beim Beweis des Primzahlsatzes von Wolke benutzt man anstelle von ³0(s) ³(s) die Funktion ³ 1 k mit großen k. Wegen des Pols bei s=1 bringt dies bei der Integration leichte Komplikationen, hat aber den Vorteil, dass außer der Nullstellen-Freiheit keine nichttriviale Abschätzung für ³ oder ³0 erforderlich ist. Dank der elementaren Äquivalenz zwischen dem Primzahlsatz und der Konvergenz von 1Pn=1 ¹(n) n brauchte Newman nur die Konvergenz von 1Pn=1 ¹(n) n zu zeigen. Dies erreichte er mit Hilfe seines Konvergenzsatzes. Die Legendresche Formel, die auf dem Sieb des Eratosthenes basiert, erlaubt die exakte Berechnung von ¼(x), wenn alle px nicht übersteigenden Primzahlen bekannt sind. Diese prinzipielle Möglichkeit zur Ermittlung von ¼(x) ist in der Praxis natürlich stark limitiert durch die mit x rasch anwachsende Anzahl der rechts in der Legendresche Formel zu berücksichtigenden Summanden. Mit verfeinerten Siebtechniken haben verschiedene Autoren zur Legendresche Formel analoge Formeln ¼(x) ersonnen, bei denen der genannte Nachteil von Legendresche Formel sukzessive reduziert wurde. Zu erwähnen sind hier vor allem Meissel, Lehmer, sowie Lagarias, Miller und Odlyzko. Aus den Graphen von R(x)¡¼(x); li(x)¡¼(x) und x log(x) ¡¼(x) für den betrachteten Bereich x · 1018 konnten wir feststellen, dass R(x); li(x) sowie x log(x) die Anzahlfunktion Pi (x) annähern, wobei R(x) die beste Approximation für Pi(x) von allen drei ist.
Let G be a finite cyclic group with generator \alpha and with an encoding so that multiplication is computable in polynomial time. We study the security of bits of the discrete log x when given \exp_{\alpha}(x), assuming that the exponentiation function \exp_{\alpha}(x) = \alpha^x is one-way. We reduce he general problem to the case that G has odd order q. If G has odd order q the security of the least-significant bits of x and of the most significant bits of the rational number \frac{x}{q} \in [0,1) follows from the work of Peralta [P85] and Long and Wigderson [LW88]. We generalize these bits and study the security of consecutive shift bits lsb(2^{-i}x mod q) for i=k+1,...,k+j. When we restrict \exp_{\alpha} to arguments x such that some sequence of j consecutive shift bits of x is constant (i.e., not depending on x) we call it a 2^{-j}-fraction of \exp_{\alpha}. For groups of odd group order q we show that every two 2^{-j}-fractions of \exp_{\alpha} are equally one-way by a polynomial time transformation: Either they are all one-way or none of them. Our key theorem shows that arbitrary j consecutive shift bits of x are simultaneously secure when given \exp_{\alpha}(x) iff the 2^{-j}-fractions of \exp_{\alpha} are one-way. In particular this applies to the j least-significant bits of x and to the j most-significant bits of \frac{x}{q} \in [0,1). For one-way \exp_{\alpha} the individual bits of x are secure when given \exp_{\alpha}(x) by the method of Hastad, N\"aslund [HN98]. For groups of even order 2^{s}q we show that the j least-significant bits of \lfloor x/2^s\rfloor, as well as the j most-significant bits of \frac{x}{q} \in [0,1), are simultaneously secure iff the 2^{-j}-fractions of \exp_{\alpha'} are one-way for \alpha' := \alpha^{2^s}. We use and extend the models of generic algorithms of Nechaev (1994) and Shoup (1997). We determine the generic complexity of inverting fractions of \exp_{\alpha} for the case that \alpha has prime order q. As a consequence, arbitrary segments of (1-\varepsilon)\lg q consecutive shift bits of random x are for constant \varepsilon >0 simultaneously secure against generic attacks. Every generic algorithm using $t$ generic steps (group operations) for distinguishing bit strings of j consecutive shift bits of x from random bit strings has at most advantage O((\lg q) j\sqrt{t} (2^j/q)^{\frac14}).
We introduce novel security proofs that use combinatorial counting arguments rather than reductions to the discrete logarithm or to the Diffie-Hellman problem. Our security results are sharp and clean with no polynomial reduction times involved. We consider a combination of the random oracle model and the generic model. This corresponds to assuming an ideal hash function H given by an oracle and an ideal group of prime order q, where the binary encoding of the group elements is useless for cryptographic attacks In this model, we first show that Schnorr signatures are secure against the one-more signature forgery : A generic adversary performing t generic steps including l sequential interactions with the signer cannot produce l+1 signatures with a better probability than (t 2)/q. We also characterize the different power of sequential and of parallel attacks. Secondly, we prove signed ElGamal encryption is secure against the adaptive chosen ciphertext attack, in which an attacker can arbitrarily use a decryption oracle except for the challenge ciphertext. Moreover, signed ElGamal encryption is secure against the one-more decryption attack: A generic adversary performing t generic steps including l interactions with the decryption oracle cannot distinguish the plaintexts of l + 1 ciphertexts from random strings with a probability exceeding (t 2)/q.
Pseudorandom function tribe ensembles based on one-way permutations: improvements and applications
(1999)
Pseudorandom function tribe ensembles are pseudorandom function ensembles that have an additional collision resistance property: almost all functions have disjoint ranges. We present an alternative to the construction of pseudorandom function tribe ensembles based on oneway permutations given by Canetti, Micciancio and Reingold [CMR98]. Our approach yields two different but related solutions: One construction is somewhat theoretic, but conceptually simple and therefore gives an easier proof that one-way permutations suffice to construct pseudorandom function tribe ensembles. The other, slightly more complicated solution provides a practical construction; it starts with an arbitrary pseudorandom function ensemble and assimilates the one-way permutation to this ensemble. Therefore, the second solution inherits important characteristics of the underlying pseudorandom function ensemble: it is almost as effcient and if the starting pseudorandom function ensemble is efficiently invertible (given the secret key) then so is the derived tribe ensemble. We also show that the latter solution yields so-called committing private-key encryption schemes. i.e., where each ciphertext corresponds to exactly one plaintext independently of the choice of the secret key or the random bits used in the encryption process.
We consider catalytic branching random walk (the reactant) where the state space is a countable Abelean group. The branching is critical binary and the local branching rate is given by a catalytic medium. Here the medium is itself an autonomous (ordinary) branching random walk (the catalyst) - maybe with a different motion law. For persistent catalyst (transient motion) the reactant shows the usual dichotomy of persistence versus extinction depending on transience or recurrence of its motion. If the catalyst goes to local extinction it turns out that the longtime behaviour of the reactant ranges (depending on its motion) from local extinction to free random walk with either deterministic or random global intensity of particles.
Statistical analysis on various stocks reveals long range dependence behavior of the stock prices that is not consistent with the classical Black and Scholes model. This memory or nondeterministic trend behavior is often seen as a reflection of market sentiments and causes that the historical volatility estimator becomes unreliable in practice. We propose an extension of the Black and Scholes model by adding a term to the original Wiener term involving a smoother process which accounts for these effects. The problem of arbitrage will be discussed. Using a generalized stochastic integration theory [8], we show that it is possible to construct a self financing replicating portfolio for a European option without any further knowledge of the extension and that, as a consequence, the classical concept of volatility needs to be re-interpreted.
AMS subject classifications: 60H05, 60H10, 90A09.
Integral equations for the mean-square estimate are obtained for the linear filtering problem, in which the noise generating the signal is a fractional Brownian motion with Hurst index h∈(3/4,1) and the noise in the observation process includes a fractional Brownian motion as well as a Wiener process. AMS subject classifications: 93E11, 60G20, 60G35.
In der vorliegenden Arbeit wird ein interaktives Beweisprotokoll für das Problem der "überprüfbaren Verschlüsselung" (verifiable encyption) vorgestellt. Mit Hilfe eines Verifiable Encryption Protokolls (VEP) beweist eine Person (der Prover) einer anderen Person (dem Verifier) effizient, daß ein vorher gesendeter Wert alpha die Verschlüsselung eines geheimen Wertes s ist. Den geheimen Wert s muß er dazu nicht offenlegen. Zur Verschlüsselung von s wird ein Public-Key-Verfahren und ein öffentlicher Schlüssel PK benutzt. PK gehört zum Schlüsselpaar einer dritten Partei, die nicht aktiv an der Protokollausführung beteiligt ist und die Rolle eines Notars einnimmt. Dem Verifier steht ein Wert d zur Verfügung, anhand dessen er entscheidet, ob er den Beweis akzeptiert oder verwirft. Akzeptiert der Verifier den Beweis des Provers, so kann er zwar mit an Sicherheit grenzender Wahrscheinlichkeit sagen, daß alpha eine Verschlüsselung von s unter dem öffentlichen Schlüssel PK ist. Er kann s jedoch nicht rekonstruieren, da er nicht im Besitz des zu PK gehörigen geheimen Schlüssels SK ist und der Beweis keine Informationen über s preisgibt.
Wir werden uns in dieser Arbeit vorwiegend mit einem Modell befassen, das Y. Peres, C. Kenyon, W. Evans und L.J. Schulman 1998 in ihrem Artikel \Broadcasting on trees and the Ising-Modell" eingeführt haben.
In diesem Modell wird ein Signal, das die Werte +1 oder -1 annehmen kann, von der Wurzel eines Baumes aus entlang der Äste eines unendlichgroßen Baumes übertragen. Die Kanten des Baumes agieren dabei als Übertragungskanäle zwischen den Knoten. Jede Kante kann das Signal korrekt übertragen oder es flippen, das heißt, das Vorzeichen des Signals umkehren.
Das Übertragungsverhalten der Kanten ist zufällig. Mit einer festen Wahrscheinlichkeit ϵ, mit 0 < ϵ <= 1/2 , verfälscht eine Kante das Signal. Dies geschieht an allen Kanten unabhängig mit der gleichen Wahrscheinlichkeit. Es stellt sich nun die Frage, wie groß diese Fehlerwahrscheinlichkeit höchstens sein darf, damit das, was in der Krone des Baumes ankommt, noch etwas zu tun hat mit dem, was in der Wurzel eingespeist wird. Mit anderen Worte: Sind die Signale auf Knoten, die einen Abstand >= n von der Wurzel haben, für n -> ∞ asymptotisch unabhängig vom Signal in der Wurzel? Eine Möglichkeit, den Grad der Abhängigkeit zu messen, ist die sogenannte Information, der Kullback-Leibler-Abstand von gemeinsamer Verteilung zur Produkt-Verteilung, die in Definition 16 eingeführt wird.
Wir werden sehen, daß es eine kritische Schwelle ϵc;I für Informationsübertragung gibt. Ist die Fehlerwahrscheinlichkeit größer als ϵc;I , so ist die Information, die zwischen Wurzel und Krone übertragen wird, 0. Ist die Fehlerwahrscheinlichkeit kleiner als ϵc;I , so wird Information übertragen. Dieser kritische Wert ϵc;I hängt nur von der Branching-Number, einer Art mittleren Verzweigungszahl, des Baumes (vgl. Definition 1) ab.
Wir werden sehen, daß das Broadcasting-Modell eine elegante Formulierung eines wohlbekannten Modells, des Ising-Modells, mit freien Randbedingungen, ist.
Im Ising-Modell hat jeder Knoten des Baumes einen "magnetischen" Spin, der entweder +1 oder -1 sein kann. Spins direkt benachbarter Knoten beeinflussen sich, in dem sie versuchen, den gleichen Wert anzunehmen. Diesem Effekt wirkt ein thermischer Einfluß entgegen, der mittels eines als Temperatur bezeichneten Parameters modelliert wird.
Die klassische Frage im Ising-Modell ist, ob Phasenübergang stattfindet. Wir wollen Phasenübergang als das Phänomen verstehen, daß die Wurzel des Baumes die Vorgabe von Randbedingungen auf der Krone des Baumes spürt. Ist dies der Fall, so sagen wir, daß Phasenübergang stattfindet. Auch dies ist eine
Form der gegenseitigen Beeinflussung zwischen Wurzel und Krone des Baumes. Russel Lyons hat 1989 in seinem Artikel \The Ising-Model on trees and treelike Graphs" das Ising-Modell auf Bäumen untersucht und gezeigt, daß es eine kritische Temperatur tc für Phasenübergang gibt. Ist die Temperatur höher als tc, so spürt die Wurzel nichts von den Randbedingungen der Krone; ist die Temperatur geringer als tc, so haben die Randbedingungen Einfluß auf die Wurzel. Auch hier hängt die kritische Temperatur nur von der Branching-Number des Baumes ab.
In der Broadcasting-Formulierung des Modells ist der Fluß von Information ein naheliegendes Werkzeug, um die Beeinflussung von Wurzel und Krone zu messen, in der Ising-Formulierung ist die Existenz von Phasenübergang ein ebenso naheliegendes Werkzeug, ebendiesen Einfluß zu messen.
Wir werden die beiden Arten der Beeinflussung miteinander vergleichen und können zeigen, daß für die Übertragung von Information stets eine stärkere Interaktion zwischen den Knoten notwendig ist, als für den Einfluß der Randbedingungen aus der Krone.
Als letztes Phänomen werden wir untersuchen, ob es einen Pfad im Baum gibt, der in der Wurzel startend nur Knoten gleichen Spins besucht und die unendlich weit entfernte Krone erreicht. Wir bezeichnen dieses Phänomen als Spinperkolation.
Wir werden die Berechnung der kritischen Interaktion für Spinperkolation in einem Bernoulli-Feld auf den Kanten rekapitulieren und dann zeigen, daß die Existenz eines Perkolationspfades nur von der Interaktionsstärke des Modells und nicht von etwaigen Randbedingungen abhängt. Dabei kombinieren wir Ergebnisse aus zwei Arbeiten von Lyons und die Erkenntnis, daß Broadcasting- Modell und freies Ising-Modell identisch sind. Wir erhalten so einen neuen, einfachen Beweis über die kritische Interaktion für Spinperkolation in der Plus-Phase des Ising-Modells, die Lyons bereits in [7] berechnet hat.
New conditions of solvability based on a general theorem on the calculation of the index at infinity for vector fields that have degenerate principal linear part as well as degenerate ... next order ... terms are obtained for the 2 Pi-periodic problem for the scalar equation x'' +n2x=g(|x|)+f(t,x)+b(t) with bounded g(u) and f(t,x) -> 0 as |x| -> 0. The result is also applied to the solvability of a two-point boundary value problem and to resonant problems for equations arising in control theory.
AMS subject classifications: 47Hll, 47H30.
Assuming a cryptographically strong cyclic group G of prime order q and a random hash function H, we show that ElGamal encryption with an added Schnorr signature is secure against the adaptive chosen ciphertext attack, in which an attacker can freely use a decryption oracle except for the target ciphertext. We also prove security against the novel one-more-decyption attack. Our security proofs are in a new model, corresponding to a combination of two previously introduced models, the Random Oracle model and the Generic model. The security extends to the distributed threshold version of the scheme. Moreover, we propose a very practical scheme for private information retrieval that is based on blind decryption of ElGamal ciphertexts.
Let G be a group of prime order q with generator g. We study hardcore subsets H is include in G of the discrete logarithm (DL) log g in the model of generic algorithms. In this model we count group operations such as multiplication, division while computations with non-group data are for free. It is known from Nechaev (1994) and Shoup (1997) that generic DL-algorithms for the entire group G must perform p2q generic steps. We show that DL-algorithms for small subsets H is include in G require m/ 2 + o(m) generic steps for almost all H of size #H = m with m <= sqrt(q). Conversely, m/2 + 1 generic steps are su±cient for all H is include in G of even size m. Our main result justifies to generate secret DL-keys from seeds that are only 1/2 * log2 q bits long.
Es steht außer Zweifel, daß digitale Signaturen schon bald zu unserem Alltag gehören wer- den. Spätestens mit dem Inkrafttreten des Gesetzes zur digitalen Signatur (siehe [BMB]) sind sie zu einem wichtigen Instrument in der Telekommunikation geworden. Dabei kommt der Verwendung von Chipkarten eine wichtige Bedeutung zu: In ihnen lassen sich die sensiblen Daten (z.B. der geheime Schlüssel) auslesesicher aufbewahren; gleichzeitig können sie bequem mitgeführt werden. Aus diesen Gründen erlebt die Verwendung von Chipkarten zur Erzeugung von digitalen Signaturen zur Zeit einen enormen Aufschwung. Problematisch ist jedoch der oft unverhältnismäßig große Berechnungsaufwand für die Erzeugung von digitalen Signaturen. Ziel dieser Arbeit ist es, Methoden zu entwickeln und/oder zu untersuchen, welche die Berechnung digitaler Unterschriften wesentlich beschleunigen. Dabei spiegelt sich die Zweiteilung der in der Praxis hauptsächlich verwendeten Typen von Signaturverfahren in der Struktur der Arbeit wider. Der erste Teil dieser Arbeit untersucht Verfahren zur effizienten Berechnung von RSA-Unterschriften. Dabei entstanden die Untersuchungen in den Abschnitten 3.2.3 und 3.2.4 in Zusammenarbeit mit R. Werchner und der Inhalt der Abschnitte 3.1 - 3.2.4 ist bereits in [MW98] veröffentlicht. Im zweiten Teil entwickeln wir Verfahren zur effizienteren Generierung von Unterschriften, die auf dem diskreten Logarithmus basieren, und untersuchen deren Sicherheit. Dabei entstanden die Untersuchungen in den Abschnitten 4.2 (bis auf 4.2.2) und 4.3.1 in Zusammenarbeit mit C. P. Schnorr und sind teilweise in [MS98] zusammengefaßt. Obwohl diese Arbeit eine mathematische Abhandlung darstellt, versuchen wir, die praktische Anwendung nicht aus den Augen zu verlieren. So orientieren sich die betrachteten Verfahren stets an den durch die verfügbare Technologie gegebenen Rahmenbedingungen. Darüber hinaus richten wir unser Augenmerk weniger auf das asymptotische Verhalten der betrachteten Verfahren, als vielmehr auf konkrete, für die Anwendung relevante Beispiele.
In this paper, a translation of the visual description technique HyCharts to Hybrid Data-Flow Graphs (HDFG) is given. While HyCharts combine a data-flow and a control-flow oriented formalism for the specification of the architecture and the behavior of hybrid systems, HDFG allow the efficient and homogeneous internal representation of hybrid systems in computers and their automatic manipulation. HDFG represent a system as a data-flow network built from a set of fundamental functions.
The translation permits to combine the advantages of the different description techniques: The use of HyCharts for specification supports the abstract and formal interactive specification of hybrid systems, while HDFG permit the tool based optimization of hybrid systems and the synthesis of mixed-signal prototypes.
We present efficient non-malleable commitment schemes based on standard assumptions such as RSA and Discrete-Log, and under the condition that the network provides publicly available RSA or Discrete-Log parameters generated by a trusted party. Our protocols require only three rounds and a few modular exponentiations. We also discuss the difference between the notion of non-malleable commitment schemes used by Dolev, Dwork and Naor [DDN00] and the one given by Di Crescenzo, Ishai and Ostrovsky [DIO98].
Gitter
(2000)
Komplexität von Gitterproblemen : Nicht-Approximierbarkeit und Grenzen der Nicht-Approximierbarkeit
(2000)
Ein Gitter vom Rang n ist die Menge der ganzzahligen Linerkombinationen von n linear unabhängigen Vektoren im Rm. Unter der Annahme P <> NP beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der eine kürzeste Gitterbasis bis auf einen Faktor nO exp(1/log log n) berechnet, wobei die Länge einer Menge von Vektoren durch die maximale Euklidische Länge der Vektoren definiert ist. Weiter zeigen wir, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n/ sqrt(log n) unter plausiblen Annahmen nicht möglich ist. Ein simultaner Diophantischer Best Approximations Nenner für reelle Zahlen alpha1, .... , alpha n und Hauptnennerschranke N ist eine natürliche Zahl q mit 1 <= q >= N, so daß maxi minp2Z |q alpha i - p| minimal ist. Unter der Annahme, daß die Klasse NP keine fast-polynomiellen Algorithmen besitzt, beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der für gegebene rationale Zahlen. Ein Gitter vom Rang n ist die Menge der ganzzahligen Linerkombinationen von n linear unabhängigen Vektoren im Rm. Unter der Annahme P 6= NP beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der eine kürzeste Gitterbasis bis auf einen Faktor nO(1= log log n) berechnet, wobei die Länge einer Menge von Vektoren durch die maximale Euklidische Länge der Vektoren definiert ist. Weiter zeigen wir, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n=plog n unter plausiblen Annahmen nicht möglich ist. Ein simultaner Diophantischer Best Approximations Nenner für reelle Zahlen alpha1, .... , alpha n und Hauptnennerschranke N ist eine natürliche Zahl q mit 1 <= q <= N, so daß maxi ...... minimal ist. Unter der Annahme, daß die Klasse NP keine fast-polynomiellen Algorithmen besitzt, beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der für gegebene rationale Zahlen alpha1,......, alphan und eine Hauptnennerschranke N einen Nenner ~q mit 1 <= ~q <= f(n)N berechnet, so daß ~q bis auf einen Faktor f(n) = nO(1= log0:5+epsilon n) ein Best Approximations Nenner ist, wobei epsilon > 0 eine beliebige Konstante ist. Wir zeigen, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n=log n unter plausiblen Annahmen nicht mölich ist. Wir untersuchen die Konsequenzen dieser Resultate zur Konstruktion von im Durchschnitt schwierigen Gitterproblemen.
Linear-implicit versions of strong Taylor numerical schemes for finite dimensional Itô stochastic differential equations (SDEs) are shown to have the same order as the original scheme. The combined truncation and global discretization error of an gamma strong linear-implicit Taylor scheme with time-step delta applied to the N dimensional Itô-Galerkin SDE for a class of parabolic stochastic partial differential equation (SPDE) with a strongly monotone linear operator with eigenvalues lambda 1 <= lambda 2 <= ... in its drift term is then estimated by K(lambda N -½ + 1 + delta gamma) where the constant K depends on the initial value, bounds on the other coefficients in the SPDE and the length of the time interval under consideration.
AMS subject classifications: 35R60, 60H15, 65M15, 65U05.
Diese Arbeit befasst sich mit der Zerlegung von Irrfahrten und Lévy Prozessen an ihrem Minimum. Bis auf rudimentäre Vorkenntnisse der höheren Stochastik und einige wenige aber wichtige Sätze stellt die Arbeit alle notwendigen Begriffe und Sätze zur Verfügung, die für das Verständnis und die Beweise benötigt werden. Diese bewusste Entscheidung zur Ausführlichkeit auch bei grundlegenden Dingen hat zwei Hintergründe: Zum einen bleibt die Arbeit damit auch für Leser mit geringen Vorkenntnissen interessant, und zum anderen entsteht so keine lange und unübersichtliche Kette von Verweisen und Zitaten, die das Verständnis des dargestellten Themas erschwert und die logischen Schlüsse nur noch von Spezialisten vollständig nachvollzogen werden können. Ein weiterer Nebeneffekt ist die Tatsache, dass Verwirrungen aufgrund unterschiedlicher Interpretationen eines Begriffs vermieden werden. Das weitere Vorwort teilt sich in zwei Abschnitte; zum einen in den Abschnitt der Irrfahrten und zum anderen in den Abschnitt der Lévy-Prozesse. Diese Einteilung spiegelt auch die Strukturierung der Arbeit selber wieder; ein Blick in das Inhaltsverzeichnis verrät, dass zuerst Irrfahrten und danach Lévy Prozesse behandelt werden.