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) (remove)
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 (6)
- Psychologie (6)
- Geschichtswissenschaften (5)
- Sportwissenschaften (5)
- Biochemie und Chemie (3)
- Biowissenschaften (3)
- Geographie (3)
Komplexität und Zufälligkeit
(1978)
We propose two improvements to the Fiat Shamir authentication and signature scheme. We reduce the communication of the Fiat Shamir authentication scheme to a single round while preserving the e±ciency of the scheme. This also reduces the length of Fiat Shamir signatures. Using secret keys consisting of small integers we reduce the time for signature generation by a factor 3 to 4. We propose a variation of our scheme using class groups that may be secure even if factoring large integers becomes easy.
Public key signature schemes are necessary for the access control to communication networks and for proving the authenticity of sensitive messages such as electronic fund transfers. Since the invention of the RSA scheme by Rivest, Shamir and Adleman (1978) research has focused on improving the e±ciency of these schemes. In this paper we present an efficient algorithm for generating public key signatures which is particularly suited for interactions between smart cards and terminals.
Im Mittelpunkt der vorliegenden Arbeit stehen die Nullstellen der nach Bernhard Riemann benannten Riemannschen Zetafunktion ..(s). Diese Funktion kann für komplexes s mit Res > 1 durch ...(s) = 1 X n=1 1 ns (1.1.1) dargestellt werden. Für andere Werte von s ist ...(s) durch die analytische Fortsetzung der Dirichlet-Reihe in (1.1.1) gegeben. Die ...-Funktion ist in der ganzen komplexen Ebene holomorph, mit Ausnahme des Punktes s = 1, wo sie einen einfachen Pol besitzt. Diese und weitere Eigenschaften von ...(s) setzen wir in dieser Arbeit als bekannt voraus, näheres findet man beispielsweise in [Tit51] oder [Ivi85]. Bereits Euler betrachtete, beispielsweise in [Eul48, Caput XV], die Summe in (1.1.1), allerdings vor allem für ganzzahlige s ... 2. Von ihm stammt die Gleichung 1 X n=1 1 ns =.... die für alle komplexen s mit Res > 1 gültig ist. Dieser Zusammenhang zwischen der ...-Funktion und den Primzahlen war Ausgangspunkt für Riemanns einzige zahlentheoretische, aber dennoch wegweisende Arbeit \ Über die Anzahl der Primzahlen unter einer gegebenen Grösse." ([Rie59]). In dieser 1859 erschienenen Arbeit erkannte Riemann als erster die Bedeutung der Nullstellen der ...-Funktion für die Verteilung der Primzahlen. Bezüglich dieser Nullstellen sei jetzt nur so viel gesagt, daß ...(s) einfache Nullstellen an den negativen geraden Zahlen .... besitzt, und, daß alle weiteren, die sogenannten nicht-trivialen Nullstellen, im kritischen Streifen 0 < Res < 1 liegen. Diese letzteren | unendlich vielen | Nullstellen sind gerade für den Primzahlsatz, also für die Beziehung ...(x) ... li(x);
The general subset sum problem is NP-complete. However, there are two algorithms, one due to Brickell and the other to Lagarias and Odlyzko, which in polynomial time solve almost all subset sum problems of sufficiently low density. Both methods rely on basis reduction algorithms to find short nonzero vectors in special lattices. The Lagarias-Odlyzko algorithm would solve almost all subset sum problems of density < 0.6463 . . . in polynomial time if it could invoke a polynomial-time algorithm for finding the shortest non-zero vector in a lattice. This paper presents two modifications of that algorithm, either one of which would solve almost all problems of density < 0.9408 . . . if it could find shortest non-zero vectors in lattices. These modifications also yield dramatic improvements in practice when they are combined with known lattice basis reduction algorithms.
We report on improved practical algorithms for lattice basis reduction. We propose a practical floating point version of theL3-algorithm of Lenstra, Lenstra, Lovász (1982). We present a variant of theL3-algorithm with "deep insertions" and a practical algorithm for block Korkin—Zolotarev reduction, a concept introduced by Schnorr (1987). Empirical tests show that the strongest of these algorithms solves almost all subset sum problems with up to 66 random weights of arbitrary bit length within at most a few hours on a UNISYS 6000/70 or within a couple of minutes on a SPARC1 + computer.
We call a distribution on n bit strings (", e) locally random, if for every choice of e · n positions the induced distribution on e bit strings is in the L1 norm at most " away from the uniform distribution on e bit strings. We establish local randomness in polynomial random number generators (RNG) that are candidate one way functions. Let N be a squarefree integer and let f1, . . . , f be polynomials with coe±- cients in ZZN = ZZ/NZZ. We study the RNG that stretches a random x 2 ZZN into the sequence of least significant bits of f1(x), . . . , f(x). We show that this RNG provides local randomness if for every prime divisor p of N the polynomials f1, . . . , f are linearly independent modulo the subspace of polynomials of degree · 1 in ZZp[x]. We also establish local randomness in polynomial random function generators. This yields candidates for cryptographic hash functions. The concept of local randomness in families of functions extends the concept of universal families of hash functions by Carter and Wegman (1979). The proofs of our results rely on upper bounds for exponential sums.
Let b1, . . . , bm 2 IRn be an arbitrary basis of lattice L that is a block Korkin Zolotarev basis with block size ¯ and let ¸i(L) denote the successive minima of lattice L. We prove that for i = 1, . . . ,m 4 i + 3 ° 2 i 1 ¯ 1 ¯ · kbik2/¸i(L)2 · ° 2m i ¯ 1 ¯ i + 3 4 where °¯ is the Hermite constant. For ¯ = 3 we establish the optimal upper bound kb1k2/¸1(L)2 · µ3 2¶m 1 2 1 and we present block Korkin Zolotarev lattice bases for which this bound is tight. We improve the Nearest Plane Algorithm of Babai (1986) using block Korkin Zolotarev bases. Given a block Korkin Zolotarev basis b1, . . . , bm with block size ¯ and x 2 L(b1, . . . , bm) a lattice point v can be found in time ¯O(¯) satisfying kx vk2 · m° 2m ¯ 1 ¯ minu2L kx uk2.
Parallel FFT-hashing
(1994)
We propose two families of scalable hash functions for collision resistant hashing that are highly parallel and based on the generalized fast Fourier transform (FFT). FFT hashing is based on multipermutations. This is a basic cryptographic primitive for perfect generation of diffusion and confusion which generalizes the boxes of the classic FFT. The slower FFT hash functions iterate a compression function. For the faster FFT hash functions all rounds are alike with the same number of message words entering each round.
Black box cryptanalysis applies to hash algorithms consisting of many small boxes, connected by a known graph structure, so that the boxes can be evaluated forward and backwards by given oracles. We study attacks that work for any choice of the black boxes, i.e. we scrutinize the given graph structure. For example we analyze the graph of the fast Fourier transform (FFT). We present optimal black box inversions of FFT-compression functions and black box constructions of collisions. This determines the minimal depth of FFT-compression networks for collision-resistant hashing. We propose the concept of multipermutation, which is a pair of orthogonal latin squares, as a new cryptographic primitive that generalizes the boxes of the FFT. Our examples of multipermutations are based on the operations circular rotation, bitwise xor, addition and multiplication.
We propose a fast variant of the Gaussian algorithm for the reduction of two dimensional lattices for the l1-, l2- and l-infinite- norm. The algorithm runs in at most O(nM(B) logB) bit operations for the l-infinite- norm and in O(n log n M(B) logB) bit operations for the l1 and l2 norm on input vectors a, b 2 ZZn with norm at most 2B where M(B) is a time bound for B-bit integer multiplication. This generalizes Schönhages monotone Algorithm [Sch91] to the centered case and to various norms.
We generalize the concept of block reduction for lattice bases from l2-norm to arbitrary norms. This extends the results of Schnorr. We give algorithms for block reduction and apply the resulting enumeration concept to solve subset sum problems. The deterministic algorithm solves all subset sum problems. For up to 66 weights it needs in average less then two hours on a HP 715/50 under HP-UX 9.05.
We study the following problem: given x element Rn either find a short integer relation m element Zn, so that =0 holds for the inner product <.,.>, or prove that no short integer relation exists for x. Hastad, Just Lagarias and Schnorr (1989) give a polynomial time algorithm for the problem. We present a stable variation of the HJLS--algorithm that preserves lower bounds on lambda(x) for infinitesimal changes of x. Given x \in {\RR}^n and \alpha \in \NN this algorithm finds a nearby point x' and a short integer relation m for x'. The nearby point x' is 'good' in the sense that no very short relation exists for points \bar{x} within half the x'--distance from x. On the other hand if x'=x then m is, up to a factor 2^{n/2}, a shortest integer relation for \mbox{x.} Our algorithm uses, for arbitrary real input x, at most \mbox{O(n^4(n+\log \alpha))} many arithmetical operations on real numbers. If x is rational the algorithm operates on integers having at most \mbox{O(n^5+n^3 (\log \alpha)^2 + \log (\|q x\|^2))} many bits where q is the common denominator for x.
In dieser Arbeit werden die mathematischen Grundlagen zur Konstruktion der primären Felder der minimalen Modelle der konformen Quantenfeldtheorie beschrieben. Wir untersuchen Verma und Fock-Moduln der Virasoro-Algebra und klassifizieren diese Moduln bezüglich der Struktur der (ko-) singulären Vektoren. Wir definieren die Vertex-Operatoren zwischen gewissen Fock-Moduln (die eine kanonische Hilbertraumstruktur besitzen) und beweisen verschiedene Eigenschaften dieser Operatoren: Unter bestimmten Voraussetzungen sind Vertex-Operatoren dicht definierte, nicht abschließbare Operatoren zwischen den Fock-Moduln. Radialgeordnete Produkte von Vertex-Operatoren existieren auf einem dichten Teilraum. Wir beweisen Kommutatorrelationen zwischen Vertex-Operatoren und den Generatoren der Virasoro-Algebra. Dann definieren wir die integrierten Vertex-Operatoren und zeigen, daß diese Operatoren im wesentlichen wieder die Eigenschaften der nichtintegrierten Vertex-Operatoren haben. Gewisse integrierte Vertex-Operatoren können mit konformen Felder identifiziert werden. Ein unter den Vertex-Operatoren invarianter Unterraum der Fock-Moduln kann mit dem physikalischen Zustandsraum identifiziert werden.
Wir verallgemeinern die Reduktionstheorie von Gitterbasen für beliebige Normen. Dabei zeigen wir neue Eigenschaften reduzierter Basen für die verallgemeinerten Reduktionsbegriffe. Wir verallgemeinern den Gauß-Algorithmus zur Reduktion zweidimensionaler Gitterbasen für alle Normen und erhalten eine universelle scharfe obere Schranke für die Zahl seiner Iterationen. Wir entwickeln für spezielle lp-Normen eine Variante des Gauß-Algorithmus mit niedriger Bit-Komplexität. Hierzu wird Schönhages schneller Reduktionsalgorithmus für quadratische Formen auf die Reduktion von Gitterbasen im klassischen zentrierten Fall übertragen.
Gitter sind diskrete additive Untergruppen des Rn. Praktische Bedeutung erlangte die Gittertheorie durch effziente Algorithmen zur Gitterbasenreduktion, mit deren Hilfe Optimierungsprobleme gelöst werden können. Der erste dieser Algorithmen wurde von Lenstra, Lenstra und Lovasz entwickelt. Schnorr und Euchner entwickelten effizientere Algorithmen. Sie untersuchten die Güte der Reduktion anhand von Rucksack-Problemen. Bei einem Rucksack-Problem der Dimension n müssen aus einer gegebenen Menge von n Gewichten diejenigen bestimmt werden, die zusammen einen gegeben Rucksack genau ausfüllen. Die Algorithmen von Schnorr und Euchner lösen fast alle Rucksack-Probleme der Dimensionen 42 bis 66. Meine neuen verbesserten Algorithmen lösen einen noch größeren Anteil der Rucksack-Probleme in kürzerer Rechenzeit. Gleichzeitig sind sie in Dimensionen 103 bis 151. Coster, Joux, LaMacchia. Odlyzko, Schnorr und Stern geben eine untere Schranke für die Größe der Gewichte von Rucksack-Problemen an, die fast immer gelöst werden können. Die Gewichte werden zufällig aus einem Intervall natüurlicher Zahlen gewählt. Dieses Ergebnis erweitere ich auf k-fache Rucksack-Probleme. Weiterhin kann für für die Wahl jedes Gewichtes eine beliebige Menge ganzer Zahlen festgelegt werden. Ebenso sind Mengen mit nur einem Element zulässig.
We call a vector x/spl isin/R/sup n/ highly regular if it satisfies =0 for some short, non-zero integer vector m where <...> is the inner product. We present an algorithm which given x/spl isin/R/sup n/ and /spl alpha//spl isin/N finds a highly regular nearby point x' and a short integer relation m for x'. The nearby point x' is 'good' in the sense that no short relation m~ of length less than /spl alpha//2 exists for points x~ within half the x'-distance from x. The integer relation m for x' is for random x up to an average factor 2/sup /spl alpha//2/ a shortest integer relation for x'. Our algorithm uses, for arbitrary real input x, at most O(n/sup 4/(n+log A)) many arithmetical operations on real numbers. If a is rational the algorithm operates on integers having at most O(n/sup 5/+n/sup 3/(log /spl alpha/)/sup 2/+log(/spl par/qx/spl par//sup 2/)) many bits where q is the common denominator for x.