Informatik
Refine
Year of publication
- 2023 (183)
- 2019 (159)
- 2016 (133)
- 2021 (130)
- 2020 (116)
- 2022 (115)
- 2015 (96)
- 2017 (91)
- 2018 (82)
- 2009 (38)
- 2024 (36)
- 2012 (34)
- 2011 (31)
- 2013 (31)
- 2010 (30)
- 2014 (30)
- 2004 (24)
- 2006 (23)
- 2001 (22)
- 2002 (22)
- 2007 (21)
- 2008 (21)
- 1999 (20)
- 2003 (19)
- 1998 (14)
- 2005 (14)
- 1994 (13)
- 1996 (13)
- 2000 (13)
- 1997 (12)
- 1995 (8)
- 1993 (4)
- 1991 (2)
- 1972 (1)
- 1978 (1)
- 1987 (1)
- 1989 (1)
- 1990 (1)
- 1992 (1)
Document Type
- Preprint (748)
- Article (401)
- Working Paper (119)
- Doctoral Thesis (93)
- Diploma Thesis (46)
- Conference Proceeding (41)
- Book (37)
- Bachelor Thesis (36)
- diplomthesis (29)
- Report (25)
Has Fulltext
- yes (1607)
Is part of the Bibliography
- no (1607)
Keywords
Institute
- Informatik (1607)
- Frankfurt Institute for Advanced Studies (FIAS) (1002)
- Physik (982)
- Mathematik (55)
- Präsidium (41)
- Medizin (25)
- Biowissenschaften (21)
- Exzellenzcluster Makromolekulare Komplexe (8)
- Psychologie (8)
- Deutsches Institut für Internationale Pädagogische Forschung (DIPF) (5)
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...
Configuration, simulation and visualization of simple biochemical reaction-diffusion systems in 3D
(2004)
Background In biological systems, molecules of different species diffuse within the reaction compartments and interact with each other, ultimately giving rise to such complex structures like living cells. In order to investigate the formation of subcellular structures and patterns (e.g. signal transduction) or spatial effects in metabolic processes, it would be helpful to use simulations of such reaction-diffusion systems. Pattern formation has been extensively studied in two dimensions. However, the extension to three-dimensional reaction-diffusion systems poses some challenges to the visualization of the processes being simulated. Scope of the Thesis The aim of this thesis is the specification and development of algorithms and methods for the three-dimensional configuration, simulation and visualization of biochemical reaction-diffusion systems consisting of a small number of molecules and reactions. After an initial review of existing literature about 2D/3D reaction-diffusion systems, a 3D simulation algorithm (PDE solver), based on an existing 2D-simulation algorithm for reaction-diffusion systems written by Prof. Herbert Sauro, has to be developed. In a succeeding step, this algorithm has to be optimized for high performance. A prototypic 3D configuration tool for the initial state of the system has to be developed. This basic tool should enable the user to define and store the location of molecules, membranes and channels within the reaction space of user-defined size. A suitable data structure has to be defined for the representation of the reaction space. The main focus of this thesis is the specification and prototypic implementation of a suitable reaction space visualization component for the display of the simulation results. In particular, the possibility of 3D visualization during course of the simulation has to be investigated. During the development phase, the quality and usability of the visualizations has to be evaluated in user tests. The simulation, configuration and visualization prototypes should be compliant with the Systems Biology Workbench to ensure compatibility with software from other authors. The thesis is carried out in close cooperation with Prof. Herbert Sauro at the Keck Graduate Institute, Claremont, CA, USA. Due to this international cooperation the thesis will be written in English.
Die Leistungsfähigkeit moderner Grafikhardware erreicht ein Niveau, auf dem sich selbst aufwändig gestaltete 3D-Szenen in kürzester Zeit berechnen lassen. Die Möglichkeiten, die diese Systeme zur Navigation und Interaktion im dreidimensionalen Raum bieten, erscheinen vielen Anwendern jedoch nicht intuitiv genug. Das Ziel der vorliegenden Arbeit war es, neue Navigations- und Interaktionstechniken für räumliche Anwendungen zu entwerfen und anhand einer prototypischen Implementierung die Eignung dieser Techniken für die Interaktion mit einem virtuellen Modell des Rubik’s Cube zu untersuchen. Da die entwickelten Verfahren ihre Tauglichkeit insbesondere bei der Interaktion über klassische Ein- und Ausgabegeräte unter Beweis stellen sollten (Maus, Tastatur und 2D-Display), waren geeignete Abbildungen der zu beherrschenden Freiheitsgrade zu konzipieren. Die Beschreibung grundlegender Aspekte der menschlichen Wahrnehmung führte zum Konzept der 3D-Metapher, welche die Durchführung einer dreidimensionalen Operation mit Hilfe von 2D-Eingabegeräten erklärt. Einzelne Interaktionsaufgaben des 3D-Raums wurden dargestellt und Beispiele von metaphorischen Konzepten für ihre Implementierung gegeben. Nach der Darstellung der am Rubik’s Cube auftretenden Interaktionsformen wurden metaphorische Konzepte für die Operationen Inspektion und Rotation entworfen und ihre besonderen Eigenschaften beschrieben; hierbei wurde zudem auf spezielle Verfahren eingegangen, die bei der Implementierung dieser Metaphern eingesetzt wurden. Im Rahmen einer Benutzerstudie wurde die Bedienung der konzipierten Interaktionsmetaphern im praktischen Einsatz getestet. Hierbei wurden insbesondere die Kriterien Intuitivität, Effizienz und Erlernbarkeit untersucht sowie die zeitliche Performance und Fehlerhäufigkeiten beim Einsatz der unterschiedlichen Werkzeuge analysiert. Die vorliegende Arbeit bietet eine Reihe von Ansätzen für künftige Erweiterungen, wie zum Beispiel die Weiterentwicklung zu einer Autorenumgebung für interaktive Anwendungen oder die Integration eines Kommunikationskanals zwischen den einzelnen Interaktionsmetaphern, um auf diese Weise auch komplexe Verhaltensmuster implementieren zu können.
Grafik-Hardware ist programmierbar geworden. Graphic Processing Units (GPUs) der neuen Generation wie der GeForce3 von NVIDIA enthalten Prozessoren, die es dem Software-Entwickler erlauben kurze Routinen auf der Grafik-Hardware auszuführen. Ich gebe in dieser Arbeit einen umfassenden Überblick über die Architekur und Leistungsfähigkeit dieser neuen Chipgeneration, zeige deren Stärken und Schwächen auf und diskutiere Verbesserungsvorschläge. Als Teil der Arbeit präsentiere ich einige von mir entwickelte Schattierungsverfahren, sowie eine Wassersimulation. Diese Demonstratoren sind darauf ausgerichtet vollständig auf den Prozessoren der neuen Grafikchip- Generation zu laufen. Als Antwort auf die Mängel der zur Zeit verfügbaren Application Programming Interfaces stelle ich ein alternatives Interface zur Steuerung der neuen GPUKomponenten vor, das insbesondere die Austauschbarkeit und Kombinierbarkeit von GPU-Programmen unterstützt.
Immer mehr Hersteller bringen kleine mobile Endgeräte (PDAs1) auf den Markt, die via WLAN2 (IEEE 802.11), Bluetooth oder UMTS3 drahtlos Kontakt mit der Außenwelt aufnehmen können. Dabei werden neben zunehmend höheren Übertragungsraten auch große Fortschritte in der Miniaturisierung erzielt. Viele PDAs besitzen bereits eingebaute Funknetzwerk-Karten, bei vielen läßt sich eine solche Karte einfach zusätzlich in das Gerät einstecken. Durch die steigende Rechenleistung der Geräte und die gleichzeitig steigenden Übertragungsraten der Funkverbindungen entstehen diverse neue Anwendungsmöglichkeiten, die allerdings noch wenig ausgenutzt werden. Es überwiegen die Standardaufgaben der PDAs, wie die Termin und die Adressenverwaltung. Ein eventuell vorhandener Zugang zu Netzwerken wird meist ebenfalls nur für Standardanwendungen verwendet, wie z.B. die Synchronisation von Daten mit einem Server, der Zugang zum World Wide Web oder zum Versenden von e-Mails. Der herkömmliche Zugang zu Netzwerken ist meist ortsgebunden. Im sogenannten Infrastruktur-Modus ist man auf eine Basisstation (Access-Point) angewiesen. Bewegt man sich in Bereichen, in denen kein solcher Access-Point zur Verfügung steht, kann eine Netzwerkverbindung nicht hergestellt werden. Die Mobilität des Benutzers ist auf die Funkreichweite seines Geräts zu dieser Basisstation beschränkt. Die Bezeichnung „mobil“ trifft also nur auf das Endgerät, nicht auf die Basisstation zu. Genutzt werden üblicherweise die gleichen Dienste wie in einem kabelgebundenem Netz, nämlich Server des Intra-, bzw. Internets. Die eigenständige Vernetzung mobiler Geräte untereinander, der sogenannte Ad-hoc-Modus, eröffnet neuartige Anwendungsgebiete. Ursprünglich dafür gedacht, zwei Stationen schnell und einfach über Funk miteinander zu verbinden, können durch eine Erweiterung beliebig viele Stationen zu einem spontanen und mobilen Netzwerk zusammengefaßt werden (mobiles Ad-hoc Netzwerk, MANET). Eine zentral verwaltete Infrastruktur entfällt dabei vollständig. Die Aufgaben des Routings muß jede einzelne der beteiligten Stationen übernehmen. Auf diese Weise erhöht sich die Funkreichweite aller beteiligten Stationen, da nicht ein zentraler Access-Point, sondern jeder beliebige Teilnehmer in Reichweite den Zugriff auf das Netzwerk ermöglicht. Es muß dabei allerdings davon ausgegangen werden, daß sich die Stationen in einem solchen Netz ständig bewegen, das Netz verlassen oder neu hinzukommen können. Somit verändert sich andauernd die Netzwerktopologie und ein kontinuierliches und selbstständiges Neuorganisieren des Netzes wird notwendig. Man spricht daher von selbstorganisierenden mobilen Netzen. Der Informationsfluß in Ad-hoc Netzen ist üblicherweise ein anderer als in Festnetzen. Es entsteht eine eher interessensbezogene Kommunikation, weniger eine, die auf dem Wissen von bekannten Endpunkten im Netzwerk basiert. In Ad-hoc Netzwerken können Endpunkte und Adressen aufgrund der sich permanent ändernden Nutzerzusammensetzung naturgemäß nicht bekannt sein. Stattdessen gibt jeder Nutzer Informationen über seine Interessen und seine Angebote im Netzwerk bekannt. Findet sich ein zu diesem Interessensprofil passendes Angebot, so kommt eine Verbindung zustande. Die Flexibilität der PDAs, ihre Mobilität und ihre ständig steigende Leistung lassen die Entwicklung von mobilen Ad-hoc-Anwendungen sinnvoll erscheinen. MANET Netzwerke sind in ihrer Auslegung flexibel und schnell, genau so, wie es die modernen PDAs sind. Es eröffnet sich durch durch beides eine große Zahl neuer und innovativer Anwendungsmöglichkeiten. Eine davon, das so genannte E-Learning, soll im Folgenden näher betrachtet werden. E-Learning ist ein Beispiel für eine Anwendung in Ad-hoc Netzen, die besonders geeignet erscheint, die Beweglichkeit ihrer Anwender in vielerlei Hinsicht zu unterstützen. Durch die Eigenschaft, geeignete Kollaborationspartner und Informationen schnell und gezielt im Netzwerk finden zu können, wird ein spontaner Wissensaustausch über die bisher bestehende Grenzen hinaus möglich. Es werden im Rahmen dieser Diplomarbeit Mechanismen behandelt, die dem Anwender die Nutzung von kollaborativen Anwendungen wie dem E-Learning ermöglichen und ihn bei dessen Nutzung unterstützen sollen.
Die Gitterbasenreduktion hat in der algorithmischen Zahlentheorie und der Kryptologie bedeutende und praktisch relevante Anwendungen [Joux und Stern, 1998; Nguyen und Stern, 2000; Nguyen, 2001]. Ein wesentlicher Beitrag auf dem Gebiet der Gitter-Reduktionsalgorithmen ist der LLL-Algorithmus [Lenstra, Lenstra und Lov´asz, 1982] und auch die Beta-Reduktion (BKZ-Reduktion) von Gitterbasen [Schnorr, 1987, 1988, 1994] ist von großer Bedeutung. Bei Implementierungen dieser Algorithmen auf modernen Rechnerarchitekturen erfolgen viele Berechnungen aus Gründen der schnelleren Verarbeitungsgeschwindigkeit in Gleitpunktzahlen-Arithmetik. Aufgrund inhärenter Rundungsfehler kommt es dabei zu numerischen Instabilitäten. Vor [Koy und Schnorr, 2001b] gab es keine erfolgreichen Ansätze die bei der Gitterbasenreduktion auftretenden Rundungsfehler so zu kontrollieren, dass auch Gitterbasen in der Dimension >= 400 reduziert werden können. Diese Diplomarbeit beschäftigt sich mit den praktischen Aspekten der Gitterbasenreduktion in Segmenten. Dabei handelt es sich um die erstmalige Implementierung und experimentelle Evaluierung der folgenden beiden Verfahren: ....
In den Anwendungsbereichen der Mixed Reality (MR) werden die reale und die virtuelle Welt kombiniert, so dass ein Eindruck der Koexistenz beider Welten entsteht. Meist wird dabei die reale Umgebung durch virtuelle Objekte angereichert, die dem Anwender zusätzliche Informationen bieten sollen. Um die virtuellen Objekte richtig zu positionieren, muss die reale Umgebung erkannt werden. Diese Erkennung der realen Umgebung wird meist durch Bestimmung und Verfolgung von Orientierung und Positionierung der realen Objekte realisiert, was als Tracking bezeichnet wird und einen der wichtigsten Bestandteile für MR-Anwendung darstellt. Ohne die exakte Ausrichtung von realen und virtuellen Objekten, geht die Illusion verloren, dass die virtuellen Objekte Teil der realen Umgebung sind und mit ihr verschmelzen. Markerkombination Das markerbasierte Tracking ist ein Verfahren, das die Bestimmung der Positionierung von realen Objekten durch zusätzliche Markierungen in der realen Umgebung ermöglicht. Diese Markierungen können besonders gut durch Bildanalyseverfahren extrahiert werden und bieten anhand ihrer speziellen Form Positionierungsinformationen. Der Einsatz dieser Trackingtechnologie ist dabei denkbar einfache und kostengünstig. Ein breiter Anwendungsbereich ist durch den kostengünstigen Einsatz dieser Technologien gegeben, allerdings ist das Erstellen von MR-Anwendungen fast ausschließlich MR-Spezialisten vorbehalten, die über Programmierfertigkeiten und spezielle Kenntnisse aus dem MR-Bereich besitzen. Diese Arbeit beschreibt die Entwicklung und Umsetzung der Konzepte, die einem Personenkreis, der lediglich über geringe Kenntnisse von MR-Technologien und deren Anwendung verfügt, den kostengünstigen und einfachen Einsatz von markerbasierten Trackingtechnologien ermöglicht. Die im Rahmen der Arbeit durchgeführte Analyse verweist auf die problematischen Anwendungsfälle des markerbasierten Trackings, die durch die Verdeckung von Markern zustande kommen, in der Beschränkung der Markeranzahl begründet sind, oder durch die Schwankung der Trackingangaben entstehen. Diese Problembereiche sind bei der Entwicklung berücksichtigt worden und können mit Hilfe der entwickelten Konzepte vom Autor bewältigt werden. Das Konzept der Markerkategorien ermöglicht dabei den Einsatz von angepassten Filterungstechniken. Die redundante Markerkombination behebt das Verdeckungsproblem und eliminiert Schwankungen durch das Kombinieren von mehreren Trackinginformationen. Die Gütefunktion ermöglicht die Bewertung von Trackinginformationen und wird zur Gewichtung der Trackingangaben innerhalb einer Markerkombination genutzt. Das Konzept der Markertupel ermöglicht eine Wiederverwendung von Markern, durch den Ansatz der Bereichsunterteilung. Die Konzepte sind in der AMIRE-Umgebung vollständig implementiert und getestet worden. Zum Abschluss ist rückblickend eine kritische Betrachtung der Arbeit, in punkto Vorgehensweise und erreichter Ergebnisse durchgeführt worden.
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.
We introduce a new method for representing and solving a general class of non-preemptive resource-constrained project scheduling problems. The new approach is to represent scheduling problems as de- scriptions (activity terms) in a language called RSV, which allows nested expressions using pll, seq, and xor. The activity-terms of RSV are similar to concepts in a description logic. The language RSV generalizes previous approaches to scheduling with variants insofar as it permits xor's not only of atomic activities but also of arbitrary activity terms. A specific semantics that assigns their set of active schedules to activity terms shows correctness of a calculus normalizing activity terms RSV similar to propositional DNF-computation. Based on RSV, this paper describes a diagram-based algorithm for the RSV-problem which uses a scan-line principle. The scan-line principle is used for determining and resolving the occurring resource conflicts and leads to a nonredundant generation of all active schedules and thus to a computation of the optimal schedule.
In the last years, much effort went into the design of robust anaphor resolution algorithms. Many algorithms are based on antecedent filtering and preference strategies that are manually designed. Along a different line of research, corpus-based approaches have been investigated that employ machine-learning techniques for deriving strategies automatically. Since the knowledge-engineering effort for designing and optimizing the strategies is reduced, the latter approaches are considered particularly attractive. Since, however, the hand-coding of robust antecedent filtering strategies such as syntactic disjoint reference and agreement in person, number, and gender constitutes a once-for-all effort, the question arises whether at all they should be derived automatically. In this paper, it is investigated what might be gained by combining the best of two worlds: designing the universally valid antecedent filtering strategies manually, in a once-for-all fashion, and deriving the (potentially genre-specific) antecedent selection strategies automatically by applying machine-learning techniques. An anaphor resolution system ROSANA-ML, which follows this paradigm, is designed and implemented. Through a series of formal evaluations, it is shown that, while exhibiting additional advantages, ROSANAML reaches a performance level that compares with the performance of its manually designed ancestor ROSANA.
In the last decade, much effort went into the design of robust third-person pronominal anaphor resolution algorithms. Typical approaches are reported to achieve an accuracy of 60-85%. Recent research addresses the question of how to deal with the remaining difficult-toresolve anaphors. Lappin (2004) proposes a sequenced model of anaphor resolution according to which a cascade of processing modules employing knowledge and inferencing techniques of increasing complexity should be applied. The individual modules should only deal with and, hence, recognize the subset of anaphors for which they are competent. It will be shown that the problem of focusing on the competence cases is equivalent to the problem of giving precision precedence over recall. Three systems for high precision robust knowledge-poor anaphor resolution will be designed and compared: a ruleset-based approach, a salience threshold approach, and a machine-learning-based approach. According to corpus-based evaluation, there is no unique best approach. Which approach scores highest depends upon type of pronominal anaphor as well as upon text genre.
Assessing enhanced knowledge discovery systems (eKDSs) constitutes an intricate issue that is understood merely to a certain extent by now. Based upon an analysis of why it is difficult to formally evaluate eKDSs, it is argued for a change of perspective: eKDSs should be understood as intelligent tools for qualitative analysis that support, rather than substitute, the user in the exploration of the data; a qualitative gap will be identified as the main reason why the evaluation of enhanced knowledge discovery systems is difficult. In order to deal with this problem, the construction of a best practice model for eKDSs is advocated. Based on a brief recapitulation of similar work on spoken language dialogue systems, first steps towards achieving this goal are performed, and directions of future research are outlined.
Robuste Anaphernresolution
(2004)
In the last years, much effort went into the design of robust anaphor resolution algorithms. Many algorithms are based on antecedent filtering and preference strategies that are manually designed. Along a different line of research, corpus-based approaches have been investigated that employ machine-learning techniques for deriving strategies automatically. Since the knowledge-engineering effort for designing and optimizing the strategies is reduced, the latter approaches are considered particularly attractive. Since, however, the hand-coding of robust antecedent filtering strategies such as syntactic disjoint reference and agreement in person, number, and gender constitutes a once-for-all effort, the question arises whether at all they should be derived automatically. In this paper, it is investigated what might be gained by combining the best of two worlds: designing the universally valid antecedent filtering strategies manually, in a once-for-all fashion, and deriving the (potentially genre-specific) antecedent selection strategies automatically by applying machine-learning techniques. An anaphor resolution system ROSANA-ML, which follows this paradigm, is designed and implemented. Through a series of formal evaluations, it is shown that, while exhibiting additional advantages, ROSANAML reaches a performance level that compares with the performance of its manually designed ancestor ROSANA.
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.
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.
Im Zeitalter der ständig wachsenden Mobilitätsanforderungen kommt dem flexiblen, dezentralen Zugriff auf Datenbestände aller Art eine immer größere Bedeutung zu. Steht ein Zugang via Internet nicht zur Verfügung, so bietet sich als Alternative die Verwendung eines Mobiltelefons an. Auf der Grundlage des WAP-Protokolls konnen elementare grafische Zugriffsschnittstellen geschaffen werden; deren Möglichkeiten sind jedoch begrenzt: Im Vergleich zu stationären Computerterminals ist die Displaygröße i.d.R. gering; entsprchend aufwändig verlauft das Browsing. Die gegenwärtige Technologie verfügt über eine geringe Bandbreite. die Navigation über Tasten wird vom Benutzer als umständlich empfunden. Es gibt Einsatzkontexte, die eine tastaturbasierte Interaktion a priori ausschließen. Als Alternative bieten sich gesprochensprachige Schnittstellen an, in denen der Benutzer einen Mensch-Maschine-Dialog mit einem telefonbasierten Sprachportal führt. Die Grundlage derartiger Anwendungen bietet Hardware- bzw. Software-Technologie zu Computer-Telefonie-Integration, Spracherkennung, Sprachsynthese. Mit diesen technologischen Basiskomponenten alleine ist es jedoch noch nicht getan: In Abhängigkeit von den spezifischen Erfordernissen der jeweiligen Anwendung sind geeignete Vorgaben zu spezifizieren, die den Computer in die Lage versetzen, den Dialog mit seinem menschlichen Gegenüber in problemadaquater Weise zu führen. Wichtige Anforderungen sind: Natürlichkeit: Ausgestaltung der sprachlichen Interaktion in einer Weise, die den Erwartungen des Anwenders hinsichtlich des jeweiligen Anwendungsfalls entsprechen; Flexibilität: Anpassung an die Eigenarten des jeweiligen Nutzers (Novize oder geübter Anwender etc.); 2 Robustheit: geeignetes Handling von Missverständnissen, unvollständigem Benutzer-Input sowie Unzulänglichkeiten der maschinellen Sprachverarbeitung (insbesondere Fehler in der Spracherkennung) etc. Formale Spezifikationen des maschinellen Dialogverhaltens werden als Dialogmodelle bezeichnet. Hinsichtlich der generischen Wiederverwendbarkeit der Dialogsoftware ist es sinnvoll, derartige Beschreibungen in einem standardisierten Formalismus, einer Dialogmodellierungssprache abzufassen, die sich somit in erster Näherung als eine "Programmiersprache" für eine generische Dialogmaschine auffassen lässt. Folglich stellt sich die Frage, wie eine geeignete Dialogmodellierungssprache aussehen könnte. In Bezug auf webbasierte Sprachportale wurde vom W3C die XML-basierte Dialogmodellierungssprache VoiceXML als Standardisierungsvorschlag erarbeitet ([7]). Im vorliegenden Dokument sollen zunächst Reichweite und Grenzen der Sprache VoiceXML evaluiert werden. Auf der Grundlage der Evaluation sollen strategischen Empfehlungen fur Unternehmen abgeleitet werden, die sich als Anwendungsentwickler auf dem Innovationsmarkt der telefonbasierten Sprachportale betätigen wollen. Die zentralen Fragen lauten: 1. Welches sind die zentralen Probleme der Entwicklung telefonbasierter Sprachportale? 2. Inwieweit löst VoiceXML diese Probleme? 3. Inwiefern lohnt es sich somit, (z.B. zwecks Herausbildung eines Alleinstellungsmerkmals) auf die Technologie VoiceXML zu setzen? 4. Welche Alternativen existieren? In welchen anderen Bereichen sollte man ggf. Kernkompetenzen herausbilden?
Coreference-Based Summarization and Question Answering: a Case for High Precision Anaphor Resolution
(2003)
Approaches to Text Summarization and Question Answering are known to benefit from the availability of coreference information. Based on an analysis of its contributions, a more detailed look at coreference processing for these applications will be proposed: it should be considered as a task of anaphor resolution rather than coreference resolution. It will be further argued that high precision approaches to anaphor resolution optimally match the specific requirements. Three such approaches will be described and empirically evaluated, and the implications for Text Summarization and Question Answering will be discussed.
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.
This paper describes the ROSANA approach, which generalizes the verification of coindexing restrictions in order to make it applicable to the deficient syntactic descriptions that are provided by a robust state-of-the-art parser. By a formal evaluation on two corpora that differ with respect to text genre and domain, it is shown that ROSANA achieves high-quality robust coreference resolution. Moreover, by an in-depth analysis, it is proven that the robust implementation of syntactic disjoint reference is nearly optimal. The study reveals that, compared with approaches that rely on shallow preprocessing, the largely nonheuristic disjoint reference algorithmization opens up the possibility/or a slight improvement. Furthermore, it is shown that more significant gains are to be expected elsewhere, particularly from a text-genre-specific choice of preference strategies.
The performance study of the ROSANA system crucially rests on an enhanced evaluation methodology for coreference resolution systems, the development of which constitutes the second major contribution o/the paper. As a supplement to the model-theoretic scoring scheme that was developed for the Message Understanding Conference (MUC) evaluations, additional evaluation measures are defined that, on one hand, support the developer of anaphor resolution systems, and, on the other hand, shed light on application aspects of pronoun interpretation.
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.
Pseudorandom function tribe ensembles based on one-way permutations: improvements and applications
(1999)
Pseudorandom function tribe ensembles are pseudorandom function ensembles that have an additional collision resistance property: almost all functions have disjoint ranges. We present an alternative to the construction of pseudorandom function tribe ensembles based on oneway permutations given by Canetti, Micciancio and Reingold [CMR98]. Our approach yields two different but related solutions: One construction is somewhat theoretic, but conceptually simple and therefore gives an easier proof that one-way permutations suffice to construct pseudorandom function tribe ensembles. The other, slightly more complicated solution provides a practical construction; it starts with an arbitrary pseudorandom function ensemble and assimilates the one-way permutation to this ensemble. Therefore, the second solution inherits important characteristics of the underlying pseudorandom function ensemble: it is almost as effcient and if the starting pseudorandom function ensemble is efficiently invertible (given the secret key) then so is the derived tribe ensemble. We also show that the latter solution yields so-called committing private-key encryption schemes. i.e., where each ciphertext corresponds to exactly one plaintext independently of the choice of the secret key or the random bits used in the encryption process.
We 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.
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.
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].
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.
Based on the quadratic residuosity assumption we present a non-interactive crypto-computing protocol for the greater-than function, i.e., a non-interactive procedure between two parties such that only the relation of the parties' inputs is revealed. In comparison to previous solutions our protocol reduces the number of modular multiplications significantly. We also discuss applications to conditional oblivious transfer, private bidding and the millionaires' problem.
We propose a new security measure for commitment protocols, called Universally Composable (UC) Commitment. The measure guarantees that commitment protocols behave like an \ideal commitment service," even when concurrently composed with an arbitrary set of protocols. This is a strong guarantee: it implies that security is maintained even when an unbounded number of copies of the scheme are running concurrently, it implies non-malleability (not only with respect to other copies of the same protocol but even with respect to other protocols), it provides resilience to selective decommitment, and more. Unfortunately two-party uc commitment protocols do not exist in the plain model. However, we construct two-party uc commitment protocols, based on general complexity assumptions, in the common reference string model where all parties have access to a common string taken from a predetermined distribution. The protocols are non-interactive, in the sense that both the commitment and the opening phases consist of a single message from the committer to the receiver.
We review the representation problem based on factoring and show that this problem gives rise to alternative solutions to a lot of cryptographic protocols in the literature. And, while the solutions so far usually either rely on the RSA problem or the intractability of factoring integers of a special form (e.g., Blum integers), the solutions here work with the most general factoring assumption. Protocols we discuss include identification schemes secure against parallel attacks, secure signatures, blind signatures and (non-malleable) commitments.
Die Arbeitsgruppe für Chemie und Physik der Atmosphäre am Institut für Meteorologie und Geophysik der Johann Wolfgang Goethe-Universität Frankfurt befasst sich unter anderem mit der Entwicklung einer Continous Flow Diffusion Chamber zur Erfassung und Klassifikation von CCN und IN. Diese Partikel besitzen eine Größe im Mikrometerbereich und sind somit nicht leicht zu erfassen und zu unterscheiden. Bei vergleichbaren Versuchen beschränkte sich bisher die automatische Auswertung auf die Anzahl der Partikel. Es gibt noch kein Verfahren, welches eine Klassifikation in CCN und IN videobasiert vornehmen kann. Es lag ebenfalls kein reales Bildmaterial vor, welches zu Testzwecken für die Klassifikation geeignet gewesen wäre. Basierend auf den physikalischen und meteorologischen Grundlagen wurde mittels Raytracing ein künstlicher Bilddatensatz mit kleinen Eiskristallen und Wassertröpfchen unter verschiedenen Betrachtungsverhältnissen erstellt. Anhand dieses Bilddatensatzes wurde dann ein Verfahren zur Klassifikation entwickelt und prototypisch implementiert, welches dies mittels Methoden aus der graphischen Datenverarbeitung und durch Berechnung der Momente vornimmt. Es war notwendig, Verfahren aus der Kameratechnik zu betrachten, die später in der realen Anwendung mit sehr kurzzeitiger Belichtung, geeigneter Optik und hochauflösender CCD-Kamera detaillierte Bilder von Objekten in der Größe von einigen 10µm liefern können.
We show that non-interactive statistically-secret bit commitment cannot be constructed from arbitrary black-box one-to-one trapdoor functions and thus from general public-key cryptosystems. Reducing the problems of non-interactive crypto-computing, rerandomizable encryption, and non-interactive statistically-sender-private oblivious transfer and low-communication private information retrieval to such commitment schemes, it follows that these primitives are neither constructible from one-to-one trapdoor functions and public-key encryption in general. Furthermore, our separation sheds some light on statistical zeroknowledge proofs. There is an oracle relative to which one-to-one trapdoor functions and one-way permutations exist, while the class of promise problems with statistical zero-knowledge proofs collapses in P. This indicates that nontrivial problems with statistical zero-knowledge proofs require more than (trapdoor) one-wayness.
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.
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 ...
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 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.
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 present an efficient variant of LLL-reduction of lattice bases in the sense of Lenstra, Lenstra, Lov´asz [LLL82]. We organize LLL-reduction in segments of size k. Local LLL-reduction of segments is done using local coordinates of dimension 2k. Strong segment LLL-reduction yields bases of the same quality as LLL-reduction but the reduction is n-times faster for lattices of dimension n. We extend segment LLL-reduction to iterated subsegments. The resulting reduction algorithm runs in O(n3 log n) arithmetic steps for integer lattices of dimension n with basis vectors of length 2O(n), compared to O(n5) steps for LLL-reduction.
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.
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 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.
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.
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.
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.
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.
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.
Assuming a cryptographically strong cyclic group G of prime order q and a random hash function H, we show that ElGamal encryption with an added Schnorr signature is secure against the adaptive chosen ciphertext attack, in which an attacker can freely use a decryption oracle except for the target ciphertext. We also prove security against the novel one-more-decyption attack. Our security proofs are in a new model, corresponding to a combination of two previously introduced models, the Random Oracle model and the Generic model. The security extends to the distributed threshold version of the scheme. Moreover, we propose a very practical scheme for private information retrieval that is based on blind decryption of ElGamal ciphertexts.
Let 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.
With ubiquitous use of digital camera devices, especially in mobile phones, privacy is no longer threatened by governments and companies only. The new technology creates a new threat by ordinary people, who now have the means to take and distribute pictures of one’s face at no risk and little cost in any situation in public and private spaces. Fast distribution via web based photo albums, online communities and web pages expose an individual’s private life to the public in unpreceeded ways. Social and legal measures are increasingly taken to deal with this problem. In practice however, they lack efficiency, as they are hard to enforce in practice. In this paper, we discuss a supportive infrastructure aiming for the distribution channel; as soon as the picture is publicly available, the exposed individual has a chance to find it and take proper action.
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.
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 present a novel practical algorithm that given a lattice basis b1, ..., bn finds in O(n exp 2 *(k/6) exp (k/4)) average time a shorter vector than b1 provided that b1 is (k/6) exp (n/(2k)) times longer than the length of the shortest, nonzero lattice vector. We assume that the given basis b1, ..., bn has an orthogonal basis that is typical for worst case lattice bases. The new reduction method samples short lattice vectors in high dimensional sublattices, it advances in sporadic big jumps. It decreases the approximation factor achievable in a given time by known methods to less than its fourth-th root. We further speed up the new method by the simple and the general birthday method. n2
We enhance the security of Schnorr blind signatures against the novel one-more-forgery of Schnorr [Sc01] andWagner [W02] which is possible even if the discrete logarithm is hard to compute. We show two limitations of this attack. Firstly, replacing the group G by the s-fold direct product G exp(×s) increases the work of the attack, for a given number of signer interactions, to the s-power while increasing the work of the blind signature protocol merely by a factor s. Secondly, we bound the number of additional signatures per signer interaction that can be forged effectively. That fraction of the additional forged signatures can be made arbitrarily small.
We modify the concept of LLL-reduction of lattice bases in the sense of Lenstra, Lenstra, Lovasz [LLL82] towards a faster reduction algorithm. We organize LLL-reduction in segments of the basis. Our SLLL-bases approximate the successive minima of the lattice in nearly the same way as LLL-bases. For integer lattices of dimension n given by a basis of length 2exp(O(n)), SLLL-reduction runs in O(n.exp(5+epsilon)) bit operations for every epsilon > 0, compared to O(exp(n7+epsilon)) for the original LLL and to O(exp(n6+epsilon)) for the LLL-algorithms of Schnorr (1988) and Storjohann (1996). We present an even faster algorithm for SLLL-reduction via iterated subsegments running in O(n*exp(3)*log n) arithmetic steps.
The general subset sum problem is NP-complete. However, there are two algorithms, one due to Brickell and the other to Lagarias and Odlyzko, which in polynomial time solve almost all subset sum problems of sufficiently low density. Both methods rely on basis reduction algorithms to find short nonzero vectors in special lattices. The Lagarias-Odlyzko algorithm would solve almost all subset sum problems of density < 0.6463 . . . in polynomial time if it could invoke a polynomial-time algorithm for finding the shortest non-zero vector in a lattice. This paper presents two modifications of that algorithm, either one of which would solve almost all problems of density < 0.9408 . . . if it could find shortest non-zero vectors in lattices. These modifications also yield dramatic improvements in practice when they are combined with known lattice basis reduction algorithms.
We present a novel parallel one-more signature forgery against blind Okamoto-Schnorr and blind Schnorr signatures in which an attacker interacts some times with a legitimate signer and produces from these interactions signatures. Security against the new attack requires that the following ROS-problem is intractable: find an overdetermined, solvable system of linear equations modulo with random inhomogenities (right sides). There is an inherent weakness in the security result of POINTCHEVAL AND STERN. Theorem 26 [PS00] does not cover attacks with 4 parallel interactions for elliptic curves of order 2200. That would require the intractability of the ROS-problem, a plausible but novel complexity assumption. Conversely, assuming the intractability of the ROS-problem, we show that Schnorr signatures are secure in the random oracle and generic group model against the one-more signature forgery.
We present a practical algorithm that given an LLL-reduced lattice basis of dimension n, runs in time O(n3(k=6)k=4+n4) and approximates the length of the shortest, non-zero lattice vector to within a factor (k=6)n=(2k). This result is based on reasonable heuristics. Compared to previous practical algorithms the new method reduces the proven approximation factor achievable in a given time to less than its fourthth root. We also present a sieve algorithm inspired by Ajtai, Kumar, Sivakumar [AKS01].
Mit dem World Wide Web sind der Bestand und die Verfügbarkeit von Informationen rapide angewachsen. Der Einzelne hat Schwierigkeiten, der Menge an Informationen und Wissen Herr zu werden und so der Informationsüberflutung zu begegnen. Dieses Problem wurde von Forschern und Technikern bereits frühzeitig erkannt und durch verschiedene Konzepte wie die intelligente Suche und die Klassifikation von Informationen zu lösen versucht. Ein weiteres Konzept ist die Personalisierung, die das bedarfsgerechte Zuschneiden von Informationen auf die Bedürfnisse des einzelnen Anwenders zum Ziel hat. Diese Arbeit beschreibt dazu eine Reihe von Personalisierungstechniken und im Speziellen das Kollaborative Filtern als eine dieser Techniken. Bestehende Schwächen des Kollaborativen Filterns wie zu dünn besetzte Benutzerprofile und das mangelnde Erkennen von Änderungen im Benutzerinteresse im Verlauf der Zeit werden durch verschiedene Ansätze zu entschärfen versucht. Dazu wird eine Kombination mit Inhaltsbasierten Filtern und die Verbreiterung der Datenbasis bewerteter Ressourcen betrieben. Ziel ist die Optimierung der Personalisierung, so dass Anwender besser auf sie abgestimmte Informationen erhalten. Ein Teil der beschriebenen Ansätze wird zudem in einem prototypischen Informationssystem umgesetzt, um die Machbarkeit und den Nutzen zu prüfen. Dazu werden der auf der Java 2 Enterprise Edition aufbauende WebSphere Applikationsserver von IBM und die relationale Datenbank DB2 UDB aus gleichem Hause eingesetzt.
Suche im Semantic Web : Erweiterung des VRP um eine intuitive und RQL-basierte Anfrageschnittstelle
(2003)
Datenflut im World Wide Web - ein Problem jedes Internetbenutzers. Klassische Internetsuchmaschinen sind überfordert und liefern immer seltener brauchbare Resultate. Das Semantic Web verspricht Hoffnung - maßgeblich basierend auf RDF. Das Licht der Öffentlichkeit erblickt das Semantic Web vermutlich zunächst in spezialisierten Informationsportalen, so genannten Infomediaries. Besucher von Informationsportalen benötigen eine Abfragesprache, welche ebenso einfach wie eine gewöhnliche Internetsuchmaschine anzuwenden ist. Eine derartige Abfragesprache existiert für RDF zur Zeit nicht. Diese Arbeit stellt eine neuartige Abfragesprache vor, welche dieser Anforderung genügt: eRQL. Bestandteil dieser Arbeit ist der mittels Java implementierte eRQL-Prozessor eRqlEngine, welcher unter http://www.wleklinski.de/rdf/ und unter http://www.dbis.informatik.uni-frankfurt.de/~tolle/RDF/eRQL/ bezogen werden kann.
In dieser Arbeit wurde die Implementierung einer JMX-konformen Managementinfrastruktur für das Agentensystem AMETAS vorgestellt. Darauf basierend wurden im Rahmen des Fehlermanagements Kontrollmechanismen der mobilen Agenten im AMETAS untersucht und eine Lösung für die Lokalisierung von AMETAS-Agenten entworfen und implementiert. Der essentielle Hintergrund für das AMETAS-Management stellt sich folgendermaßen dar: Die Betrachtung des Anwendungs- und Infrastrukturmanagements mit Blick auf die Managementhierarchie stellt die Offenheit und Kooperationsfähigkeit der angestrebten Managementlösung in den Vordergrund. Diese Eigenschaften ermöglichen die Integration der in einem Unternehmen existierenden Managementlösungen. Ziel ist dabei ein kostengünstiges und effizientes Management. Eine Managementarchitektur wird mit Hilfe der informations-, organisations-, kommunikations- und funktionsbezogenen Aspekte beschrieben und modelliert. Anhand dieser Aspekte ist CORBA, DMTF, WBEM und JMX analysiert und ihre Eignung für das AMETASManagement bewertet worden. Neben den allgemeinen Kriterien sind ihre Teilmodelle, ihre Unterstützung des dezentralen und des dynamischen Managements sowie ihre Integrationsfähigkeit im AMETAS zentrale Punkte. Es zeigt sich, dass die JMX die besten Möglichkeiten für das AMETAS-Management bietet. Das OSI-Funktionsmodell klassifiziert die Managementaufgaben und -funktionen in fünf Bereiche, die häufig als FCAPS bezeichnet werden: Fehler-, Konfigurations-, Abrechnungs- , Leistungs- und Sicherheitsmanagement. Diese Klassifikation ist orthogonal zu jeder anderen und bietet einen geeigneten Rahmen für die Aufteilung der Managementaufgaben und - funktionen. Das in dieser Arbeit empfohlene AMETAS-Management orientiert sich hinsichtlich der Managementaufgabenaufteilung am OSI-Modell. Die JMX bietet mächtigeWerkzeuge zur Instrumentierung aller Arten von Ressourcen. Ihre Java-Basiertheit bedeutet eine wesentliche Vereinfachung für das Agentensystem. Die offene Architektur von der JMX ermöglicht die Kooperation des AMETAS-Managements mit anderen Managementstandards. Das AMETAS-Management nutzt die Vorzüge der mobilen Agenten insbesondere im Bereich des Konfigurations- und Fehlermanagements aus. Folgende Eigenschaften zeichnen das AMETAS-Management aus: 1) Verwendung der Agenteninfrastruktur für das Management. Selbiges wird dabei als ein AMETAS-Dienst implementiert und kann alle Möglichkeiten und Dienste der Agenteninfrastruktur nutzen. 2) Verwendung der AMETAS-Agenten und Dienste als Managementwerkzeuge. 3) Selbstmanagement des Systems. Der Managementdienst ist hierfür mit ausreichender Intelligenz ausgestattet. Er nutzt die Mechanismen der Agenteninfrastruktur aus und erledigt diverse Managementaufgaben selbständig. Das Ereignissystem vom AMETAS spielt hierbei eine wichtige Rolle. Die Analyse der Kontrollmechanismen von MASIF, Aglets Workbench und Mole liefert hinsichtlich ihrer Eignung für die Lokalisierung von Agenten im AMETAS folgendes Ergebnis: Die untersuchten Ansätze sind teilweise allgemein anwendbar. Man unterscheidet die nichtdeterministischen Ansätze wie Advertising und Energiekonzept von denen, die bestimmte Spuren von Agenten in einer geeigneten Art hinterlegen. In dieser Hinsicht stellte sich das Pfadkonzept als interessant heraus: Bei diesem Konzept können die Informationen über den Pfad der Migration eines Agenten in geeigneterWeise zeitlich beschränkt oder unbeschränkt gespeichert werden. Eine andere Alternative bietet die Registrierungsmethode. Bei dieser Methode wird ein Agent in einer zentralen Stelle registriert, wobei die eindeutige Identität eines Agenten und die aktuelle Stelle, in der sich ein Agent aufhält, gespeichert werden. Vor dem Hintergrund der erfolgten Analyse empfiehlt sich als Basis für die Lokalisierung von AMETAS-Agenten eine Art Pfadkonzept: Die Spuren der Agenten werden durch einen Managementdienst gesichert. Will man einen bestimmten Agenten oder eine Gruppe lokalisieren, werden die dezentral vorhandenen Informationen innerhalb eines konsistenten Schnitts (Schnappschuss) ausgewertet. Die Schnappschussmethode empfiehlt sich für die Lokalisierung von Agenten im AMETAS entsprechend den zu Beginn der Arbeit von einem Lokalisierungsmechanismus geforderten Eigenschaften: Sie erlaubt eine zuverlässige Lokalisierung der gesuchten Agenten, deren Autonomie dabei respektiert wird. Die Kosten-Leistungsrelation ist günstig einzuschätzen, da unnötiger Daten- bzw. Agentenverkehr ebenso vermieden wird wie die Pflege umfangreicher, zentralistischer Datenbanken.
Das größte Problem bei der Erstellung von MR-Anwendungen besteht darin, dass sie meistens durch Programmierung erstellt werden. Daher muss ein Autor spezielles Fachwissen über MR-Technologie und zumindest allgemeine Programmierkenntnisse mitbringen, um eine MR-Anwendung erstellen zu können. Dieser Erstellungsprozess soll mit Hilfe von MR-Autorensystemen, die derzeit auf dem Markt existieren und in der Forschung entwickelt werden, vereinfacht werden. Dies war ein Grund, warum diese Arbeit sich zum Ziel erklärte, zu überprüfen, inwieweit die Erstellung von MRAnwendungen durch Einsatz von MR-Autorensystemen vereinfacht wird. Ein weiteres Hauptziel war die Erstellung einer repräsentativen MR-Anwendung, die in dieser Arbeit als MR-Referenzanwendung bezeichnet wird. Sie sollte vor allem bei weiteren Entwicklungen als Vorlage dienen können und auf Basis von standardisierten Vorgehensmodellen, wie das Wasserfallmodell, erstellt werden. Ganz wichtig war es noch im Rahmen dieser Arbeit zu bestätigen, dass standardisierte Vorgehensmodelle auf MR-Anwendungen übertragbar sind. Um diese Ziele zu erreichen, sind in dieser Arbeit viele Schritte befolgt worden, die jeweils als Teilziele betrachtet werden können. Die MR-Referenzanwendung , die im Rahmen dieser Arbeit erstellt wurde, sollte mit Hilfe eines MR-Autorensystems umgesetzt werden. Um das richtige MRAutorensystem dafür auszusuchen, wurden im Rahmen einer Analyse fakultative und obligatorische Anforderungen an MR-Autorensysteme definiert, worin auch Funktionen identifiziert wurden, die ein solches System bereitstellen sollte. Das Anbieten einer Vorschau ist ein Beispiel für diese Funktionen, die bei der Erstellung von MR-Anwendungen eine essentielle Rolle spielen können. Die obligatorischen Anforderungen sind welche, die jedes Softwaresystem erfüllen soll, während die fakultativen das Ziel der Verbesserung von Autorensystemen verfolgen. Mit Hilfe der Analyse wurde ein Vergleich zwischen bekannten MR-Autorensystemen gezogen, dessen Ergebnis AMIRE als ein für die Ziele dieser Arbeit geeignetes MR-Autorensystem identifizierte. Für die MR-Referenzanwendung , die ähnliche Funktionen aufweisen sollte wie andere typische MR-Anwendungen wurden Funktionen, Anwendungsfälle und Design der Oberfläche spezifiziert. Diese Spezifikation wurde unabhängig von dem ausgesuchten Autorensystem durchgeführt, um darin analog zur Software-Technik das Augenmerk auf fachliche und nicht auf technische Aspekte zu legen. Um ans Ziel zu gelangen, wurde die MR-Referenzanwendung durch AMIRE realisiert, jedoch musste zuvor ihre Spezifikation auf dieses MR-Autorensystem überführt werden. Bei der Überführung wurde die Realisierung aus technischer Sicht betrachtet, das heißt es wurden verschiedene Vorbereitungen, wie die Auswahl der benötigten Komponenten, die Planung der Anwendungslogik und die Aufteilung der Anwendung in verschiedenen Zuständen, durchgeführt. Nach der gelungenen Realisierung und beispielhaften Dokumentation der MRReferenzanwendung konnte die Arbeit bewertet werden, worin die erzielten Resultate den Zielen der Arbeit gegenübergestellt wurden. Die Ergebnisse bestätigen, dass mit AMIRE die Entwicklung einer MR-Anwendung ohne Spezialwissen möglich ist und dass diese Arbeit alle ihrer Ziele innerhalb des festgelegten Zeitrahmens erreicht hat.
Das Ziel dieser Arbeit war die Entwicklung einer haptischen 3D-Benutzungsoberfläche für die Virtual-Glove-Box. Eine „Glove Box“ ist ein Apparat, in welchem chemische Versuche in abgeschlossener Atmosphäre durchgeführt werden können. Die „Virtual Glove Box“ setzt dieses Konzept für Virtual Reality Anwendungen um. Die Oberflächenelemente waren als wiederverwendbare Komponenten auszuführen. Die Bedienung erfolgt unter Einsatz zweier virtueller Hände mit an den Händen getragenen Exoskeletten zur Vermittlung des haptischen Feedbacks. Es enstand EASY, ein System zur einfachen und individuellen Gestaltung von Benutzungsberflächenelementen. Diese können in ein bereitgestelltes Framework einfügt und ohne Wissen über die zugrundeliegende Hardware benutzt werden. Die Entwicklung konnte nicht abgeschlossen werden, da die zur Verfügung stehenden Hardware-Komponenten nicht in Betrieb zu nehmen waren.
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.
This paper proves correctness of Nöcker's method of strictness analysis, implemented in the Clean compiler, which is an effective way for strictness analysis in lazy functional languages based on their operational semantics. We improve upon the work of Clark, Hankin and Hunt did on the correctness of the abstract reduction rules. Our method fully considers the cycle detection rules, which are the main strength of Nöcker's strictness analysis. Our algorithm SAL is a reformulation of Nöcker's strictness analysis algorithm in a higher-order call-by-need lambda-calculus with case, constructors, letrec, and seq, extended by set constants like Top or Inf, denoting sets of expressions. It is also possible to define new set constants by recursive equations with a greatest fixpoint semantics. The operational semantics is a small-step semantics. Equality of expressions is defined by a contextual semantics that observes termination of expressions. Basically, SAL is a non-termination checker. The proof of its correctness and hence of Nöcker's strictness analysis is based mainly on an exact analysis of the lengths of normal order reduction sequences. The main measure being the number of 'essential' reductions in a normal order reduction sequence. Our tools and results provide new insights into call-by-need lambda-calculi, the role of sharing in functional programming languages, and into strictness analysis in general. The correctness result provides a foundation for Nöcker's strictness analysis in Clean, and also for its use in Haskell.
This paper proves correctness of Nocker s method of strictness analysis, implemented for Clean, which is an e ective way for strictness analysis in lazy functional languages based on their operational semantics. We improve upon the work of Clark, Hankin and Hunt, which addresses correctness of the abstract reduction rules. Our method also addresses the cycle detection rules, which are the main strength of Nocker s strictness analysis. We reformulate Nocker s strictness analysis algorithm in a higherorder lambda-calculus with case, constructors, letrec, and a nondeterministic choice operator used as a union operator. Furthermore, the calculus is expressive enough to represent abstract constants like Top or Inf. The operational semantics is a small-step semantics and equality of expressions is defined by a contextual semantics that observes termination of expressions. The correctness of several reductions is proved using a context lemma and complete sets of forking and commuting diagrams. The proof is based mainly on an exact analysis of the lengths of normal order reductions. However, there remains a small gap: Currently, the proof for correctness of strictness analysis requires the conjecture that our behavioral preorder is contained in the contextual preorder. The proof is valid without referring to the conjecture, if no abstract constants are used in the analysis.
Work on proving congruence of bisimulation in functional programming languages often refers to [How89,How96], where Howe gave a highly general account on this topic in terms of so-called lazy computation systems . Particularly in implementations of lazy functional languages, sharing plays an eminent role. In this paper we will show how the original work of Howe can be extended to cope with sharing. Moreover, we will demonstrate the application of our approach to the call-by-need lambda-calculus lambda-ND which provides an erratic non-deterministic operator pick and a non-recursive let. A definition of a bisimulation is given, which has to be based on a further calculus named lambda-~, since the na1ve bisimulation definition is useless. The main result is that this bisimulation is a congruence and contained in the contextual equivalence. This might be a step towards defining useful bisimulation relations and proving them to be congruences in calculi that extend the lambda-ND-calculus.
In this paper we demonstrate how to relate the semantics given by the nondeterministic call-by-need calculus FUNDIO [SS03] to Haskell. After introducing new correct program transformations for FUNDIO, we translate the core language used in the Glasgow Haskell Compiler into the FUNDIO language, where the IO construct of FUNDIO corresponds to direct-call IO-actions in Haskell. We sketch the investigations of [Sab03b] where a lot of program transformations performed by the compiler have been shown to be correct w.r.t. the FUNDIO semantics. This enabled us to achieve a FUNDIO-compatible Haskell-compiler, by turning o not yet investigated transformations and the small set of incompatible transformations. With this compiler, Haskell programs which use the extension unsafePerformIO in arbitrary contexts, can be compiled in a "safe" manner.
This paper proposes a non-standard way to combine lazy functional languages with I/O. In order to demonstrate the usefulness of the approach, a tiny lazy functional core language FUNDIO , which is also a call-by-need lambda calculus, is investigated. The syntax of FUNDIO has case, letrec, constructors and an IO-interface: its operational semantics is described by small-step reductions. A contextual approximation and equivalence depending on the input-output behavior of normal order reduction sequences is defined and a context lemma is proved. This enables to study a semantics of FUNDIO and its semantic properties. The paper demonstrates that the technique of complete reduction diagrams enables to show a considerable set of program transformations to be correct. Several optimizations of evaluation are given, including strictness optimizations and an abstract machine, and shown to be correct w.r.t. contextual equivalence. Correctness of strictness optimizations also justifies correctness of parallel evaluation. Thus this calculus has a potential to integrate non-strict functional programming with a non-deterministic approach to input-output and also to provide a useful semantics for this combination. It is argued that monadic IO and unsafePerformIO can be combined in Haskell, and that the result is reliable, if all reductions and transformations are correct w.r.t. to the FUNDIO-semantics. Of course, we do not address the typing problems the are involved in the usage of Haskell s unsafePerformIO. The semantics can also be used as a novel semantics for strict functional languages with IO, where the sequence of IOs is not fixed.
Context unification is a variant of second order unification. It can also be seen as a generalization of string unification to tree unification. Currently it is not known whether context unification is decidable. A specialization of context unification is stratified context unification, which is decidable. However, the previous algorithm has a very bad worst case complexity. Recently it turned out that stratified context unification is equivalent to satisfiability of one-step rewrite constraints. This paper contains an optimized algorithm for strati ed context unification exploiting sharing and power expressions. We prove that the complexity is determined mainly by the maximal depth of SO-cycles. Two observations are used: i. For every ambiguous SO-cycle, there is a context variable that can be instantiated with a ground context of main depth O(c*d), where c is the number of context variables and d is the depth of the SO-cycle. ii. the exponent of periodicity is O(2 pi ), which means it has an O(n)sized representation. From a practical point of view, these observations allow us to conclude that the unification algorithm is well-behaved, if the maximal depth of SO-cycles does not grow too large.
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.
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 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.
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.
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.
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.
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.
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.
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.
Funktionale Programmiersprachen weisen viele Eigenschaften auf, die zur modernen Softwareentwicklung benotigt werden: Zuverlässigkeit, Modularisierung, Wiederverwendbarkeit und Verifizierbarkeit. Als schwer vereinbar mit diesen Sprachen stellte sich die Einbettung von Seiteneffekten in diese Sprachen heraus. Nach einigen mehr oder weniger gescheiterten Ansätzen hat sich mittlerweile fur die nichtstrikte funktionale Sprache Haskell der monadische Ansatz durchgesetzt, bei dem die Seiteneffekte geschickt verpackt werden, so dass zumindest IO-behaftete Teile eines Haskell-Programms dem klassischen imperativen Programmierstil ähneln. S. Peyton Jones bringt dieses in [Pey01, Seite 3] auf den Punkt, indem er schreibt "...Haskell is the world's finest imperative programming language." Dies ist einerseits vorteilhaft, denn die klassischen Programmiertechniken können angewendet werden, andererseits bedeutet dies auch eine Rückkehr zu altbekannten Problemen in diesen Sprachen: Der Programmcode wird unverständlicher, die Wiederverwendbarkeit von Code verschlechtert sich, Änderungen im Programm sind aufwendig. Zudem erscheint die monadische Programmierung teilweise umständlich. Deshalb wurde im Zuge der Entwicklung in fast jede Implementierung von Haskell ein Konstrukt eingebaut, dass von monadischem IO zu direktem IO führt. Da dieses nicht mit dem bisherigen Ansatz vereinbar schien, wird es als "unsafe" bezeichnet, die entsprechende Funktion heißt "unsafePerformIO". Zahlreiche Anwendungen benutzten diese Funktion, teilweise scheint die Verwendung zumindest aus Effizienzgründen unabdingbar. Allerdings ist die Frage, wann dieses verwendet werden darf, d.h. so angewendet wird, dass es nicht "unsicher" ist, nur unzureichend geklärt. Das Zitat in Abbildung 1.1 gibt wenig Aufschluss über die korrekte Anwendung, zumal immer wieder Diskussionen entstehen, ob die Verwendung von unsafePerformIO in diesem oder jenem Spezialfall korrekt ist.
The wide-area deployment of WiFi hot spots challenges IP access providers. While new profit models are sought after by them, profitability as well as logistics for large-scale deployment of 802.11 wireless technology are still to be proven. Expenditure for hardware, locations, maintenance, connectivity, marketing, billing and customer care must be considered. Even for large carriers with infrastructure, the deployment of a large-scale WiFi infrastructure may be risky. This paper proposes a multi-level scheme for hot spot distribution and customer acquisition that reduces financial risk, cost of marketing and cost of maintenance for the large-scale deployment of WiFi hot spots.
Entwurf und prototypische Realisierung einer Architektur zur flexiblen Verschlüsselung von XML-Daten
(2001)
Im Rahmen dieser Arbeit ist auf Basis einer sorgfältigen Prüfung existierender Literatur zu kryptografischen Verfahren und sowohl einer Analyse bestehender Ansätze zur Verschlüsselung von XML-Dokumenten, als auch unter Nutzung bestehender Standards für XML-Technologien, eine Architektur zur flexiblen Verschlüsselung von XML-Daten erstellt worden. Ausgehend von Einsatz-Szenarien wurden dazu Anforderungen an das gewünschte System definiert. Anhand dieser Anforderungen wurde systematisch eine vollständige Spezifikation zur Verschlüsselung von XML-Daten hergeleitet. Weiterhin ist eine erweiterbare und generische Architektur zur Verarbeitung von XML-Daten spezifiziert worden. Auf dieser aufbauend, wurde eine Architektur für die flexible Ver- und Entschlüsselung von XML-Daten erstellt. Diese Architekturen und ihre Komponenten sind generisch, wobei für die prototypische Realisierung exemplarisch eine konkrete Auswahl dieser Komponenten implementiert wurde. Für die Verschlüsselung wurde dazu auf die zuvor erstellte Spezifikation zurückgegriffen und deren relevante Teile implementiert. Anschliessend wurden Experimente durchgeführt, die einen Eindruck von der Leistungsfähigkeit der Architektur gegeben haben. Insgesamt haben sich die Erwartungen an die Architektur mehr als erfüllt. Stehen Transformationen als verwendbare Klassen bereit, die auf dem DOM operieren, so ist es leicht möglich, diese in das DPF einzubetten, wie z.B. beim Verschlüsselungs-Prozessor geschehen. Damit ist eine sehr gute Erweiterbarkeit gegeben. Da die Arbeitsweise eines Transformations-Prozessors sowohl direkt durch übergebene Argumente aus dem DPS als auch durch die Verwendung von Annotationen gesteuert werden kann, kann die Verarbeitung von Dokumenten sehr flexibel und auch feingranular erfolgen. Die Möglichkeit, Annotationen aus mehreren DAS-Dokumenten zu aggregieren, erlaubt eine verteilte Pflege dieser Dokumente. Mit der Möglichkeit, mehrere Prozessoren direkt nacheinander eine Eingabe bearbeiten zu lassen, wird die Flexibilität nochmals gesteigert. Denn wenn die Prozessoren als Komponenten zur Verfügung stehen, können diese stets aufs Neue kombiniert werden. Vor allem der Ansatz, dass alle zur Verarbeitung und Steuerung relevanten Daten in Form deklarativer Beschreibungen erfolgen, die den Bedürfnissen jedes Prozessors angepasst sind, macht das System zu einem mächtigen Instrument. Zudem werden dadurch keine tiefergehenden Programmierkenntnisse benötigt. So entfällt auch die Notwendigkeit, Änderungen des gewünschten Transformations-Ergebnisses durch Änderungen im Quelltext des erzeugenden Programms vorzunehmen. Dadurch sind insgesamt den Möglichkeiten zur Verarbeitung von XML-Dokumenten kaum Grenzen gesetzt. Notwendige Anpassungen bleiben zumeist auf eine oder wenige Komponenten beschränkt, was Änderungen leichter ermöglicht. Dabei hat sich wieder einmal der flexible und trotzdem mächtige Ansatz der Kette von Werkzeugen (Chain of Tools) bewährt. Auch die Spezifikation zur Verschlüsselung von XML-Daten konnte alle Erwartungen erfüllen. Alle eingangs gestellten Anforderungen sind damit ausnahmslos darstellbar. Insbesondere betrifft dies die partielle und feingranulare Verschlüsselung von XML-Daten, sowie die hierarchische und damit einhergehende Super-Verschlüsselung. Rückblickend kann gesagt werden, dass das wissenschaftliche Fundament in Form von kryptografischen Grundlagen zwar sehr gut ist, aber die darauf aufbauenden höherwertigen Dienste und Architekturen aus wissenschaftlicher Sicht bisher kaum Beachtung gefunden haben. So wird zwar die Verschlüsselung von ganzen Daten-Objekten zwischen zwei Empfängern gut beherrscht, aber eine feingranulare Verschlüsselung, bei der Daten an grosse dynamische Empfängergruppen in offenen Systemen vertraulich übermittelt werden, hat bisher keine Beachtung gefunden. In der vorliegenden Arbeit werden diese Probleme adressiert, wobei aber nicht für alle eine abschliessende Lösung präsentiert werden konnte, da dies den Rahmen der Arbeit gesprengt hätte. Vielleicht ist es gerade die fehlende wissenschaftliche Durchdringung, die es so schwierig macht, geeignete Standards für die Verschlüsselung von XML-Dokumenten zu etablieren. Denn wenn man betrachtet, wie lange schon beim W3C über die Verschlüsselung diskutiert und daran gearbeitet wird, so kann es einen nur verwundern, dass nicht greifbarere Ergebnisse vorliegen. Ende Juli, also kurz vor Abschluss der vorliegenden Arbeit, ist bei Recherchen noch ein wissenschaftlich fundierteres Papier aufgetaucht, das auf einer Konferenz im Juni dieses Jahres vorgestellt wurde. Es beschreibt eine Document Security Language (DSL), die auf XSLT beruht und eine Architektur zur Verschlüsselung von XML-Dokumenten [85]. Da die Nähe zu dieser Arbeit gross ist, soll sie hier noch kurz vergleichend betrachtet werden. Die dort beschriebene Architektur und die Sprache bietet auch die Verschlüsselung auf feingranularer Ebene. Aber sie ist nicht erweiterbar und kennt auch kein generisches Meta-Daten-Konzept, so dass sie hinter den Ergebnissen der vorliegenden Arbeit deutlich zurückfällt. Zudem beruht sie auf der vorne schon im Zusammenhang mit der Verwendung von XSLT kritisierten Arbeit in [48]. Sie trägt dazu im Bereich der Verschlüsselung nicht viel Neues bei. Allerdings weist sie einige interessante Ansätze im Bereich der Infrastrukturen auf [85, Abschnitt 3.2]. Um diese könnte die hier vorgestellte Architektur der Verschlüsselungs-Prozessoren ergänzt werden, denn dieses Gebiet wurde in der Arbeit ausgespart.