Refine
Year of publication
Document Type
- Preprint (739)
- Article (401)
- Working Paper (119)
- Doctoral Thesis (92)
- Diploma Thesis (46)
- Conference Proceeding (41)
- Book (37)
- Bachelor Thesis (34)
- diplomthesis (29)
- Report (25)
Has Fulltext
- yes (1595) (remove)
Is part of the Bibliography
- no (1595)
Keywords
Institute
- Informatik (1595) (remove)
Considered are the classes QL (quasilinear) and NQL (nondet quasllmear) of all those problems that can be solved by deterministic (nondetermlnlsttc, respectively) Turmg machines in time O(n(log n) ~) for some k Effloent algorithms have time bounds of th~s type, it is argued. Many of the "exhausUve search" type problems such as satlsflablhty and colorabdlty are complete in NQL with respect to reductions that take O(n(log n) k) steps This lmphes that QL = NQL iff satisfiabdlty is m QL CR CATEGORIES: 5.25
We present a hierarchy of polynomial time lattice basis reduction algorithms that stretch from Lenstra, Lenstra, Lovász reduction to Korkine–Zolotareff reduction. Let λ(L) be the length of a shortest nonzero element of a lattice L. We present an algorithm which for k∈N finds a nonzero lattice vector b so that |b|2⩽(6k2)nkλ(L)2. This algorithm uses O(n2(kk+o(k))+n2)log B) arithmetic operations on O(n log B)-bit integers. This holds provided that the given basis vectors b1,…,bn∈Zn are integral and have the length bound B. This algorithm successively applies Korkine–Zolotareff reduction to blocks of length k of the lattice basis. We also improve Kannan's algorithm for Korkine-Zolotareff reduction.
Performance and storage requirements of topology-conserving maps for robot manipulator control
(1989)
A new programming paradigm for the control of a robot manipulator by learning the mapping between the Cartesian space and the joint space (inverse Kinematic) is discussed. It is based on a Neural Network model of optimal mapping between two high-dimensional spaces by Kohonen. This paper describes the approach and presents the optimal mapping, based on the principle of maximal information gain. It is shown that Kohonens mapping in the 2-dimensional case is optimal in this sense. Furthermore, the principal control error made by the learned mapping is evaluated for the example of the commonly used PUMA robot, the trade-off between storage resources and positional error is discussed and an optimal position encoding resolution is proposed.
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.
It is well known that artificial neural nets can be used as approximators of any continous functions to any desired degree. Nevertheless, for a given application and a given network architecture the non-trivial task rests to determine the necessary number of neurons and the necessary accuracy (number of bits) per weight for a satisfactory operation. In this paper the problem is treated by an information theoretic approach. The values for the weights and thresholds in the approximator network are determined analytically. Furthermore, the accuracy of the weights and the number of neurons are seen as general system parameters which determine the the maximal output information (i.e. the approximation error) by the absolute amount and the relative distribution of information contained in the network. A new principle of optimal information distribution is proposed and the conditions for the optimal system parameters are derived. For the simple, instructive example of a linear approximation of a non-linear, quadratic function, the principle of optimal information distribution gives the the optimal system parameters, i.e. the number of neurons and the different resolutions of the variables.
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.
It is well known that artificial neural nets can be used as approximators of any continuous functions to any desired degree and therefore be used e.g. in high - speed, real-time process control. Nevertheless, for a given application and a given network architecture the non-trivial task remains to determine the necessary number of neurons and the necessary accuracy (number of bits) per weight for a satisfactory operation which are critical issues in VLSI and computer implementations of nontrivial tasks. In this paper the accuracy of the weights and the number of neurons are seen as general system parameters which determine the maximal approximation error by the absolute amount and the relative distribution of information contained in the network. We define as the error-bounded network descriptional complexity the minimal number of bits for a class of approximation networks which show a certain approximation error and achieve the conditions for this goal by the new principle of optimal information distribution. For two examples, a simple linear approximation of a non-linear, quadratic function and a non-linear approximation of the inverse kinematic transformation used in robot manipulator control, the principle of optimal information distribution gives the the optimal number of neurons and the resolutions of the variables, i.e. the minimal amount of storage for the neural net. Keywords: Kolmogorov complexity, e-Entropy, rate-distortion theory, approximation networks, information distribution, weight resolutions, Kohonen mapping, robot control.
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.
One of the most interesting domains of feedforward networks is the processing of sensor signals. There do exist some networks which extract most of the information by implementing the maximum entropy principle for Gaussian sources. This is done by transforming input patterns to the base of eigenvectors of the input autocorrelation matrix with the biggest eigenvalues. The basic building block of these networks is the linear neuron, learning with the Oja learning rule. Nevertheless, some researchers in pattern recognition theory claim that for pattern recognition and classification clustering transformations are needed which reduce the intra-class entropy. This leads to stable, reliable features and is implemented for Gaussian sources by a linear transformation using the eigenvectors with the smallest eigenvalues. In another paper (Brause 1992) it is shown that the basic building block for such a transformation can be implemented by a linear neuron using an Anti-Hebb rule and restricted weights. This paper shows the analog VLSI design for such a building block, using standard modules of multiplication and addition. The most tedious problem in this VLSI-application is the design of an analog vector normalization circuitry. It can be shown that the standard approaches of weight summation will not give the convergence to the eigenvectors for a proper feature transformation. To avoid this problem, our design differs significantly from the standard approaches by computing the real Euclidean norm. Keywords: minimum entropy, principal component analysis, VLSI, neural networks, surface approximation, cluster transformation, weight normalization circuit.
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 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.
Die Implementation der Striktheits-Analyse, die im Zuge dieser Arbeit vorgenommen wurde, stellt eine effiziente Approximation der abstrakten Reduktion mit Pfadanalyse dar. Durch die G#-Maschine, ein neues, auf der G-Maschine basierendes Maschinenmodell, wurde die verwendete Methode systematisch dargelegt. Die große Ähnlichkeit mit der G-Maschin, die in unserer Implementation beibehalten werden konnte, zeigt, wie natürlich die verwendete Methode der Reduktion in funktionalen Programmiersprachen entspricht. Obwohl die Umsetzung mehr Wert auf Nachvollziehbarkeit, als auf Effizienz legt, zeigt sie, daß die Methode der abstrakten Reduktion mit Pfadanalyse auch in einer funktionalen Implementierung durchaus alltagstauglich ist und Striktheits-Information findet, die Umsetzungen anderer Methoden nicht finden. Es bestehen Möglichkeiten zur Optimierung u. a. von Programmteilen, die für jede simulierte G#-Maschinen-Anweisung ausgeführt werden. Bei vorsichtiger Einschätzung erscheint eine Halbierung der Laufzeit mit vertretbarem Aufwand erreichbar.
We consider the problem of unifying a set of equations between second-order terms. Terms are constructed from function symbols, constant symbols and variables, and furthermore using monadic second-order variables that may stand for a term with one hole, and parametric terms. We consider stratified systems, where for every first-order and second-order variable, the string of second-order variables on the path from the root of a term to every occurrence of this variable is always the same. It is shown that unification of stratified second-order terms is decidable by describing a nondeterministic decision algorithm that eventually uses Makanin's algorithm for deciding the unifiability of word equations. As a generalization, we show that the method can be used as a unification procedure for non-stratified second-order systems, and describe conditions for termination in the general case.
We consider unification of terms under the equational theory of two-sided distributivity D with the axioms x*(y+z) = x*y + x*z and (x+y)*z = x*z + y*z. The main result of this paper is that Dunification is decidable by giving a non-deterministic transformation algorithm. The generated unification are: an AC1-problem with linear constant restrictions and a second-order unification problem that can be transformed into a word-unification problem that can be decided using Makanin's algorithm. This solves an open problem in the field of unification. Furthermore it is shown that the word-problem can be decided in polynomial time, hence D-matching is NP-complete.
In Abschnitt 4.1 wurden Algebren auf Mengen und Relationen vorgestellt. Desweitern wurde in Abschnitt 4.2 eine zu ALC erweiterte terminologische Wissensrepräsentationssprache ALCX definiert und gezeigt, daß die in Abschnitt 4.1 vorgestellten Algebren zur Festlegung der odell-theoretischen Semantik der Sprache ALCX benutzt werden können. Als Ergebnis einer derartigen Festlegung kann jeder terminologische Ausdruck direkt mit einem algebraischen Term assoziiert werden. Desweitern können alle in den Algebren aufgeführten universellen Identitäten in semantisch äquivalente terminologische Identitäten überführt werden. Eine mittels ALCX repräsentierte Wissensbasis ist in meinem Programm mit Hilfe der in der funktionalen Programmiersprache Gofer (Version 2.28) gegebenen Möglichkeiten formuliert. Mein Programm bietet durch Simplifizierung von Anfrageausdrücken eine optimierte Lösung des aus dem Bereich der Wissensrepräsentation bekannten Retrieval-Problems. Die Simplifizierung von Anfrageausdrücken wird in meinem Programm erzielt, indem in den oben genannten Algebren erfüllte universelle Identitäten als Simplifikationshilfsmittel benutzt werden. Die in den Algebren aufgeführten universellen Identitäten bestehen stets aus zwei äquivalenten Termen, für die eine unterschiedliche Anzahl von Reduktionsschritten zur Evaluierung benötigt werden. Es existieren universelle Identitäten, bei denen unabhängig von den Instanzen der Argumentterme ein Term gegenüber einem anderen Term effizienter auswertbar ist. Bei diesen universellen Identitäten kann eine Simplifikation von einem Term zu einem anderen Term immer unproblematisch realisiert werden. Es gibt jedoch auch universelle Identitäten, bei denen die Unabhängigkeit von den Instanzen der Argumentterme nicht gegeben ist. In diesen Fällen wird ein von der Wissensbasis abhängiges Komplexitätsabschätzungsverfahren eingesetzt, um den effizienter auswertbaren Term von zwei an einer universellen Identität beteiligten Termen zu ermitteln. Daß die Simplifikation eines Anfrageausdrucks große Einsparungen bei dessen Auswertung nach sich ziehen kann, wurde an verschiedenen Beispielen in Abschnitt 5.4.4 gezeigt. Über eine weitere Möglichkeit, die zum Simplifizieren von Anfrageausdrucken verwendet werden kann, wurde in Abschnitt 5.4.5 berichtet. Die Genauigkeit der Komplexitätsabschätzung kann erhöht werden, indem das Komplexitätsabschätzungsverfahren erweitert wird. So kann beispielsweise die Komplexität der Funktion "oder" genauer abgeschätzt werden, indem für zu vereinigende Mengen überprüft wird, ob Teilmengenbeziehungen vorhanden sind. Durch eine genauere Abschätzung der Mächtigkeit entstehender Vereinigungsmengen wird die Komplexitätsabschätzung insgesamt in ihrer Genauigkeit gesteigert. Eine Änderung der Instanzen meiner terminologischen Datenbank erfordert eine Änderung des Skripts meines Programms. Indem die Instanzen-Daten in einer veränderlichen Datenbank festgehalten würden, könnte hier Abhilfe geschaffen werden. Dies könnte im Rahmen der Erstellung einer benutzterfreundlichen Ein- und Ausgabe-Schnittstelle realisiert werden.
Wir haben in dieser Arbeit einige Probleme auf Objekten betrachtet, deren Struktur wohlgeformten Klammerworten entspricht. Dies waren spezielle Routing-Probleme, das Umformen und Auswerten algebraischer Ausdrücke, sowie die Berechnung korrespondierender Symbole zweier Ausdrücke. Eine effiziente Lösung dieser Probleme gelang durch einen rekursiven Divide-and-Conquer Ansatz, der auf Grund der “natürlichen” rekursiven Definition der betrachteten Objekte auch nahe liegt. Im Divide-Schritt wurde das jeweilige Problem in viele wesentlich kleinere Teilprobleme zerlegt, so daß die gesamte Laufzeit des Algorithmus asymptotisch gleich der des Divide-Schrittes und des Conquer-Schrittes blieb. Das Zerlegen der Probleme erfolgte im wesentlichen unter Anwendung bekannter Routing-Algorithmen für monotone Routings und Bit-Permute-Complement Permutationen. Im Conquer-Schritt für das Klammerrouting und das Knotenkorrespondenzproblem wurden nur die Datenbewegungen des Divide-Schrittes rückwärts ausgeführt. Für das Tree-Contraction-Problem wurde dagegen im Conquer-Schritt die Hauptarbeit geleistet. Die Methode der Simulation eines PRAMAlgorithmus durch die Berechnung seiner Kommunikationsstruktur und eine entsprechende Umordnung der Datenelemente konnte sowohl für eine effiziente Implementierung des Tree-Contraction Conquer-Schrittes auf dem Hyperwürfel als auch für die Konstruktion eines einfachen NC1-Schaltkreises zum Auswerten Boolescher Formeln angewandt werden. In einer Implementierung eines Divide-and-Conquer Algorithmus auf einem Netzwerk müssen den generierten Teilproblemen für ihre weitere Bearbeitung Teile des Netzwerks zugeordnet werden. Um die weiteren Divide-Schritte nach der gleichen Methode ausführen zu können, sollte die Struktur dieser Teilnetzwerke analog zu der des gesamten Netzwerks sein. Wir haben das Teilnetzwerk-Zuweisungsproblem für den Hyperwürfel und einige hyperwürfelartige Netzwerke untersucht. Der Hyperwürfel und das Butterfly-Netzwerk können so in Teilnetzwerke vorgegebener Größen aufgeteilt werden, daß nur ein geringer Anteil der Prozessoren ungenutzt bleibt, und die Teilprobleme können schnell in die ihnen zugeordneten Teilnetzwerke gesendet werden. Unter Anwendung dieser Teilnetzwerk-Zuweisungs-Algorithmen haben wir optimale Implementierungen für eine große Klasse von Divide-and-Conquer Algorithmen auf dem Hyperwüfel und hyperwürfelartigen Netzwerken erhalten. Wir konnten garantieren, daß die Laufzeit der gesamten Implementierung des Divide-and-Conquer Algorithmus asymptotisch gleich der Laufzeit ist, die sich aus dem gegebenen Divide-Schritt und Conquer-Schritt ergibt, wenn man alle mit der Teilnetzwerk-Zuweisung verbundenen Probleme außer acht läßt. Wir haben die hier vorgestellte allgemeine Divide-and-Conquer Implementierung im optimalen Teilwürfel-Zuweisungs-Algorithmus, im Klammerrouting-Algorithmus, der selbst ein wesentlicher Teil des Tree-Contraction-Algorithmus ist, und im Algorithmus für das Knotenkorrespondenzproblem eingesetzt.
We present a framework for the self-organized formation of high level learning by a statistical preprocessing of features. The paper focuses first on the formation of the features in the context of layers of feature processing units as a kind of resource-restricted associative multiresolution learning We clame that such an architecture must reach maturity by basic statistical proportions, optimizing the information processing capabilities of each layer. The final symbolic output is learned by pure association of features of different levels and kind of sensorial input. Finally, we also show that common error-correction learning for motor skills can be accomplished also by non-specific associative learning. Keywords: feedforward network layers, maximal information gain, restricted Hebbian learning, cellular neural nets, evolutionary associative learning
After a short introduction into traditional image transform coding, multirate systems and multiscale signal coding the paper focuses on the subject of image encoding by a neural network. Taking also noise into account a network model is proposed which not only learns the optimal localized basis functions for the transform but also learns to implement a whitening filter by multi-resolution encoding. A simulation showing the multi-resolution capabilitys concludes the contribution.
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.
We introduce algorithms for lattice basis reduction that are improvements of the famous L3-algorithm. If a random L3-reduced lattice basis b1,b2,...,bn is given such that the vector of reduced Gram-Schmidt coefficients ({µi,j} 1<= j< i<= n) is uniformly distributed in [0,1)n(n-1)/2, then the pruned enumeration finds with positive probability a shortest lattice vector. We demonstrate the power of these algorithms by solving random subset sum problems of arbitrary density with 74 and 82 many weights, by breaking the Chor-Rivest cryptoscheme in dimensions 103 and 151 and by breaking Damgard's hash function.
Die Anfänge der Gittertheorie reichen in das letzte Jahrhundert, wobei die wohl bekanntesten Ergebnisse auf Gauß, Hermite und Minkowski zurückgehen. Die Arbeiten sind jedoch zumeist in der Schreibweise der quadratischen Formen verfaßt, erst in den letzten Jahrzehnten hat sich die von uns verwendete Gitterschreibweise durchgesetzt. Diese ist zum einen geometrisch anschaulicher, zum anderen wurden in den letzten Jahren für diese Schreibweise effiziente Algorithmen entwickelt, so daß Probleme der Gittertheorie mittels Computer gelöst werden können. Ein wichtiges Problem ist, in einem Gitter einen kürzesten nicht verschwindenden Vektor zu bestimmen. Den Grundstein für diese algorithmische Entwicklung legten A.K. Lenstra, H.W. Lenstra Jr. und L. Lovasz mit ihrer Arbeit. In dieser führten sie einen Reduktionsbegriff ein, der durch einen Polynomialzeitalgorithmus erreicht werden kann. Ein weiterer Reduktionsbegriff, die Blockreduktion, geht auf Schnorr zurück. Euchner hat im Rahmen seiner Diplomarbeit effiziente Algorithmen für diese beiden Reduktionsbegriffe auf Workstations implementiert und auch in Dimensionen > 100 erfolgreich getestet. Die Verbesserungen von Schnittechniken des in der Blockreduktion verwendeten Aufzählungsverfahrens und die Einführung einer geschnittenen Aufzählung über die gesamte Gitterbasis hat Hörner in seiner Diplomarbeit beschrieben. Ziel der folgenden Arbeit war es nun, diese bereits auf sequentiellen Computern implementierten Algorithmen zu modifizieren, um auf parallelen Rechnern, speziell Vektorrechnern, einen möglichst hohen Geschwindigkeitsgewinn zu erzielen. Wie in den seriellen Algorithmen werden die Basisvektoren stets in exakter Darstellung mitgeführt, so daß das Endergebnis einer Berechnung nicht durch Rundungsfehler verfälscht wird.
Im Jahr 1993 schlug A. Shamir Protokolle zur Erstellung digitaler Unterschriften vor, die auf rationalen Funktionen kleinen Grades beruhen. D. Coppersmith, J. Stern und S. Vaudenay präsentierten die ersten Angriffe auf die Verfahren. Diese Angriffe können den geheimen Schlüssel nicht ermitteln. Für eine der von Shamir vorgeschlagenen Varianten zeigen wir, wie der geheime Schlüssel ermittelt werden kann. Das zweite Signaturschema von Shamir hängt von der Wahl einer algebraischen Basis ab. Eine besondere Bedeutung haben Basen, deren Elemente polynomiale Terme vom Grad 2 sind. Wir analysieren die Struktur der algebraischen Basen. Für den hervorgehobenen Spezialfall kann eine vollständige Klassifikation durchgeführt werden.
The paper focuses on the division of the sensor field into subsets of sensor events and proposes the linear transformation with the smallest achievable error for reproduction: the transform coding approach using the principal component analysis (PCA). For the implementation of the PCA, this paper introduces a new symmetrical, lateral inhibited neural network model, proposes an objective function for it and deduces the corresponding learning rules. The necessary conditions for the learning rate and the inhibition parameter for balancing the crosscorrelations vs. the autocorrelations are computed. The simulation reveals that an increasing inhibition can speed up the convergence process in the beginning slightly. In the remaining paper, the application of the network in picture encoding is discussed. Here, the use of non-completely connected networks for the self-organized formation of templates in cellular neural networks is shown. It turns out that the self-organizing Kohonen map is just the non-linear, first order approximation of a general self-organizing scheme. Hereby, the classical transform picture coding is changed to a parallel, local model of linear transformation by locally changing sets of self-organized eigenvector projections with overlapping input receptive fields. This approach favors an effective, cheap implementation of sensor encoding directly on the sensor chip. Keywords: Transform coding, Principal component analysis, Lateral inhibited network, Cellular neural network, Kohonen map, Self-organized eigenvector jets.
This paper describes the use of a radial basis function (RBF) neural network. It approximates the process parameters for the extrusion of a rubber profile used in tyre production. After introducing the problem, we describe the RBF net algorithm and the modeling of the industrial problem. The algorithm shows good results even using only a few training samples. It turns out that the „curse of dimensions“ plays an important role in the model. The paper concludes by a discussion of possible systematic error influences and improvements.
Das Thema dieser Arbeit ist die Dienstvermittlung in offenen verteilten Systemen und die Rolle, die ein Typsystem dabei einnimmt. Ein Typsystem besteht aus einer Typbeschreibungssprache und der Definition einer Typkonformität. Die Typbeschreibungssprache erlaubt die Spezifiation von Typen, wohingegen mit der Typkonformität während eines Vermittlungsvorgangs überprüft wird, ob Angebot und Nachfrage zusammenpassen. In dieser Arbeit wurde zunächst nachgewiesen, daß es sinnvoll ist, bei einem Typ zwischen seiner Intension und seiner Extension zu unterscheiden. Die Intension eines Typs ist die Gesamtheit aller Beschreibungen, die auf diesen zutreffen. Die Extension eines Typs repräsentiert dagegen eine konkrete Beschreibung (d.h. Spezifikation eines Dienstangebots). Eine Interpretation ordnet jeder Extension eine Intension zu. Um in einem offenen verteilten System Dienste vermitteln zu können, müssen sich Dienstnutzer und {anbieter auf die Extensionen aller Typen einigen. Einem Typ kommt hierdurch die Rolle eine Standards zu, der allen beteiligten Parteien a priori bekannt sein muß. Daraus resultiert eine injektive Interpretation, die jeder Intension genau eine Extension zuordnet. Die eindeutig bestimmte Extension einer Intension fungiert als systemweiter Standard. Ein Typ als Standard steht im Widerspruch zu der Vielfalt und Dynamik eines offenen Dienstmarktes. Der Standardisierungsprozeß von Extensionen, der einem Vermittlungsvorgang vorausgehen muß, hemmt gerade die Dynamik des Systems. Die Konsequenz daraus ist, daß neben den Diensten auch die Diensttypen Gegenstand der Vermittlung sein müssen. Diese Schlußfolgerung ist bisher noch nicht formuliert worden. Es wäre somit wünscheswert, nicht{injektive Interpretationen zuzulassen, so daß eine Intension mehrere Extensionen besitzen kann, die unterschiedliche Sichten der Dienstnutzer und {anbieter repräsentieren. Die Analyse einiger bestehender Typsysteme zeigte, daß mit diesen eine nicht-injektive Interpretation nicht realisierbar ist. Im Hauptteil dieser Arbeit wurden zwei neue Typsysteme vorgestellt, die diese Eigenschaft unterstützen. Das deklarative Typsystem erweitert die Schnittstellenbeschreibungssprache eines syntaktischen Typsystems, indem semantische Spezifiationen zugelassen werden. Die deklarative Semantik dient dabei als Grundlage für die Beschreibung der Semantik einer Typspezifikation. Die Extension entspricht einem definiten Programm bestehend aus einer endlichen Menge von Horn-Klauseln. Die Intension eines Typs korrespondiert mit dem kleinsten Herbrand-Modell des definiten Programms, welches die semantische Spezifikation des Typs darstellt. Die Forderung nach der Möglichkeit nicht{injektiver Interpretationen ergibt sich aus den Eigenschaften der deklarativen Semantik, wonach verschiedene definite Programme ein identisches kleinstes Herbrand-Modell besitzen können. Das zweite in dieser Arbeit vorgestellte Typsystem entspringt einem wissensbasierten Ansatz. Grundlage bildet eine Wissensrepräsentationstechnik, die anwenderbezogene semantische Spezifikationen erlaubt. Ein Konzeptgraph als wissensbasierte Typspezifikation vereinigt in sich unterschiedliche Beschreibungen eines Typs. Ein Konzeptgraph, der selbst eine Extension darstellt, repräsentiert somit die Vereinigung mehrerer Extensionen eines Typs. Die Intension ist jedoch durch einen Konzeptgraph nicht eindeutig bestimmt. Dieser stellt lediglich eine Approximation dar. Hier liegt ein fundamentaler Unterschied in den beiden Typsystemen. Während eine Extension im deklarativen Typsystem auch immer eindeutig eine Intension charakterisiert, ist dies bei dem wissensbasierten Typsystem nicht der Fall. Die Konsequenz daraus ist, daß dieser Umstand bei einem Vermittlungsvorgang berücksichtigt werden muß. Ein wissensbasierter Vermittler muß über ein spezielles Vermittlungsprotokoll die Verfeinerung einer wissensbasierten Typspezifikation erlauben, die zu einer besseren Approximation der Intension führt. Das deklarative Typsystem besitzt aufgrund der Unentscheidbarkeit der deklarativen Typkonformität keine praktische Relevanz. Es zeigt jedoch, wie mit Hilfe der deklarativen Semantik der Open World Assumption genüge geleistet werden kann. Im Vergleich dazu kann das wissensbasierte Typsystem als "Fuzzyfizierung" des deklarativen Typsystems angesehen werden. Die wissensbasierte Typbeschreibungssprache ermöglicht im Sinne der Fuzzy Logik unscharfe Spezifikationen, die im Laufe der Zeit verfeinert werden. Ein Vorteil des wissensbasierten Ansatzes ist die Möglichkeit von anwenderbezogenen Typspezifikationen. Ein anderer Vorteil besteht darin, daß eine wissensbasierte Typbeschreibungssprache eine Meta-Sprache repräsentiert, in der Spezifikationen aus anderen Domänen dargestellt werden können. Ungeachtet dieser Vorteile bleibt jedoch der Beweis offen, daß die wissensbasierte Dienstvermittlung tatsächlich eine geeignete Methodik für die Vermittlung von Typen darstellt.
Automatic termination proofs of functional programming languages are an often challenged problem Most work in this area is done on strict languages Orderings for arguments of recursive calls are generated In lazily evaluated languages arguments for functions are not necessarily evaluated to a normal form It is not a trivial task to de ne orderings on expressions that are not in normal form or that do not even have a normal form We propose a method based on an abstract reduction process that reduces up to the point when su cient ordering relations can be found The proposed method is able to nd termination proofs for lazily evaluated programs that involve non terminating subexpressions Analysis is performed on a higher order polymorphic typed language and termi nation of higher order functions can be proved too The calculus can be used to derive information on a wide range on di erent notions of termination.
Korrektur zu: C.P. Schnorr: Security of 2t-Root Identification and Signatures, Proceedings CRYPTO'96, Springer LNCS 1109, (1996), pp. 143-156 page 148, section 3, line 5 of the proof of Theorem 3. Die Korrektur wurde präsentiert als: "Factoring N via proper 2 t-Roots of 1 mod N" at Eurocrypt '97 rump session.
We analyse a continued fraction algorithm (abbreviated CFA) for arbitrary dimension n showing that it produces simultaneous diophantine approximations which are up to the factor 2^((n+2)/4) best possible. Given a real vector x=(x_1,...,x_{n-1},1) in R^n this CFA generates a sequence of vectors (p_1^(k),...,p_{n-1}^(k),q^(k)) in Z^n, k=1,2,... with increasing integers |q^{(k)}| satisfying for i=1,...,n-1 | x_i - p_i^(k)/q^(k) | <= 2^((n+2)/4) sqrt(1+x_i^2) |q^(k)|^(1+1/(n-1)) By a theorem of Dirichlet this bound is best possible in that the exponent 1+1/(n-1) can in general not be increased.
Given x small epsilon, Greek Rn an integer relation for x is a non-trivial vector m small epsilon, Greek Zn with inner product <m,x> = 0. In this paper we prove the following: Unless every NP language is recognizable in deterministic quasi-polynomial time, i.e., in time O(npoly(log n)), the ℓinfinity-shortest integer relation for a given vector x small epsilon, Greek Qn cannot be approximated in polynomial time within a factor of 2log0.5 − small gamma, Greekn, where small gamma, Greek is an arbitrarily small positive constant. This result is quasi-complementary to positive results derived from lattice basis reduction. A variant of the well-known L3-algorithm approximates for a vector x small epsilon, Greek Qn the ℓ2-shortest integer relation within a factor of 2n/2 in polynomial time. Our proof relies on recent advances in the theory of probabilistically checkable proofs, in particular on a reduction from 2-prover 1-round interactive proof-systems. The same inapproximability result is valid for finding the ℓinfinity-shortest integer solution for a homogeneous linear system of equations over Q.
We study the approximability of the following NP-complete (in their feasibility recognition forms) number theoretic optimization problems: 1. Given n numbers a1 ; : : : ; an 2 Z, find a minimum gcd set for a1 ; : : : ; an , i.e., a subset S fa1 ; : : : ; ang with minimum cardinality satisfying gcd(S) = gcd(a1 ; : : : ; an ). 2. Given n numbers a1 ; : : : ; an 2 Z, find a 1-minimum gcd multiplier for a1 ; : : : ; an , i.e., a vector x 2 Z n with minimum max 1in jx i j satisfying P n...
A partial rehabilitation of side-effecting I/O : non-determinism in non-strict functional languages
(1996)
We investigate the extension of non-strict functional languages like Haskell or Clean by a non-deterministic interaction with the external world. Using call-by-need and a natural semantics which describes the reduction of graphs, this can be done such that the Church-Rosser Theorems 1 and 2 hold. Our operational semantics is a base to recognise which particular equivalencies are preserved by program transformations. The amount of sequentialisation may be smaller than that enforced by other approaches and the programming style is closer to the common one of side-effecting programming. However, not all program transformations used by an optimising compiler for Haskell remain correct in all contexts. Our result can be interpreted as a possibility to extend current I/O-mechanism by non-deterministic deterministic memoryless function calls. For example, this permits a call to a random number generator. Adding memoryless function calls to monadic I/O is possible and has a potential to extend the Haskell I/O-system.
An anaphor resolution algorithm is presented which relies on a combination of strategies for narrowing down and selecting from antecedent sets for re exive pronouns, nonre exive pronouns, and common nouns. The work focuses on syntactic restrictions which are derived from Chomsky's Binding Theory. It is discussed how these constraints can be incorporated adequately in an anaphor resolution algorithm. Moreover, by showing that pragmatic inferences may be necessary, the limits of syntactic restrictions are elucidated.
Funktionsorientierte Bausteine zur Integration kontinuierlicher Medien in verteilte Anwendungen
(1997)
Das Ziel der vorliegenden Arbeit war die Entwicklung einer komfortablen Beschreibung verteilter Anwendungen, die kontinuierliche Medien integrieren. Die Klarheit des Ansatzes ergibt sich aus der Beschränkung auf die anwenderrelevanten Funktionalitäten. Weitere Gebiete, die systembezogen sind, wurden nur soweit wie nötig behandelt. Die Aufgaben anderer Bereiche, wie des Betriebssystems und des Managementsystems sowie der Kommunikationsdienste, konnten nur gestreift werden, indem die anwendungsabhängigen Anforderungen spezifiziert wurden. Durch deren Extraktion und die Zuordnung der Anforderungen an die einzelnen Bereiche, ergibt sich eine klarere Sicht auf Betriebssystem, Management und Kommunikationsdienste und deren notwendige Weiterentwicklung. Das entwickelte Funktionenmodell beschreibt zusammenhängend alle mit kontinuierlichen Medien verbundenen Arbeiten. In der vorliegenden Arbeit wurde gezeigt, wie aus den Funktionen auf kontinuierlichen Medien durch die Spezifikation geeigneter Schnittstellen Bausteine zur Integration der Medien in verteilte Anwendungen erstellt werden. Die Beschrei bung der Bausteine erfolgt durch diese Schnittstellen; es sind Steuer-, Daten- und Managementschnittstellen. Die Herauslösung der gesonderten Beschreibung der Multimedia-Datenflußstruktur schafft einerseits die Grundlage für eine Teilklassifikation der Anwendungen nach Medien-Gesichtspunkten. Andererseits kann die Erstellung einer Anwendung aus einer bestimmten Anwendungsklasse, wie zum Beispiel ein einfaches Wiedergabesystem, durch die gesonderte Beschreibung der Multimedia-Datenflußstruktur schneller in der Bausteinstruktur realisiert werden. Das Funktionenmodell wird auch in [Fritzsche96] beschrieben. Das in dieser Arbeit konzipierte Bausteinmodell gewährleistet eine integrierte Beschreibung von Geräten, Werkzeugen und Anwendungen kontinuierlicher Medien. Die verwendete Beschreibungstechnik erlaubt dabei nicht nur eine übersichtliche Darstellung sondern bietet auch hierarchische Strukturierungen an. Das Zusammenspiel der Bausteine erfordert zu sätzliche Komponenten zur Steuerung und Abstimmung der einzelnen Funktionen, die in dieser Arbeit neu eingeführt werden. Es lassen sich sowohl zentralistische als auch verteilte Steuerungen realisieren. Mit einer entsprechenden Schnittstelle versehen kann eine Steuerkomponente eine ganze Gruppe von Bausteinen dem Benutzer als Einheit zur Verfügung stellen. Somit lassen sich auch verschiedene Medien und/oder mehrere Funktionen gemeinsam mit einer Steuerkomponente zu einem Baustein zusammenfassen. Diese zusammenge setzten Bausteine bieten nun echte Multifunktionalität und Multimedialität. Durch die Komponenten- und Anwendungsmodellierung nach [Zimm93] wird darüber hinaus eine flexible, auch dynamisch änderbare Anwendungsstruktur vom Anwendungs-Management ermöglicht. Das Bausteinmodell wird auch in [Fritzsche96] behandelt. Bisherigen Ansätzen für Multimedia-Komponenten fehlt die allgemeine Interoperabilität der Komponenten. Diese kann nur durch eine umfassende, formale Spezifikation der Komponenten-Schnittstellen, insbesondere aber von Steuerschnittstellen, erfolgen. Zur Spezifikation der Schnittstellen ist die Integration der kontinuierlichen oder zeitabhängigen Medien als abstrakte Datentypen unabdingbar. Auf diese Art werden aus den Komponenten Bausteine. Im vorliegenden Ansatz wurden erstmalig Steuerschnittstellen für Multimedia-Komponenten spezifiziert und als Hierarchie dargestellt. Der neue Ansatz erlaubt es daher, multimediale Systeme nach einem Baukastensystem zu erstellen, indem Bausteine durch Bindung untereinander zu einer Anwendung zusammengesetzt werden. Nach der Verbindungsstruktur der multimedialen Anwendung können verschiedene Anwendungstypen unterschieden werden. Die Definition der Komponentenschnittstellen bezieht sich auf ein abstraktes Datenmodell für kontinuierliche Medien. Das Datenmodell ist eine eigenständige Weiterentwicklung der Ansätze von [Herrtw91] und [Gibbs94] und kann auch zur Realisierung der Komponenten verwendet werden. Multimediadaten wurden zunächst auf zwei Ebenen als Sequenz und Sequenzelemente modelliert. Daraus lassen sich bereits einige Funktionen auf den Daten ableiten, die von den Bausteinen realisiert werden müssen. Kennzeichnend für die Sequenzelemente ist, daß sie die Zeitparameter Zeitpunkt und Dauer besitzen und damit eine explizite Integration der Zeit in das Datenmodell realisieren. Aus diesen Parametern der Elemente können auch für die Sequenz die Parameter Zeitpunkt und Dauer abgeleitet werden. Somit könnte eine Sequenz selbst wieder Element einer Sequenz werden. Da diese Sequenzen von Sequenzen aber zum Teil schwer zu handhaben sind und zum Aufbau von sehr komplexen Verschachtelungen verleiten, wird in dieser Arbeit eine andere Erweiterung der Datenhierarchie, eine Liste, vorgestellt. Diese Erweiterung führt nur eine weitere Hierarchieebene oder Granularitätsstufe ein, ist aber durch die vorgegebenen Funktionen gleichmächtig wie die Verschachtelung der Sequenzen, im Operationsablauf aber leichter nachzuvollziehen. Die Liste repräsentiert die gröbste Granularitätsstufe. Diese ist mit der Titelfolge einer Schallplatte oder einer CD vergleichbar. Die einzelnen Teile haben zueinander nur eine lose Ordnung. In der ersten Verfeinerung der Granularität wird in jedem einzelnen Listenelement eine strenge zeitliche Ordnung gefordert; ein Listenelement ist eine Sequenz. In der zweiten Stufe der Verfeinerung, der Unterteilung der Sequenzen, treten die bereits bekannten Se quenzelemente auf. Die Daten werden im Ticker-Schrittgeber-Modell interpretiert. Dieses Modell erhält zwei Zeitebenen, den Ticker als Bezugssystem der Funktionen untereinander und den Schrittgeber als Steuerung der einzelnen Funktionen. Ein zweistufiges Uhrenmodell mir festgesetzten Operationen und Uhrenbeziehungen wird in dieser Arbeit neu eingeführt. Die Beziehung zwischen Schrittgeber und Ticker ist, daß ein Schritt nach einer bestimmten Anzahl von Ticks erfolgt. Der Startwert des Tickers kann frei gewählt werden, ebenso der Startwert des Schrittgebers. Für den Schrittgeber bestimmt sein Start-Tick, wann er beginnt fortzuschreiten. Ein Schrittgeber ist mit genau einer Sequenz verbunden, deren Start-Schritt beschreibt, bei welchem Schrittwert das erste Sequenzelement gültig wird. Die Start-Zeitpunkte der Elemente und ihre Dauern werden in Schritten gemessen. Das Datenmodell für Multimedia wurde in [Fritzsche95] veröffentlicht. Implementierungen Als Grundlage für die Entwicklung der Bausteine zur Integration kontinuierlicher Medien in verteilte Anwendungen wurden die Funktionen auf den Medien herangezogen. Diese sind in ihren einfachsten Formen die Grundfunktionen Perzeption, Präsentation und Speicherung der Medien, wobei die Speicherung in die Funktionen Schreiben in den Speicher und Lesen aus dem Speicher geteilt wird. Die durch die Perzeption festgelegten, oder künstlich erzeugten Mediendaten können zwischen den einzelnen Funktionen übertragen werden. Eine Bearbeitung der Daten ist beim Austausch zwischen den Funktionen möglich. Die Veränderung der Daten und ihr Bezug zu den Grundfunktionen wird durch die Verarbeitungsfunktionen der Typen f 1 bis f 5 beschrieben. Die Funktionen werden durch Operationen gesteuert, die aus dem Datenmodell abgeleitet werden. Insbesondere wird so auch die explizite Veränderung der Zeitparameter möglich. Somit bietet das Datenmodell eine geeignete Grundlage für jede Art der Verarbeitung kontinuierlicher Medien. Das entwickelte Modell unterstützt die Anwendungserstellung durch objektorientierte Ansätze auf den Ebenen der Konzeption, der Anwendungsspezifikation und der Komponentenentwicklung. Konzeptionell bietet das Funktionenmodell die schnelle und übersichtliche Darstellung der Anwendung. Die aus dem Funktionenmodell ableitbare Anwendungsspezifikation unterstützt die weitere Entwicklung durch Anwendungs- und Komponentenschablonen, sowie durch die vorgefertigte und erweiterbare Hierarchie der Schnittstellen und durch die Bibliotheken für Standardbausteine. Die Verwendung dieser Elemente der Anwendungsspezifikation läßt sich teilweise automatisieren. Das Ergebnis der Anwendungsspezifikation ist eine Menge von Komponenten, die alle vollständig spezifiziert sind. Diese Komponenten sind die funktionsorientierten Bausteine zur Integration kontinuierlicher Medien in verteilte Anwendungen. Im ersten Schritt wurde das vorgestellte Datenmodell mit seinen Operationen in einer objektorientierten Programmiersprache (C [Lipp91]) implementiert [Braun92]. Darauf aufbauend wurden verschiedene Anwendungsfunktionen und Normalisierungsoperationen entwickelt und für den Bereich Audio realisiert [Bast93]. Die von den Funktionen auf kontinuierlichen Medien abgeleiteten Bausteine werden, wie in der vorliegenden Arbeit ausführlich dargestellt, als Komponenten verteilter Anwendungen realisiert. Aus den verschiedenen Realisierungsebenen sollen hier zwei Beispiele hervorgehoben werden. Zunächst wird auf die Komponentenrealisierung eingegangen; danach folgt die Realisierung von Tickern und enger Kopplung. Diese beiden Punkte stellen zentrale Aufgaben des Ansatzes dar. Realisierung von Komponenten Die Realisierung der Komponenten gliedert sich in zwei Abschnitte. Der erste Abschnitt ist die Zerlegung einer Komponente in Standardobjekte nach [Zimm93]. Die Standardobjekte entstammen Kommunikationsklassen, Stub- und Dispatcherklassen, Anwendungsklassen und Kooperationsprotokollklassen. Die Objekte der Anwendungsklassen realisieren die Anwendungsfunktionalität der Komponente. Das Ausprogrammieren dieser Objekte stellt den zweiten Abschnitt der Komponentenrealisierung dar. Dazu liefert das entwickelte Datenmodell die Programmierunterstützung. Zur Abbildung der Spezifikationskonstrukte der Komponenten auf Implementierungskonstrukte wird in [Zimm93] eine Methode vorgestellt, die die unterschiedlichen Konstrukte für Schnittstellen, Kommunikationskontexte und Komponenten auf Klassen und Objekte abbildet. So entsteht eine Klassenhierarchie von C Klassen [Lipp91] für kommunikations-, anwendung-s und managementorientierte Objekte. Weiterhin wird in [Zimm93] ein Verfahren vorgestellt, durch das in Abhängigkeit von den Eigenschaften einer Komponente parallel ablaufende Datenflüsse in ein System von leichtgewichtigen Prozessen (Threads) transformiert werden können. Als Resultat gewinnt man eine modulare Softwarearchitektur der Komponente, die sich aus interagierenden Objekten und zugehörigen Threads zusammen setzt. In [Zimm93] werden folgende Objektklassen unterschieden: . Kommunikationsklassen . Stub- und Dispatcherklassen . Anwendungsklassen . Kooperationsprotokollklassen. Eine elementare Objektarchitektur aus diesen Klassen ist in Abbildung 54 dargestellt. Es gibt jeweils eine Realisierung für eine Supplier-Komponente und eine Consumer- Komponente. Die Anwendungsobjekte können bezüglich ihrer Funktionalität in initiierende und akzeptierende Objekte eingeteilt werden. Im Falle unidirektionaler Schnittstellen sind die Anwendungsobjekte auf der Konsumentenseite (z.B. Benutzerkomponente) für die Initiierung von Methoden an Schnittstellenobjekten verantwortlich. Beispielsweise ist ein Anwendungsobjekt innerhalb der Benutzerkomponente für die Initiierung der Steueroperationen verantwortlich. Im Falle von interaktiven Komponenten [Zimm93] erfolgt dazu ein Benutzerdialog mit einem interaktiven Benutzer. Also realisiert innerhalb der Benutzerkomponente das Anwendungsobjekt einen solchen Benutzerdialog. Anwendungsobjekte auf der Konsumentenseite stellen somit typischerweise keine eigenen Methoden bereit, sondern bestehen lediglich aus einem Konstruktor. Auf der akzeptierenden Seite, den Anbieter (Supplier), realisiert ein Anwendungsobjekt die Operationen an einer Schnittstelle. Dazu wird eine Methode accept benötigt, falls ein verbindungsorientierter Kommunikationskontext zugrunde liegt. Diese Methode dient der Behandlung eingehender Verbindungswünsche. In [Alireza94] werden verschiedene Komponentenrealisierungen ausführlich vorgestellt. Die Realisierung der Ticker und Schrittgeber stellt die Einbettung der zeitbezogenen Komponenten in ihre (Betriebssystem) Umgebung dar. Ähnlich, wie eine Komponente über den Socketmechanismus Zugang zum Kommunikationssystem erhält, erhält eine zeitbezogene Komponente über den Ticker-Schrittgeber-Mechanismus Zugang zum Zeitbezugssystem. Denn die Schrittgeber beziehen sich auf Ticker, Ticker aber auf die Systemzeit. Da auch die Systemzeit als Takt zur Verfügung gestellt wird, können Ticker und Schrittgeber wegen ihrer ähnlichen Funktionalitäten aus einer gemeinsamen Zeitgeberklasse abgeleitet werden. Im Anhang C ist die Deklaration dieser gemeinsamen Klasse angegeben. In einer Anwendung beziehen sich die Schrittgeber verschiedener Komponenten auf einen gemeinsamen Ticker. Dieser Ticker liegt in der Systemumgebung der den Komponenten gemeinsamen interaktiven Benutzerkomponente. Die interaktive Benutzerkomponente verteilt die Ticks über die Steuerschnittstellen an die Komponenten und realisiert so die enge Kopplung der Komponenten. Bei einer Tickrate von 600 Hz ist es nur innerhalb eines Systems sinnvoll jeden Tick als Ereignis zu verteilen. Anstatt nun zu jedem Tick ein Ereignis zu verteilen werden bei der Tickverteilung Tickwerte mit fester Rate verteilt, wobei diese Rate in die Größenordnung der Schritte fällt. Um die Übertragungsraten gemäß den Anforderungen an der Steuerschnittstelle klein zu halten, wird zu jedem Schritt nur ein Teil (1 Byte) des Tickwertes übertragen. Begonnen wird mit der Übertragung des höchstwertigen Bytes, so daß im letzten Schritt einer Tickerübertragung mit dem letzten Byte der genaue aktuelle Tickwert übertragen wird. Ähnliche Verfahren werden bereits bei anderen Synchronisations verfahren verwendet. Eine genaue Beschreibung sowie die Kodierung für die verschachtelte Übertragung von Tickwerten und SchnittstellenAufrufen wird in [Hesme93] vorgestellt. Weitere Entwicklung Zur Realisierung verteilter multimedialer Anwendungen, muß man die einzelnen verteilten Komponenten bestimmen und ihre Funktion beschreiben. Die Komponenten tauschen unter einander Steuerungsinformationen und Multimediadaten aus. Diese Daten und das beim Austausch verwendete Protokoll sollten allgemein standardisiert sein, um den Zusammen schluß heterogener Systeme zu ermöglichen. In der vorliegenden Arbeit wurde gezeigt, wie sowohl die Daten als auch das Zusammenspiel der Komponenten festgelegt werden können. Obwohl alle Geräteklassen und Geräte funktionen sowie verschiedene Werkzeuge entwickelt wurden, und das vorgestellte Modell die gesamte Entwicklung verteilter multimedialer Anwendungen unterstützt, ist dieses große Gebiet noch lange nicht erschöpfend behandelt. Eine Erweiterung der Managementschnittstellen und die Realisierung von komplexen Werkzeugen sind die vordringlichsten Aufgaben. Damit entsteht ein mächtiges Entwicklungswerkzeug für Multimediaanwendungen. Funktionsorientierte Bausteine zur Integration kontinuierlicher Medien in verteilte Anwendungen Eine weitere Aufgabe ist die genauere Untersuchung der Nebenbedingungen, die zur Unterscheidung der Funktionen der Typen f 1 bis f 5 führten. Aus diesen Untersuchungen sowie aus den Ergebnissen der Ticker- und Schrittgeber-Realisierung lassen sich dann genauer spezifizierte Anforderungen an die Betriebs- oder Kommunikations-Systeme ableiten.
This paper describes the development of a typesetting program for music in the lazy functional programming language Clean. The system transforms a description of the music to be typeset in a dvi-file just like TEX does with mathematical formulae. The implementation makes heavy use of higher order functions. It has been implemented in just a few weeks and is able to typeset quite impressive examples. The system is easy to maintain and can be extended to typeset arbitrary complicated musical constructs. The paper can be considered as a status report of the implementation as well as a reference manual for the resulting system.
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.
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.
It is well known that first order uni cation is decidable, whereas second order and higher order unification is undecidable. Bounded second order unification (BSOU) is second order unification under the restriction that only a bounded number of holes in the instantiating terms for second order variables is permitted, however, the size of the instantiation is not restricted. In this paper, a decision algorithm for bounded second order unification is described. This is the fist non-trivial decidability result for second order unification, where the (finite) signature is not restricted and there are no restrictions on the occurrences of variables. We show that the monadic second order unification (MSOU), a specialization of BSOU is in sum p s. Since MSOU is related to word unification, this is compares favourably to the best known upper bound NEXPTIME (and also to the announced upper bound PSPACE) for word unification. This supports the claim that bounded second order unification is easier than context unification, whose decidability is currently an open question.
This paper describes context analysis, an extension to strictness analysis for lazy functional languages. In particular it extends Wadler's four point domain and permits in nitely many abstract values. A calculus is presented based on abstract reduction which given the abstract values for the result automatically finds the abstract values for the arguments. The results of the analysis are useful for veri fication purposes and can also be used in compilers which require strictness information.
The extraction of strictness information marks an indispensable element of an efficient compilation of lazy functional languages like Haskell. Based on the method of abstract reduction we have developed an e cient strictness analyser for a core language of Haskell. It is completely written in Haskell and compares favourably with known implementations. The implementation is based on the G#-machine, which is an extension of the G-machine that has been adapted to the needs of abstract reduction.
Syntactic coindexing restrictions are by now known to be of central importance to practical anaphor resolution approaches. Since, in particular due to structural ambiguity, the assumption of the availability of a unique syntactic reading proves to be unrealistic, robust anaphor resolution relies on techniques to overcome this deficiency. In this paper, two approaches are presented which generalize the verification of coindexing constraints to de cient descriptions. At first, a partly heuristic method is described, which has been implemented. Secondly, a provable complete method is specified. It provides the means to exploit the results of anaphor resolution for a further structural disambiguation. By rendering possible a parallel processing model, this method exhibits, in a general sense, a higher degree of robustness. As a practically optimal solution, a combination of the two approaches is suggested.
In this paper we regard first the situation where parallel channels are disturbed by noise. With the goal of maximal information conservation we deduce the conditions for a transform which "immunizes" the channels against noise influence before the signals are used in later operations. It shows up that the signals have to be decorrelated and normalized by the filter which corresponds for the case of one channel to the classical result of Shannon. Additional simulations for image encoding and decoding show that this constitutes an efficient approach for noise suppression. Furthermore, by a corresponding objective function we deduce the stochastic and deterministic learning rules for a neural network that implements the data orthonormalization. In comparison with other already existing normalization networks our network shows approximately the same in the stochastic case but, by its generic deduction ensures the convergence and enables the use as independent building block in other contexts, e.g. whitening for independent component analysis. Keywords: information conservation, whitening filter, data orthonormalization network, image encoding, noise suppression.
This paper describes the problems and an adaptive solution for process control in rubber industry. We show that the human and economical benefits of an adaptive solution for the approximation of process parameters are very attractive. The modeling of the industrial problem is done by the means of artificial neural networks. For the example of the extrusion of a rubber profile in tire production our method shows good results even using only a few training samples.
The encoding of images by semantic entities is still an unresolved task. This paper proposes the encoding of images by only a few important components or image primitives. Classically, this can be done by the Principal Component Analysis (PCA). Recently, the Independent Component Analysis (ICA) has found strong interest in the signal processing and neural network community. Using this as pattern primitives we aim for source patterns with the highest occurrence probability or highest information. For the example of a synthetic image composed by characters this idea selects the salient ones. For natural images it does not lead to an acceptable reproduction error since no a-priori probabilities can be computed. Combining the traditional principal component criteria of PCA with the independence property of ICA we obtain a better encoding. It turns out that the Independent Principal Components (IPC) in contrast to the Principal Independent Components (PIC) implement the classical demand of Shannon’s rate distortion theory.
This paper proposes a new approach for the encoding of images by only a few important components. Classically, this is done by the Principal Component Analysis (PCA). Recently, the Independent Component Analysis (ICA) has found strong interest in the neural network community. Applied to images, we aim for the most important source patterns with the highest occurrence probability or highest information called principal independent components (PIC). For the example of a synthetic image composed by characters this idea selects the salient ones. For natural images it does not lead to an acceptable reproduction error since no a-priori probabilities can be computed. Combining the traditional principal component criteria of PCA with the independence property of ICA we obtain a better encoding. It turns out that this definition of PIC implements the classical demand of Shannon’s rate distortion theory.
Classically, encoding of images by only a few, important components is done by the Principal Component Analysis (PCA). Recently, a data analysis tool called Independent Component Analysis (ICA) for the separation of independent influences in signals has found strong interest in the neural network community. This approach has also been applied to images. Whereas the approach assumes continuous source channels mixed up to the same number of channels by a mixing matrix, we assume that images are composed by only a few image primitives. This means that for images we have less sources than pixels. Additionally, in order to reduce unimportant information, we aim only for the most important source patterns with the highest occurrence probabilities or biggest information called „Principal Independent Components (PIC)“. For the example of a synthetic picture composed by characters this idea gives us the most important ones. Nevertheless, for natural images where no a-priori probabilities can be computed this does not lead to an acceptable reproduction error. Combining the traditional principal component criteria of PCA with the independence property of ICA we obtain a better encoding. It turns out that this definition of PIC implements the classical demand of Shannon’s rate distortion theory.
In dieser Arbeit definieren wir ein Maß für den Grad der Mehrdeutigkeit (degree of ambiguity da) kontextfreier Grammatiken und Sprachen als die Anzahl der Ableitungsbäume in Abhängigkeit von der Länge n eines Wortes. Wir zeigen, dass es weder Sprachen noch zyklenfreie Grammatiken gibt, deren Mehrdeutigkeitsgrad stärker als 2£(n) wächst (wie z B. £(nn)). Aus [10] ist es außerdem bekannt, dass es keine Grammatiken (und somit keine Sprachen) gibt, deren Mehrdeutigkeit stärker als polynomiell, aber schwächer als exponentiell wächst (wie z. B. £(2pn). Deshalb untersuchen wir in dieser Arbeit hauptsächlich konstant mehrdeutige, polynomiell mehrdeutige und exponentiell mehrdeutige Grammatiken und Sprachen. Für jede feste, ganze Zahl k 2 N hat Maurer [8] die Existenz einer k-deutigen kontextfreien Sprache nachgewiesen. Durch Verwendung einer einfacheren Sprache, nämlich der Sprache Lk := fambm1 1 bm2 2 : : : bmk k jm;m1;m2; : : : ;mk ¸ 1; 9 i mit m = mig, und mit Hilfe von Ogden's Lemma1 erhalten wir einen wesentlich kürzeren Beweis. Ferner zeigen wir die Existenz exponentiell mehrdeutiger Sprachen. Wir zeigen, dass die Sprache L¤ { wobei L = faibicj ji; j ¸ 1g [ faibjciji; j ¸ 1g-exponentiell mehrdeutig ist, indem wir beweisen, dass das Wort (ah+h!bh+h!ch+h!)k mindestens 2k Ableitungen in jeder Grammatik G für L¤ hat, wobei k aus N ist und h die Konstante aus Ogden's Lemma für G ist. Für beliebig kleines c aus R+ entwerfen wir eine Grammatik Gc für L¤, so dass daGc · 2cn gilt. Somit gilt, dass die Sprache L¤ zwar exponentiell mehrdeutig ist, aber es gibt kein festes c aus R+ , so dass L¤ 2cn-deutig ist. Wir geben polynomiell mehrdeutige Grammatiken an und zeigen die Existenz von polynomiell mehrdeutigen Sprachen, indem wir mit Hilfe von Ogden's Lemma beweisen, dass die Anzahl der Ableitungsbäume eines Wortes der Länge n in jeder Grammatik für die Sprache Lk in der Größenordnung von (nk) liegt, wobei k eine Konstante aus N ist, und L := fambm1cbm2c : : : bmpcjp 2 N; m;m1;m2; : : : ;mp 2 N; 9i 2 f1; 2; : : : ; pg mit m = mig gilt. Durch Angabe einer O(nk){deutigen Grammatik zeigen wir schließlich, dass Lk polynomiell vom Grad k mehrdeutig ist. Außerdem entwerfen wir für jedes feste d aus R+ eine Grammatik Gd für L, so dass daGd · dn dn für genügend großes n ist.
In this paper we present a non-deterministic call-by-need (untyped) lambda calculus lambda nd with a constant choice and a let-syntax that models sharing. Our main result is that lambda nd has the nice operational properties of the standard lambda calculus: confluence on sets of expressions, and normal order reduction is sufficient to reach head normal form. Using a strong contextual equivalence we show correctness of several program transformations. In particular of lambdalifting using deterministic maximal free expressions. These results show that lambda nd is a new and also natural combination of non-determinism and lambda-calculus, which has a lot of opportunities for parallel evaluation. An intended application of lambda nd is as a foundation for compiling lazy functional programming languages with I/O based on direct calls. The set of correct program transformations can be rigorously distinguished from non-correct ones. All program transformations are permitted with the slight exception that for transformations like common subexpression elimination and lambda-lifting with maximal free expressions the involved subexpressions have to be deterministic ones.
A und B möchten digitale Unterschriften auf faire Weise austauschen, d.h. A soll genau dann eine Unterschrift von B erhalten, wenn B eine Unterschrift von A erhält. Der triviale Ansatz zum Austausch zweier Unterschriften, daß A seine Unterschrift an B sendet und dann B seine Unterschrift an A schickt, ist nicht fair, da B nach Erhalt der Unterschrift von A das Protokoll vorzeitig beenden oder eine ungültige Unterschrift senden kann. Bei den bekannten praktikablen Protokollen zum fairen Austausch unterteilen die Teilnehmer die Unterschriften in kleine Blöcke aus wenigen Bits und tauschen die Blöcke dann schrittweise aus. Diese Protokolle garantieren einerseits, daß man sofort überprüfen kann, ob ein erhaltener Block korrekt ist. Andererseits geben die bereits ausgetauschten Blöcke so wenig wie möglich über den restlichen Teil der Unterschrift preis. Versucht in diesem Fall ein Teilnehmer zu betrügen, indem er beispielsweise einen falschen Wert sendet, so kann der andere Teilnehmer dies unmittelbar bemerken und stoppen. Da die noch nicht ausgetauschten Blöcke fast nichts über den übrigen Teil der Unterschrift preisgeben, hat der Betrüger höchstens einen Block mehr als der ehrliche Teilnehmer erhalten. Ist die Blockgröße hinreichend klein, kann der ehrliche Teilnehmer den Nachteil durch Raten bzw. Probieren ausgleichen. In dieser Diplomarbeit entwickeln wir Protokolle zum fairen Austausch sogenannter Diskreter- Logarithmus-Unterschriften. Die bekannten praktikablen Protokolle zum Austausch dieses Unterschriftentyps verwenden als Sicherheitsvoraussetzung die Faktorisierungsannahme. Im Unterschied dazu beruht die Sicherheit unseres Austauschprotokolls auf der Diskreten- Logarithmus-Annahme und damit auf der des Unterschriftenverfahrens. Ferner erlauben unsere Protokoll die Herausgabe der Blöcke in beliebiger, auch vom Protokollverlauf abhängiger Reihenfolge, während die Reihenfolge bei den bisherigen Protokollen von vornherein festgelegt ist.
Um in verschiedenen Anwendungsumgebungen eingesetzt werden zu können, lässt die CORBA-Spezifikation einen weiten Spielraum für Implementierungen. Sollte CORBA in einem speziellen Umfeld eingesetzt werden, so war bisher eine Neu-Implementierung notwendig, da herkämmliche CORBA-Implementierungen nicht oder nur sehr eingeschränkt an spezielle Anwendungsumgebungen anpassbar sind. In dieser Arbeit wurde ein Ansatz für eine erweiterbare CORBA-Implementierung vorgestellt und implementiert.
A new approach to optimize multilevel logic circuits is introduced. Given a multilevel circuit, the synthesis method optimizes its area while simultaneously enhancing its random pattern testability. The method is based on structural transformations at the gate level. New transformations involving EX-OR gates as well as Reed–Muller expansions have been introduced in the synthesis of multilevel circuits. This method is augmented with transformations that specifically enhance random-pattern testability while reducing the area. Testability enhancement is an integral part of our synthesis methodology. Experimental results show that the proposed methodology not only can achieve lower area than other similar tools, but that it achieves better testability compared to available testability enhancement tools such as tstfx. Specifically for ISCAS-85 benchmark circuits, it was observed that EX-OR gate-based transformations successfully contributed toward generating smaller circuits compared to other state-of-the-art logic optimization tools.
Im Zeitraum 1. 11. 1993 bis 30. 3. 1997 wurden 1149 allgemeinchirurgische Intensivpatienten prospektiv erfaßt, von denen 114 die Kriterien des septischen Schocks erfüllten. Die Letalität der Patienten mit einem septischen Schock betrug 47,3%. Nach Training eines neuronalen Netzes mit 91 (von insgesamt n = 114) Patienten ergab die Testung bei den verbleibenden 23 Patienten bei der Berücksichtigung von Parameterveränderungen vom 1. auf den 2. Tag des septischen Schocks folgendes Ergebnis: Alle 10 verstorbenen Patienten wurden korrekt als nicht überlebend vorhergesagt, von den 13 Überlebenden wurden 12 korrekt als überlebend vorhergesagt (Sensitivität 100%; Spezifität 92,3%).
Durch zunehmende Vernetzung steigt auch das Interesse elektronische Wahlen mit Hilfe kryptographischer Methoden auf Rechnernetzen zu verwirklichen. In der folgendern Arbeit werden Wahlschemata behandelt, deren Ziel es ist, die gesamte Wahl auf einem Rechnernetz durchzuführen. Die Arbeit beschränkt sich auf Wahlen mit zwei Wahlvorschlägen. Auf Wahlen mit drei oder mehr Wahlvorschlägen wird nicht eingegangen. Im ersten Kapitel wird eine Einleitung in die elektronischen Wahlen gegeben. Im zweiten Kapitel wird das verwendete Modell eines Wahlschemas und die Anforderungen, bezüglich der die Wahlschemata untersucht werden, vorgestellt. Im dritten Kapitel werden die kryptographische Methoden für die folgenden Kapitel vorgestellt. Im vierten Kapitel werden zwei Wahlschemata betrachtet, deren Ansatz es ist, die Stimmen mit Hilfe von Schwellenwerten auf mehrere Behörden zu verteilen. Die Sicherheit der Wahlschemata in diesem Kapitel basiert auf dem diskreten Logarithmus. Im fünften Kapitel werden weitere Wahlschemata betrachet, bei denen die Wähler mit Hilfe von Verschlüsselungsmethoden ihre Stimmen an die Behörden senden. Die Sicherheit dieser Schemata basiert auf dem Wurzelziehen modulo einer zusammengesetzten Zahl mit unbekannter Faktorisierung. In diesem Kapitel lernen wir auch das erste quittungsfreie Wahlschema kennen. Im sechsten Kapitel werden Wahlschemata betrachtet, die das Konzept eines Mixes benutzen. Auch in diesem Kapitel lernen wir ein quittungsfreies Wahlschema kennen.
Diese Arbeit plädiert für eine rationale Behandlung von Patientendaten und untersucht dazu die Analyse der Daten mit Hilfe neuronale Netze etwas näher. Erfolgreiche Beispielanwendungen zeigen, daß die menschlichen Diagnosefähigkeiten deutlich schlechter sind als neuronale Diagnosesysteme. Für das Beispiel der neueren Architektur mit RBF-Netzen wird die Funktionalität näher erläutert und gezeigt, wie menschliche und neuronale Expertise miteinander gekoppelt werden kann. Der Ausblick deutet Anwendungen und Praxisproblematik derartiger Systeme an.
This paper describes the use of a Radial Basis Function (RBF) neural network in the approximation of process parameters for the extrusion of a rubber profile in tyre production. After introducing the rubber industry problem, the RBF network model and the RBF net learning algorithm are developed, which uses a growing number of RBF units to compensate the approximation error up to the desired error limit. Its performance is shown for simple analytic examples. Then the paper describes the modelling of the industrial problem. Simulations show good results, even when using only a few training samples. The paper is concluded by a discussion of possible systematic error influences, improvements and potential generalisation benefits. Keywords: Adaptive process control; Parameter estimation; RBF-nets; Rubber extrusion
The prevention of credit card fraud is an important application for prediction techniques. One major obstacle for using neural network training techniques is the high necessary diagnostic quality: Since only one financial transaction of a thousand is invalid no prediction success less than 99.9% is acceptable. Due to these credit card transaction proportions complete new concepts had to be developed and tested on real credit card data. This paper shows how advanced data mining techniques and neural network algorithm can be combined successfully to obtain a high fraud coverage combined with a low false alarm rate.
For the efficient management of large image databases, the automated characterization of images and the usage of that characterization for searching and ordering tasks is highly desirable. The purpose of the project SEMACODE is to combine the still unsolved problem of content-oriented characterization of images with scale-invariant object recognition and modelbased compression methods. To achieve this goal, existing techniques as well as new concepts related to pattern matching, image encoding, and image compression are examined. The resulting methods are integrated in a common framework with the aid of a content-oriented conception. For the application, an image database at the library of the university of Frankfurt/Main (StUB; about 60000 images), the required operations are developed. The search and query interfaces are defined in close cooperation with the StUB project “Digitized Colonial Picture Library”. This report describes the fundamentals and first results of the image encoding and object recognition algorithms developed within the scope of the project.
The prevention of credit card fraud is an important application for prediction techniques. One major obstacle for using neural network training techniques is the high necessary diagnostic quality: Since only one financial transaction of a thousand is invalid no prediction success less than 99.9% is acceptable. Due to these credit card transaction proportions complete new concepts had to be developed and tested on real credit card data. This paper shows how advanced data mining techniques and neural network algorithm can be combined successfully to obtain a high fraud coverage combined with a low false alarm rate.
Im heutigen Zahlungsverkehr übernehmen in zunehmendem Maße Zahlungen mit Kreditkarten eine entscheidende Rolle. Entsprechend der Verbreitung dieser Art des Zahlungsverkehrs nimmt ebenfalls der Mißbrauch mit diesem bargeldlosen Zahlungsmittel zu. Um die Verluste, die bei dem Kreditkarteninstitut auf diese Weise entstehen, so weit wie möglich einzudämmen, wird versucht, Mißbrauchstransaktionen bei der Autorisierung der Zahlungsaufforderung zu erkennen. Ziel dieser Diplomarbeit ist es zu bestimmen, in wie weit es möglich ist, illegale Transaktionen aus der Menge von Autorisierungsanfragen mit Hilfe adaptiver Algorithmen aufzudecken. Dabei sollen sowohl Methoden aus dem Bereich des Data-Mining, als auch aus den Bereichen der neuronalen Netze benutzt werden. Erschwerend bei der Mißbrauchsanalyse kommt hinzu, daß die Beurteilung der einzelnen Transaktionen in Sekundenbruchteilen abgeschlossen sein muß, um die hohe Anzahl an Autorisierungsanfragen verarbeiten zu können und den Kundenservice auf Seiten des Benutzers und des Händlers auf diese Weise zu optimieren. Weiter handelt es sich bei einem Großteil der bei der Analyse zu Verfügung stehenden Datensätze um symbolische Daten, also alpha-numerisch kodierte Werte, die stellvertretend für verschiedene Eigenschaften verwendet werden. Nur wenige der Transaktionsdaten sind analoger Natur, weisen also eine Linearität auf, die es erlaubt, "Nachbarschaften" zwischen den Daten bestimmen zu können. Damit scheidet eine reine Analyse auf Basis von neuronalen Netzwerken aus. Diese Problematik führte unter anderem zu dem verfolgten Ansatz. Als Grundlage der Analyse dienen bekannte Mißbrauchstransaktionen aus einem Zeitintervall von ungefähr einem Jahr, die jedoch aufgrund der hohen Anzahl nicht komplett als solche mit den eingehenden Transaktionen verglichen werden können, da ein sequentieller Vergleich zu viel Zeit in Anspruch nähme. Im übrigen würde durch einen einfachen Vergleich nur der schon bekannte Mißbrauch erkannt werden; eine Abstraktion der Erkenntnisse aus den Mißbrauchserfahrungen ist nicht möglich. Aus diesem Grund werden diese Mißbrauchstransaktionen mit Hilfe von Methoden aus dem Bereich des Data-Mining verallgemeinert und damit auf ein Minimum, soweit es die Verläßlichkeit dieser Datensätze zuläßt, reduziert. Desweiteren schließt sich eine Analyse der zu diesem Zeitpunkt noch nicht betrachteten analogen Daten an, um die maximale, enthaltene Information aus den Transaktionsdaten zu beziehen. Dafür werden moderne Methoden aus dem Bereich der neuronalen Netzwerke, sogenannte radiale Basisfunktionsnetze, verwendet. Da eine Mißbrauchsanalyse ohne eine entsprechende Profilanalyse unvollständig wäre, wurde abschließend mit den vorhanden Mitteln auf den zugrunde liegenden Daten in Anlehnung an die bisherige Methodik eine solche Profilauswertung und zeitabhängige Analyse realisiert. Mit dem so implementierten Modell wurde versucht, auf allgemeine Art und Weise, Verhaltens- beziehungsweise Transaktionsmuster einzuordnen und mit bei der Mißbrauchsentscheidung einfließen zu lassen. Aus den vorgestellten Analyseverfahren wurden verschiedene Klassifizierungsmodelle entwickelt, die zu guten Ergebnissen auf den Simulationsdaten führen. Es kann gezeigt werden, daß die Mißbrauchserkennung durch eine kombinierte Anwendung aus symbolischer und analoger Auswertung bestmöglich durchzuführen 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.
Context unification is a variant of second-order unification and also a generalization of string unification. Currently it is not known whether context uni cation is decidable. An expressive fragment of context unification is stratified context unification. Recently, it turned out that stratified context unification and one-step rewrite constraints are equivalent. This paper contains a description of a decision algorithm SCU for stratified context unification together with a proof of its correctness, which shows decidability of stratified context unification as well as of satisfiability of one-step rewrite constraints.
Wir betrachten das auf der Crypto '97 vorgeschlagene gitterbasierte Kryp- tosystem von Goldreich, Goldwasser und Halevi (GGH) [11]. Die Autoren veröffentlichten Challenges zu den Sicherheitsparametern 200, 250, 300, 350 und 400 [12]. Jeder Challenge besteht aus dem öffentlichen Schlüssel, sowie einem Ciphertext. Für den Angriff entwickeln wir numerisch stabile Gitterreduktionsalgorithmen, die es ermöglichen, das System in diesen Dimensionen anzugreifen. Es werden Methoden zur Orthogonalisierung, die sogenannten House- holder-Reflexionen und Givens-Rotationen behandelt, und eine praktikable Gleitpunkt-Arithmetik Version des LLL-Algorithmus nach Lenstra, Lenstra und Lov'asz [16] angegeben. Wir entwickeln und analysieren den LLL-Block- Algorithmus, der die Gitterreduktion in Blöcken organisiert. Die Gleitpunkt-Arithmetik Version des LLL-Block-Algorithmus wird experimentell auf das GGH-Schema angewendet und mit der LLL-Reduktion in den Dimensio- nen 100 bis 400 verglichen. Neben der besseren numerischen Stabilität ist die LLL-Block-Reduktion um den Faktor 10 bis 18 mal schneller als die gewöhnliche LLL-Reduktion. Das GGH-Kryptosystem wurde ebenfalls von Nguyen [22] angegriffen, und die ursprünglichen Nachrichten wurden bis in Dimension 350 rekonstruiert. Wir stellen weitere Angriffe auf das Kryptosystem vor. Es zeigt sich, dass die öffentlichen Parameter für erfolgreiche Angriffe benutzt werden können. Der private Schlüssel in der Dimension 200 wird nach ca. 10 Stunden rekonstruiert und Ciphertext-Attaken sind bis in Dimension 300 erfolgreich.
This thesis has explored how structural techniques can be applied to the problem of formal verification for sequential circuits. Algorithms for formal verification which operate on non-canonical gate netlist representations of digital circuits have certain advantages over the traditional techniques based on canonical representations as BDDs. They allow to exploit problem-specific knowledge because they can take into account structural properties of the designs being analyzed. This allows us to break the problem down into sub-problems which are (hopefully) easier to be solved. However, in the past, the main application of such structural techniques was in the field of combinational equivalence checking. One reason for this is that the behaviour of a sequential system does not only depend on its inputs but also on its internal states, and no concepts had been developed to-date allowing structural methods to deal with large sets of states. An important goal of this research was therefore to develop structural, non-canonical forms of representing the reachable states of a finite state machine and to develop methods for reachability analysis based on such representations. In order to reach this goal, two steps were taken. Firstly, a framework for manipulating Boolean functions represented as gate netlists has been established. Secondly, using this framework, a structural method for FSM traversal was developed serving as the basis for an equivalence checking algorithm for sequential circuits. The framework for manipulating Boolean functions represented as multi-level combinational networks is based on a new concept of an implicant in a multi-level network and on an AND/ORtype enumeration technique which allows us to derive such implicants. This concept extends the classical notion of an implicant in two-level circuits to the multi-level case. Using this notion, arbitrary transformations in multi-level combinational networks can be performed. The multi-level network implicants can be determined from AND/OR reasoning graphs, which are associated with an AND/OR reasoning technique operating directly on the gate netlist description of a multi-level circuit. This reasoning technique has the important property that it is complete, i.e. the associated AND/OR trees contain all prime implicants of a Boolean function at an arbitrary node in a combinational circuit. In other words, AND/OR graphs constructed for a network function serve as a representation of this function. A great advantage over BDDs is that AND/OR graphs, besides representing the logic function, also represent some structural properties of the analyzed circuitry. This permits to develop heuristics that are specially tailored for certain applications such as logic optimization or verification. Another advantage which is especially useful for logic optimization is the fact that the proposed AND/OR enumeration scheme is not restricted to the use of a specific logic alphabet such as B3 = {0, 1, X}. By using Roth’s D-calculus based on B5 = {0, 1, D, D-Komplement} permissible implicants can be determined. Transformations based on permissible implicants exploit observability don’t-care conditions in logic synthesis by creating permissible functions at internal network nodes. In order to evaluate the new structural framework for manipulating Boolean functions represented as gate netlists, several experiments with implicant-based optimization of multi-level circuits were performed. The results show that implicant-based circuit transformations lead to significantly better optimization results than traditional synthesis techniques. Next, based on the proposed structural methods for Boolean function manipulation, techniques for representing and manipulating the set of states of a sequential circuit have been developed. The concept of a “stub circuit” was introduced which implicitly represents a set of state vectors as the range of a multi-output function given as a gate netlist. The stub circuit is the result of an existential quantification operation which is obtained by functional decomposition using implicant-based netlist transformations and a network cutting procedure. Using this existential quantification operation, a new structural FSM traversal algorithm was formulated which performs a fixed point iteration on the set of reachable states represented by the stub circuit. The proposed approach performs a reachability analysis of the states of a sequential circuit. It operates on gate netlists and naturally allows to incorporate structural properties of a design under consideration into the reasoning. Therefore, structural FSM traversal is an interesting alternative to traditional symbolic FSM traversal, especially in those applications of formal verification, where structural properties can be exploited. Structural FSM traversal was applied to the problem of sequential equivalence checking. Here, structural similarities between the designs to be compared can effectively reduce the complexity of the verification task. The FSM to be traversed is a special product machine called sequential miter. The special structural properties of this product machine have made it possible to formulate an approximate algorithm for structural FSM traversal, called record and play(). This algorithm uses an approximation on the reachable state set represented by the stub circuit which is very beneficial for performance. Instead of calculating the stub circuit using the exact algorithm, implicant-based transformations directly using structural design similarities are performed. These transformations, together with existential quantification implemented by the cutting procedure, lead to an over-approximation of the reachable state set. By this overapproximation, only such unreachable product states are added to the set of states represented by the stub circuit which are unreachable at the current point in time but which are nevertheless equivalent. Therefore, more product states are added to the set of reachable states sometimes leading to drastic acceleration of the traversal, i.e. the fixed point is reached in much fewer steps. The algorithm record and play() was applied to the problem of checking the equivalence of a circuit with its optimized and retimed version. Retiming is a form of sequential circuit optimization which can radically alter the state encoding of a circuit. Traditional FSM traversal techniques often fail because the BDDs needed to represent the reachable state set and the transition relation of the product machine become too large. Experiments were conducted to evaluate the performance of record and play() on a standard set of sequential benchmark circuits. The algorithm was capable of proving the equivalence of optimized and retimed circuits with their original versions, some of which (to our knowledge) have never before been verified using traditional techniques like symbolic FSM traversal. The experimental results are very promising. Future research will therefore explore how structural FSM traversal can be applied to model checking.
The thesis in general deals with CORBA, the Common Object Request Broker Architecture. More specifically, it takes a look at the server-side, where object adapters exist to aid the developer in implementing objects and in dealing with request processing. The new Portable Object Adapter was recently added to the CORBA 2.2 standard. My task was the implementation of the POA in MICO and the examination if (a) the POA specification is sensible and (b) in which areas it improves over the old Basic Object Adapter. After introducing distributed platforms in general and CORBA in particular, the thesis' main two chapters are a detailed abstract examination ("Design") of the POA design and their relization ("Implementation"), highlighting the potential trouble spots, persistence and collocation.
We present the FPGA implementation of an algorithm [4] that computes implications between signal values in a boolean network. The research was performed as a masterrsquos thesis [5] at the University of Frankfurt. The recursive algorithm is rather complex for a hardware realization and therefore the FPGA implementation is an interesting example for the potential of reconfigurable computing beyond systolic algorithms. A circuit generator was written that transforms a boolean network into a network of small processing elements and a global control logic which together implement the algorithm. The resulting circuit performs the computation two orders of magnitudes faster than a software implementation run by a conventional workstation.
This paper presents a new timing driven approach for cell replication tailored to the practical needs of standard cell layout design. Cell replication methods have been studied extensively in the context of generic partitioning problems. However, until now it has remained unclear what practical benefit can be obtained from this concept in a realistic environment for timing driven layout synthesis. Therefore, this paper presents a timing driven cell replication procedure, demonstrates its incorporation into a standard cell placement and routing tool and examines its benefit on the final circuit performance in comparison with conventional gate or transistor sizing techniques. Furthermore, we demonstrate that cell replication can deteriorate the stuck-at fault testability of circuits and show that stuck-at redundancy elimination must be integrated into the placement procedure. Experimental results demonstrate the usefulness of the proposed methodology and suggest that cell replication should be an integral part of the physical design flow complementing traditional gate sizing techniques.
In der vorliegenden Diplom-Arbeit wurde das in [19] vorgeschlagene Modell zur Partitionierung hybrider Systeme diskutiert und die Anwendbarkeit verschiedener verschiedener Optimierungsverfahren auf das Problem untersucht.
Hierbei wurde der Systemgraph um die Ein-/Ausgabe-Blöcke erweitert, damit der Systemgraph eine eine konsistente Erweiterung des des Graphen-Modells darstellt. Weiterhin wurden die Probleme und Einschränkungen aufgezeigt, die sich bei der Abbildung eines hybriden Systems auf den Systemgraphen ergeben.
Gegenstand der Arbeit ist ein Gleichheitskalkül für den Kern einer nicht-strikten funktionalen Programmiersprache. Funktionale Programmiersprachen unterstützen bestens die Prinzipien Abstraktion, Einkapselung, Hierarchiesierung und Modularisierung, die gemeinhin als Grundelemente des Software-Engineering betrachtet werden. Darüber hinaus bieten funktionale Programmiersprachen aufgrund ihrer Entwicklung aus dem Lambda-Kalkül eine große Nähe zu mathematischen Modellen. Daher besitzen sie im Bereich der Programmverifikation ausgeprägte Vorteile gegenüber imperativen oder objekt-orientierten Programmiersprachen. In der Arbeit wird nun ein Gleichheitsbegriff für Ausdrücke in funktionalen Programmiersprachen entwickelt und dessen Praktikabilität durch die Implementierung eines Beweisers untermauert. Dieser Gleichheitsbegriff ist die kontextuelle Gleichheit, die Ausdrücke aufgrund ihres Terminierungsverhaltens als Unterprogramme in allen möglichen Kontexten einordnet. Kontextuelle Gleichheit wird in Kapitel 2 vorgestellt, nachdem der klassische und der sogenannte "lazy" Lambda-Kalkül eingeführt wurden. Kapitel 3 enthält einen Überblick über die funktionale Programmierung, da auch die Implementierung des o.g. Beweisers in einer funktionalen Programmiersprache, nämlich Haskell, durchgeführt wird. In Kapitel 4 wird die funktionale Kernsprache, die Gegenstand der Untersuchung sein wird, beschrieben. Sie enthält alle wesentlichen Elemente wie z.B. Funktionsdefinition und -anwendung sowie Datentypen. Im selben Kapitel wird auch der Gleichheitsbegriff für diese Kernsprache definiert. Kapitel 5 schließlich entwickelt auf Basis der zuvor erfolgten Definitionen einen Kalkül für den Gleichheitsbeweis. Außerdem wird in diesem Kapitel auch die Umsetzung dieses Gleichheitskalküls präsentiert. Aus der Dissertation von Marko Schütz werden hierbei Erkenntnisse über die Kontextanalyse verwendet, um erfüllende Belegungen von freien Variablen zu berechnen. Die Arbeit schließt mit Beispielanalysen und Meßwerten sowie einer Diskussion der Ergebnisse und möglicher Erweiterungen.
Wir betrachten in dieser Diplomarbeit die Sicherheit des ringbasierten Public Key Kryptosystems NTRU, das 1996 von J. Hoffstein, J. Pipher und J.H. Silverman vorgeschlagen wurde. Dieses Kryptosystem bietet schnelle Kodierung und Dekodierung in Laufzeit O(n exp 2) bei kleinem Sicherheitsparameter n. Die Sicherheit des Systems beruht auf einem Polynomfaktorisierungsproblem (PFP)im Polynomring Zq[X]/(X exp n -1). Das PFP wurde von Coppersmith und Shamir auf ein Kürzestes Vektor Problem im Gitter Lcs reduziert. Die neuen Ergebnisse dieser Arbeit bauen auf dem Gitter Lcs auf. Wir betrachten die Nachteile von Lcs und konstruieren verbesserte Gitterbasen zum Angriff auf das NTRU-Kryptosystem. Dabei nutzen wir Strukturen des Polynomrings Zq[X]/(X exp n -1) und der geheimen Schlüssel aus. Durch die neuen Gitterbasen wird der Quotient aus der Länge des zweitkürzesten und der Länge des kürzesten Gittervektors vergrößert. Da wir Approximationsalgorithmen zum Finden eines kürzesten Vektors verwenden, beschleunigt dies die Attacken. Wir präsentieren verschiedene Methoden, wie man die Dimension der Gitterbasen verkleinern kann. Durch die verbesserten Gitterattacken erhalten wir eine Cryptanalyse des NTRU-Systems in der vorgeschlagenen mittleren Sicherheitsstufe. Beträgt die Zeit zum Brechen eines Public-Keys unter Verwendung der Coppersmith/Shamir-Basis 1 Monat, so verringert sich die Laufzeit durch einen kombinierten Einsatz der neuen Gitterbasen auf ca. 5 Stunden auf einem Rechner und bei Parallelisierung auf ca. 1:20 Stunde auf 4 Rechnern. Wir erwarten, daß die neuen Methoden NTRU in hoher Sicherheitsstufe n = 167 brechen, obwohl für dieses n bisher nur "schwache" Schlüssel gebrochen wurden. Trotz signifikanter Verbesserungen deuten die experimentellen Ergebnisse auf ein exponentielles Laufzeitverhalten bei steigendem Sicherheitsparameter n hin. Der Laufzeitexponent kann allerdings gesenkt werden, so daß man n größer wählen muß, um Sicherheit gegenüber den neuen Attacken zu erzielen. Auch wenn das NTRU-Kryptosystem nicht vollständig gebrochen wird, verliert es seinen größten Vorteil gegenüber anderen Public Key Kryptosystemen: Die effiziente Kodierung und Dekodierung bei kleinem Sicherheitsparameter n.
In contrast to the symbolic approach, neural networks seldom are designed to explain what they have learned. This is a major obstacle for its use in everyday life. With the appearance of neuro-fuzzy systems which use vague, human-like categories the situation has changed. Based on the well-known mechanisms of learning for RBF networks, a special neuro-fuzzy interface is proposed in this paper. It is especially useful in medical applications, using the notation and habits of physicians and other medically trained people. As an example, a liver disease diagnosis system is presented.
Wir haben Interaktion in der Kommunikationskomplexität untersucht und dabei die drei Modi probabilistische, (beschränkt) nichtdeterministische und quantenmechanische Kommunikation betrachtet. Bei allen drei Modi haben wir herausgefunden, dass Interaktion für Effzienz oft unerlässlich ist, im nichtdeterministischen Fall gibt es eine Abhängigkeit zwischen dem Einfluss der Interaktion und der erlaubten Anzahl der nichtdeterministischen Ratebits. Abgesehen von dem erreichten besseren Verständnis des Kommunikationsmodells haben wir verschiedene Anwendungen auf andere Berechnungsmodelle beschrieben, bei denen untere Schranken der Kommunikation zu unteren Schranken für andere Ressourcen in diesen Modellen geführt haben. Ein Beispiel eines kommunikations- und interaktionsbeschränkten Modells sind endliche Automaten, welche wir in allen drei Modi untersucht haben. Ein weiteres Beispiel sind Formeln, für die wir eine Verbindung zwischen Einweg Kommunikation und Formellänge herstellen konnten. Diese Verbindung führte zu unteren Schranken für probabilistische, nichtdeterministische und Quanten Formeln. Dabei sind die unteren Schranken für Quanten Formeln und probabilistische Formeln im wesentlichen gleich. Für monotone Schaltkreise haben wir gezeigt, wie nichtdeterministisches Raten die Tiefe drastisch reduzieren kann, und wie eine geringfügige Einschränkung der nichtdeterministischen Ratebits zu einer Tiefenhierarchie führt. Insgesamt lässt sich feststellen, dass die Schwäche interaktionsbeschränkter Kommunikation mathematisch nachvollziehbar ist. Außerdem scheint ein solches Verhalten in der Welt einfacher Berechnungsmodelle häufig aufzutreten. Oder anders gesagt, viele Berechnungsmodelle sind deshalb einfacher zu verstehen, weil sie durch interaktionsbeschränkte Kommunikation analysierbar sind.
Schemaevolution in objektorientierten Datenbanksystemen auf der Basis von Versionierungskonzepten
(2000)
Gegenstand dieses Kapitels ist zunächst die Zusammenfassung der in dieser Arbeit erreichten Ergebnisse im Hinblick auf die ursprüngliche Zielsetzung, also die Unterstützung von Schema evolution in objektorientierten Datenbanksystemen. Anschließend folgen Überlegungen, welche der erzielten Ergebnisse zur Lösung von Problemen in anderen Arbeitsbereichen herangezogen werden können und auf welche Weise dies geschehen kann. Die Arbeit schlie?t mit einem Ausblick auf weitere Arbeiten im von uns bearbeiteten Themengebiet. Erreichte Ziele Ausgangspunkt unserer Arbeit war die Beobachtung, dass die Evolution von Datenbankschema ta, welche zur Anpassung an sich ändernde funktionale und nichtfunktionale Anforderungen 130 der Diskurswelt benötigt wird, durch die gegenwärtig verfügbaren Modelle und Systeme nicht adäquat unterstützt wird. Wir stellten daraufhin die Hypothese auf, dass ein Modell auf der Basis der Versionierung von Schemata mit einer entsprechenden Abbildung der Änderungen auf die Objektebene dies leisten kann. Wir konnten in dieser Abhandlung zeigen, dass das nach diesen Gesichtspunkten entworfene COASTModell die daran gestellten Erwartungen erfüllt und Sche maänderungen in Gegenwart existierender Objekte und Applikationen erfolgreich realisierbar sind. Die einzelnen Arbeitsschritte und Ergebnisse ergaben sich dabei wie folgt: - Problemanalyse und grober Modellentwurf: Die Notwendigkeit einer Unterstützung für Schemaevolutionsprozesse ergab sich aus der Beobachtung, dass vor allem moderne An wendungsbereiche eine flexible Anpassung an ständig veränderliche Umstände erfordern. Während des Betriebs einer Datenbank aufkommende Änderungsanforderungen lassen sich zur Entwurfszeit nicht vorhersehen und sind im Rahmen fest vorgegebener Datenbanksche mata nur schwerlich adäquat umsetzbar. Wir konnten in diesem Zusammenhang bei den vorhandenen Systemen zur Unterstützung der Schemaevolution das Fehlen einer Berück sichtigung im Betrieb beøndlicher Datenbankapplikationen feststellen. Gleichzeitig blieben Anforderungen an flexibel koppelbare Datenbankzustände für verschiedene Schemaausprä gungen bisher unberücksichtigt. Das an dieser Stelle grob skizzierte Modell zur Lösung des Problems beruhte folgerichtig auf dem Einsatz von Versionierungskonzepten auf der Ebene der Datenbankschemata. Solche Versionierungskonzepte hatten ihre Fähigkeiten zur Unterstützung von Evolutionsprozessen insbesondere auch im Zusammenhang mit Entwurfsaufgaben bereits zuvor sowohl auf der Ebene kompletter Datenbanken als auch auf der einzelner Objekte nachgewiesen. - Untersuchung bestehender Lösungsansätze: Wir konnten für das Lösungsmodell vier ele mentare Aspekte identiøzieren: Durchführung von Änderungen auf Schemaebene unter Verwendung von Versionierungskonzepten, Erzeugung und Verwaltung der Abhängigkeits beziehungen zwischen den Schemaversionen, Abbildung der Änderungen auf die Objekt ebene sowie flexible Konzepte zur Steuerung und Durchführung der Objektpropagation. Da kein Modell existierte, das all diese Punkte berücksichtigt, mussten wir uns in der Literatur recherche auf Ansätze beschränken, die sich mit einzelnen Aspekten unserer Aufgabenstel lung befassen. Aus dieser Perspektive stellt sich unser Modell zu einem Teil als Integration früherer Arbeiten dar. Zum anderen Teil beruht unser Modell in den grundlegenden Aspek ten der Behandlung von Ableitungsbeziehungen sowie der Steuerung und Durchführung der Objektpropagation auf gänzlich neuen Ansätzen. Die wesentliche Erkenntnis dieses Arbeitsschrittes ist somit die Feststellung, dass einerseits verschiedene Konzepte bestehen der Ansätze übernommen werden konnten, obwohl keine Arbeit alle Anforderungen an unser Modell erfüllte, und andererseits einige Aspekte bislang nahezu vollständig ignoriert wurden. - Detaillierte Modellbildung: Aufgrund der Erkenntnisse über bestehende Arbeiten entwarfen wir in diesem Arbeitsschritt COAST als Modell zur Durchführung von Schemaänderun gen in Anwesenheit von Objekten und Applikationen. Grundbestandteile unseres Ansatzes sind die Schemaversionen, die vergleichbar einer Konøgurationsverwaltung semantisch in Zusammenhang stehende Klassenversionen zu konsistenten Teilstrukturen zusammenset zen. Für die Durchführung von Schemaänderungen haben wir zwei grundsätzlich verschiedene Wege analysiert und resultierende Konsequenzen studiert. Dem internen Ansatz folgend wird eine von dem jeweiligen Einsatzgebiet des Systems unabhängige, fest vorgegebene und konzeptionell vollständige Taxonomie von Schemaänderungsprimitiven bereitgestellt, de ren Semantik a priori bekannt ist und demzufolge bei allen weiteren Schritten auf Schema und Objektebene berücksichtigt werden kann. Der externe Ansatz, als Alternative, erlaubt die Durchführung applikationsspezifischer Schemaänderungen und erhöht damit die Flexi bilität. Der Prozess des Einbringens extern erstellter Schemaversionen in das System kann dabei in vielfältiger Weise unterstützt werden. Bemerkenswerterweise fanden sich die auf Schemaebene angewandten Konzepte analog auf Instanzenebene wieder und zwar bei den Objektversionen, deren Zusammenhang sich in Form von Propagationsgraphen widerspiegelt ähnlich den Ableitungsbeziehungen auf Sche maebene. Die Steuerung der Objektpropagation sowohl zum Zeitpunkt der Schemaände rung als auch später, als Reaktion auf verändernde Datenbankzugrioee ist im behandelten Umfeld mit Sicherheit einzigartig. - Validierung des Modells: Aussagen zur Tauglichkeit des Modells im Hinblick auf seine Kon zeptionsziele konnten wir durch eine Evaluierung anhand unserer sehr detailliert beschrie benen Vorgaben erhalten. Damit ist gleichzeitig ein Vergleich mit bisherigen Lösungswegen insgesamt und mit einzelnen Vertretern davon gegeben. Die Evaluierung konnte in allen Aspekten belegen, dass das COASTModell zur Unterstützung von Schemaänderungen in Benutzung befindlicher Datenbanksysteme gut geeignet ist. Wir möchten an dieser Stelle nochmals betonen, dass COAST in vielerlei Hinsicht einfach erweitert werden kann und im Vergleich zu bisherigen Systemen durch erheblich flexiblere Möglichkeiten der Einflussnahme und eine verbesserte Tauglichkeit ausgezeichnet wird. Zu nächst sind sowohl die hier vorgestellte Schemaänderungstaxonomie als auch die damit ver bundene Propagationssprache vielfältig um komplexe Operationen erweiterbar. Weiterhin kann die Menge verwendbarer Propagationsflags insbesondere mit Blick auf das Verhalten bei komplexen Schemaänderungen hin ergänzt werden. Aber bereits die hier dargestell ten Möglichkeiten der Propagationssteuerung decken das gesamte Spektrum von isolierten Schemaversionen am einen Ende bis hin zur kompletten Propagation am anderen Ende ab. In Erweiterung der Konzepte auf der Basis von Sichtenmechanismen können durch die Objektversionierung beliebige Änderungen des Datenbankzustandes durchgeführt wer den. Damit wird ein erheblicher Beitrag für die Transparenz der Schemaevolution für die Applikationsentwickler geleistet. Die für die Tauglichkeit wichtigste Eigenschaft besteht zweifelsfrei in der Möglichkeit, be stehende Applikationen auch noch nach der Durchführung von Schemaänderungen ohne Anpassung weiterverwenden zu können. Damit erweitert sich der Einsatzbereich von Sche maänderungen auf sehr große, komponentenbasierte Systeme auf der Basis zahlreicher Einzelapplikationen. - Hinweise für den Datenbankentwurf: Um den Schemaversionierungmechanismus adäquat einsetzen zu können, erweisen sich Aussagen über den Schemaänderungsprozess als notwen dig. Daher haben wir diesen Prozess systematisch in Teilschritte zerlegt, die nacheinander betrachtet werden können. Bereits während der Modellbildung haben wir dort, wo sich ei nem Schemaentwickler Alternativen im Umgang mit COAST bieten, diese aufgezeigt und ihre jeweiligen Konsequenzen untersucht. Im Ergebnis resultiert für den Schemaentwick ler im Vergleich zu unversionierten Systemen ein zusätzlicher Spezifikationsaufwand. Dies ist jedoch für die Erreichung unserer Ziele unvermeidbar und der Gesamtaufwand für die Durchführung einer Schemaänderung reduziert sich dem Versionierungskonzept folgend er heblich, nicht zuletzt, weil aus der Sicht der Applikationsentwickler die volle Transparenz gewährleistet wird. - Realisierungsbetrachtungen: Um Erkenntnisse über den Realisierungsaufwand sowie die zu erwartenden Leistungsmerkmale zu erhalten, haben wir zweierlei Ansätze für eine pro totypische Realisierung untersucht. Zum einen haben wir einen Schemaversionierungsme chanismus als Aufsatz auf dem kommerziellen Objektdatenbanksystem O 2 implementiert. Auch wenn sich dies konzeptionell als möglich erwiesen hat, so haben sich dort an mehre ren Stellen erhebliche Einbußen bezüglich der Transparenz gezeigt [Wöh96]. Daher haben wir uns verstärkt mit dem zweiten, deutlich aufwendigeren Weg beschäftigt: die Eigenent wicklung eines kompletten, objektorientierten Datenbankmanagementsystems, bei dem die Konzepte von COAST transparent und von Anfang an im Kern integriert werden konnten. Die Realisierung der verzögerten Propagation kann bei realistischen Zugriffsprofilen mit einer gewissen Lokalität bezüglich der Schemaversionen größenordnungsmäßig mit unver sionierten Systemen vergleichbare Laufzeiten erreichen. Konzeptionell bedingt muss zwar ein größerer Platzbedarf als bei einem statischen System (ohne Schemaänderungen) in Kauf genommen werden. Im Vergleich zu anderen Konzepten der Schemaevolution, etwa den Ansätzen auf der Basis von isolierten Datenbanken oder mit materialisierten Sichten tritt aber kein Mehraufwand auf. In all diesen Varianten wird, ähnlich wie bei Puffern absichtlich Platz zugunsten einer erhöhten Zugriffsgeschwindigkeit investiert. Je ähnlicher sich verschiedene Schemaversionen sind und je intensiver die Propagation zwischen ihnen demnach ausfällt, desto besser sind die Voraussetzungen für platzsparende Mechanismen auf der Basis von mehreren Schemaversionen gemeinsam genutzter Objektversionen. In die sem Zusammenhang konnten wir eine Reihe von Verbesserungsmöglichkeiten identifizieren, die den COASTPrototyp Systemen auf der Basis von Sichtenmechanismen gleichstellen würden. Übertragbarkeit der Ergebnisse Die Tragfähigkeit der Konzepte des COASTModells für die Unterstützung evolutionärer Sche maänderungen haben wir erfolgreich belegen können. Im folgenden sprechen wir noch einige Möglichkeiten an, die in dieser Abhandlung gewonnenen Erkenntnisse auch im Zusammenhang mit anderen Konzepten einzusetzen. - Abschnitt 2.2 hatte allgemeine Versionierungskonzepte vorgestellt, wie sie typischerweise auf Objekte angewendet werden, um deren inhaltliche Evolution abzubilden. Wir haben dieselben Konzepte in der vorliegenden Arbeit auf Schemata als Instanzen der Metaebene angewendet, um deren evolutionäre Entwicklung zu unterstützen. Dabei hat sich die Ver wendung versionierter Datenbankobjekte ebenfalls als sehr hilfreich erwiesen. Die Versio nen eines Objektes bei der Schemaversionierung repräsentieren ein Objekt in verschiedenen Datentypen. Von Situationen abgesehen, in denen das Modifikationsflag abgeschaltet ist und Änderungen daher gewollt nicht propagiert werden, repräsentieren die Versionen eines Objektes denselben logischen Objektwert. Damit unterscheiden sich die hier verwendeten Objektversionen von denen der klassischen Objektversionierung. Letztere stellen nämlich verschiedene logische Objektwerte dar, die allerdings alle demselben Datentyp entsprechen. Die vorangegangene, vergleichende Betrachtung zeigt einerseits, dass die beiden Formen der Versionierung unterschiedliche Ziele verfolgen, und andererseits legt sie die Vermutung nahe, dass es sich um orthogonale und damit gewinnbringend kombinierbare Ansätze han delt. Verschiedene Typen zur Darstellung desselben logischen Objektwertes hier stehen verschiedenen Objektwerten desselben Typs dort gegenüber. Tatsächlich lässt sich unser Ansatz um Mechanismen zur Objektversionierung erweitern, indem jede unserer Objektversionen nun durch verschiedene klassische Objektversionen ersetzt wird. Damit entsteht ein zweidimensionaler Raum von Objektversionen: entlang der einen Dimension liegt jeweils ein logischer Objektwert in verschiedenen Typen, entlang der anderen Dimension liegen jeweils verschiedene logische Zustände eines Objektes, die durch denselben Typ repräsentiert werden. Um die Kombination der beiden Versionierungskonzepte zu erreichen, sind allerdings noch einige Fragen näher zu untersuchen. Diese beschäftigen sich beispielsweise mit dem Zu sammenhang zwischen den Objektversionen entlang der beiden Dimensionen und mit der Propagation versionierter Objekte. Hier ist beispielsweise zu klären, ob alle, oder wenn nicht welche der logischen Objektwerte eines Objektes in andere Schemaversionen zu pro pagieren sind. Schließlich bietet die Realisierung des integrierten Gesamtkonzeptes zahl reiche Ansatzpunkte für technische Optimierungen und erfordert diese auch, um sowohl den Zeitaufwand für die Propagation als auch den Platzbedarf für die Speicherung der zweidimensional versionierten Objekte zu reduzieren. - Wir waren in der Literaturrecherche auf das Sichtenkonzept als Grundlage zur Simulati on von Schemaänderungen eingegangen und hatten dabei einige Deøzite bei der Lösung der hier betrachteten Aufgabenstellung identiøziert. Dies impliziert jedoch keine Aussa ge über die Tragfähigkeit von Sichten in dem Umfeld, für das sie ursprünglich konzipiert worden waren. Aufgrund der mit COAST erzielten Transparenz, die eine Schemaversion nach außen hin wie ein Schema eines unversionierten Systems erscheinen läßt, kann ein Sichtenkonzept auf dem COASTModell aufgesetzt werden. Konzeptionelle Schwierigkei ten sind durch die Kombination von Sichten und Schemaversionen nicht zu erwarten: Beim Ableiten neuer Schemaversionen können auf den Vorgängern definierte Sichten bei Bedarf mitintegriert werden und das Anlegen, Ändern und Löschen von Sichten kann durch die Primitive des Sichtenmechanismus erfolgen. In einem beide Konzepte integrierenden System kann entsprechend der gestellten Anforderungen entschieden werden, ob diese besser durch Anlegen einer neuen Sicht oder durch Ableiten einer neuen Schemaversion erfüllt werden. - Einen Schritt über die Integration eines separaten Sichtensystems hinaus geht die Über legung, ob Sichten nicht sogar durch Schemaversionen simuliert werden können. Damit wäre dann auch eine vollständig homogene Integration beider Konzepte in einem System erreicht. Um diese Überlegung zu verfolgen, betrachten wir die konzeptionellen Kompo nenten eines Sichtensystems und analysieren kurz, wie diese auf die Konzepte von COAST abgebildet werden können. Die für den Schemaentwickler zu verwendende Schnittstelle eines Sichtensystems ist durch die Sichtendefinitionssprache gegeben. Die dort zur Verfügung stehenden Konstrukte die nen zunächst der Definition des Sichtschemas und sind insoweit durch die Primitive der COASTODL abgedeckt. Darüber hinaus bestimmt eine Sichtendefinition die Extension der Sichtklassen durch Angabe je einer Anfrage, wobei das Ergebnis dieser Anfrage dem Schema der definierten Sichtklasse entsprechen muss bzw. dieses implizit erst bestimmt. Um diesen Teil eines Sichtenkonzeptes zu simulieren, sind in COAST zwei Erweiterungen not wendig. Zum einen wird eine Anfragesprache benötigt. Diese wäre für die Vervollständigung von COAST sowieso erforderlich und könnte sich konzeptionell sehr stark an bestehenden objektorientierten Anfragesprachen orientieren. Ein Anfragesystem muss zu jeder Anfrage zunächst das Schema ihres Resultates ermitteln und dieses könnte dann mit den Primiti ven der COASTODL erstellt werden. Daraufhin muss das Anfragesystem die eigentliche Durchführung der Anfrage auf der Datenbank erledigen. Dies beschreibt gleichzeitig die zweite in COAST erforderliche Erweiterung. Für die Durchführung der Anfrage und ins besondere der darin ggf. enthaltenen Selektion von Objekten müsste eine entsprechende Erweiterung der Propagationssprache von COAST vorgenommen werden. Änderungen von Objekten in Sichtklassen sind aufgrund des Sichtenänderungsproblems i.Allg. nicht durchführbar, da in der Sichtendefinitionssprache keine Möglichkeit besteht, die Auswirkungen einer solchen Änderung auf die Objekte des Basisschemas zu spezifi zieren. Daher bieten einige Konzepte Erweiterungen an, die man in COAST durch Ver wendung von Rückwärtskonvertierungsfunktionen bereits hat. Durch die Vorwärts und Rückwärtskonvertierungsfunktionen können beide Richtungen von Abbildungen zwischen (simuliertem) Basisschema und (simuliertem) Sichtschema sogar homogen durch dasselbe Konzept spezifiziert werden. Die Propagationsflags wären zur Simulation alle eingeschaltet und durch die Verwendung der verzögerten Propagationsmechanismen von COAST liefert die Simulation von Sich ten durch Schemaversionen zusätzlich ein optimiertes Konzept der Materialisierung von Sichten. - Das Konzept der direkten Schemaevolution hatte sich bei der Anwendung in dem hier beschriebenen Einsatzgebiet als zu restriktiv erwiesen. Nichtsdestotrotz kann die direkte Schemaevolution in Einzelfällen für die Durchführung von Schemaänderungen genügen, insbesondere solange noch keine Applikationen für eine Schemaversion implementiert sind. Folgerichtig können Situationen entstehen, wo selbst eingefrorene Schemaversionen noch in eingeschränktem Umfang änderbar wären, auch wenn dies i.Allg. nicht der Fall ist. Daher haben wir eine Kombination der direkten Schemaänderung mit dem Versionierungsansatz auf der Basis des Datenmodells von O 2 untersucht [FL96] (siehe Abschnitt 5.4.2). Dort konnten wir durch eine Klassiøkation der Schemaänderungsprimitive feststellen, ob den im Einzelfall gegebenen Umständen zufolge die Ableitung einer neuen Schemaversion erfor derlich ist oder nicht. Auf diesem Wege kann die Zahl entstehender Schemaversionen und damit auch der sich ergebende Verwaltungsaufwand reduziert werden. - Die in Datenbanksystemen benötigten Änderungsoperationen lassen sich drei elementaren Kategorien zuordnen:
The efficient management of large multimedia databases requires the development of new techniques to process, characterize, and search for multimedia objects. Especially in the case of image data, the rapidly growing amount of documents prohibits a manual description of the images’ content. Instead, the automated characterization is highly desirable to support annotation and retrieval of digital images. However, this is a very complex and still unsolved task. To contribute to a solution of this problem, we have developed a mechanism for recognizing objects in images based on the query by example paradigm. Therefore, the most salient image features of an example image representing the searched object are extracted to obtain a scale-invariant object model. The use of this model provides an efficient and robust strategy for recognizing objects in images independently of their size. Further applications of the mechanism are classical recognition tasks such as scene decomposition or object tracking in video sequences.
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.
Zunächst wurde die Notwendigkeit von Schemaänderungen erläutert und verschiedene Ansätze aus der Literatur beschrieben, Schemaänderungen in laufenden Systeme so durchzuführen, dass eine möglichst einfache und automatisch stattfindende Konvertierung der betroffenen Datenobjekte erfolgen kann. Beim Vergleich erweist sich das Konzept der Schemaversionierung als die leistungsfähigste Lösung. Der Grundgedanke der Schemaversionierung ist, durch jede Schemaänderung eine neue Schemaversion zu erstellen, wobei die alte Schemaversion weiterhin benutzt werden kann. Die Datenobjekte liegen ebenfalls in mehreren Versionen vor und die Schemaänderung wird auf Objektebene nachempfunden, indem Datenänderungen propagiert, d.h. die Daten automatisch konvertiert werden. Für die Propagation werden die Beziehungen zwischen den Schemaversionen ausgenutzt. Mit dem Konzept der Schemaversionierung ist es möglich, mehrere Versionen eines Schemas parallel zu benutzen und nur die auf die Datenbank zugreifenden Applikationen anzupassen, die auch wirklich von der Schemaänderung betroffen sind. Diese Diplomarbeit ist Teil des COAST-Projekts, das die Schemaversionierung als Prototyp umsetzt. In COAST existierte vor dieser Diplomarbeit nur die Möglichkeit, einfache Schemaanderungen durchzuführen. Neu wurden komplexe Schemaanderungsoperationen eingeführt und das Konzept der Propagation entsprechend erweitert. Komplexe Schemaänderungen unterscheiden sich von einfachen Schemaänderungen dadurch, dass sie Attribute aus mehreren Quellklassen in einer Zielklasse (oder andersherum) vereinen können. Die bereits in kurz angeschnittenen Default-Konvertierungsfunktionen wurden genauer untersucht und konkret eingeführt. Es wurden mehrere typische Schemaänderungsoperationen vorgestellt und darauf untersucht, ob sie mit den bisherigen einfachen Schemaänderungsoperationen durchführbar waren oder ob dazu komplexe Schemaänderungsoperationen nötig sind. Außerdem wurde analysiert, ob das System für die entsprechenden Operationen automatisch sinnvolle Defaultkonvertierungsoperationen generieren kann oder ob ein Eingriff des Schemaentwicklers notwendig ist. Dazu wurden sie in eine von vier Kategorien eingeteilt, die aussagen, ob einfache oder komplexe Schemaänderungsoperationen nötig sind und ob sinnvolle Default-Konvertierungsfunktionen ohne Eingriff des Schemaentwicklers erzeugt werden können oder nicht. Zu jeder der aufgezahlten Schemaänderungsoperationen wurde die entsprechende vom System erzeugte Default-Konvertierungsfunktion aufgeführt und im Falle, dass sie der Schemaentwickler uberprüfen muss, angegeben, wo noch potenzieller Bedarf für manuelle Änderungen vorliegt. Die Auswirkungen der Einführung von komplexen Schemaänderungsoperationen auf die Propagation wurde im nächsten Kapitel analysiert und dabei festgestellt, dass das bisherige Konzept der Propagationskanten zwischen je zwei Objektversionen desselben Objekts nicht mehr ausreicht. Entsprechend wurde das neue Konzept von kombinierten Propagationskanten entwickelt, das Kanten zwischen mehr als nur zwei Objektversionen zulässt. Dazu wurden verschiedene Lösungsmöglichkeiten miteinander verglichen. Weiter wurden verschiedene Ansätze fur die Darstellung und Speicherung von Konvertierungsfunktionen vorgestellt und entschieden, die Konvertierungsfunktionen konkret in textueller Darstellung in den Propagationskanten zu speichern. Fur die Spezifizierung der gewünschten Konvertierungen bei der Propagation wurde eine Konvertierungssprache entwickelt und nach verschiedenen Gesichtspunkten konzipiert. Diese Gesichtspunkte umfassen sowohl den nötigen Funktionsumfang der Sprache wie auch entwurfstechnische Aspekte. Sämtliche Befehle der entwickelten Sprache wurden detailliert vorgestellt und abschließend die Sprache in BNF (Backus-Naur-Form) präsentiert. COAST ist inzwischen als Prototyp implementiert und wurde u.a. auf der CeBIT '99 vorgestellt (s. [Lau99b] und [LDHA99]). Nach einer Beschreibung der Funktionsweise und des Aufbaus von COAST und insbesondere des Propagationsmanagers wurden einige Implementierungsdetails vorgestellt und verschiedene Betrachtungen zur moglichen Optimierung beschrieben. Die Ziele der Diplomarbeit wurden damit erreicht: Die Schemaevolution kann mit den Vorzügen der Versionierung durchgeführt werden. Komplexe Schemaänderungen sind nun möglich und wurden ins Modell integriert. Die Propagation wurde entsprechend erweitert und eine Sprache zur Spezifikation der Propagation entwickelt.
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].