Forschungsseminar - Näheres zu den Vorträgen
Falk Niehörster: Einführung in die Quanteninformatik und der Existenzbeweis einer universellen Quanten-Turingmaschine
Nach einer kurzen Einführung in die Axiome der Quantenmechanik und die Grundlagen der Quanteninformatik, soll die von David Deutsch definierte Quanten-Turingmaschine dargestellt werden. Darüber hinaus wird der Existenzbeweis einer universellen Quanten-Turingmaschine von Bernstein und Vazirani ausführlich besprochen. Zum Abschluss soll ein Überblick über die grundlegenden Quantenkomplexitätsklassen gegeben werden.
zur Abstractübersichtzurück zum Seminarplan
André Hernich: Charakterisierungen von P mittels Selbstreduktion und Teilinformation
Selbstreduzierbarkeit ist eine Eigenschaft, die sich viele NP-vollständige sowie PSPACE-vollständige Sprachen teilen. Teilinformationsklassen enthalten Sprachen, für die in Polynomialzeit Teilinformation bezüglich der Mitgliedschaft von Wörtern in solchen Sprachen berechenbar ist. Beispiele sind die Klassen der p-selektiven, strongly membership comparable und der leicht zählbaren Sprachen. Es ist bekannt, dass die Sprachen in P genau die selbstreduzierbaren p-selektiven Sprachen sind. In diesem Vortrag soll gezeigt werden, dass ähnliche Ergebnisse auch für andere Teilinformationklassen gelten. Zum Beispiel lassen sich die Sprachen in P ebenso charakterisieren als selbstreduzierbare Sprachen L, die leicht 2-zählbar oder für die L und das Komplement strongly 2-membership comparable sind.
zur Abstractübersichtzurück zum Seminarplan
Matthias Schwan: Sicherheitsanforderungen und -massnahmen in Funknetzen (WLAN)
Die Einrichtung eines WLAN's erhöht in der Regel den Komfort der Nutzer erheblich, weshalb die Anzahl der Installationen stark steigt. Die durch den Standard IEEE 802.11 definierten Sicherheitsfunktionen erfüllen allerdings nur geringe Sicherheitsanforderungen. Im Vortrag werden die verschiedenen Sicherheitsfunktionen vorgestellt und analysiert, um abschliessend einen Sicherheitslevel festlegen zu können.
zur Abstractübersichtzurück zum Seminarplan
Lyuda Kotomina: Construction of the pseudorandom number generators that use fast machine instructions (addition and XOR) and analysis of there cryptographic characteristics
For the Information security systems we set the problem of finding pseudorandom number generators (also called generators of initial cryptographic sequences) that use fast machine instructions. Besides, such generators must have some characteristics that we can use for making a conclusion about "reliability" of the generators. In the overview we analyse generators that use two fastest machine instructions: arithmetic - addition and logical - XOR (addition modulo 2). We get the criteria that allow both - constructing and analysing of such generators.
zur Abstractübersichtzurück zum Seminarplan
André Hernich: Transforming Turing into Truth-table reductions for languages in P[NONSEL_n]
We call a set {b_0,...,b_n} \subseteq {0,1}^n an ascending chain, if
b_0 = 0^n and b_{i+1}, i \in {0,...,n-1}, is obtained from b_i by
changing one 0 to 1. Let NONSEL_n be the set of all subsets D of
{0,1}^n such that there is no ascending chain D' with D' \subseteq D. A
language A is in P[NONSEL_n] if there exists a function f \in FP which
computes on input of n words (w_1,...,w_n) a set D \subseteq NONSEL_n
which contains the value of \chi_A^n(w_1,...,w_n), where \chi_A^n is
the n-fold characteristic function of A.
Beigel, Kummer and Stephan have shown how to transform Turing into
Truth-table reductions for easily countable languages. We show a
generalization of this theorem: every Turing reduction to a language in
P[NONSEL_n] can be transformed into a Truth-table reduction.
zurück zum Seminarplan
Birgit Schelm: On the role of the class HP in separating average-case approximation classes
A polynomial-time algorithm scheme A for a distributional problem (L,\mu), where L is a language and \mu a probability distributions on words, is a deterministic algorithm with the following properties:
- It receives a word x and a positive integer m as input.
- It may err on some inputs; its error probability depends on the input distribution \mu as follows: Prob[A(x,1^m) \neq \chi_L(x)] < 1/m.
- Its running time is polynomial in
|x|
and m.
The class HP is defined as the class of all distributional problems
(L,\mu) that have a polynomial time algorithm scheme.
In my talk I will discuss the role of the class HP in separating
average-case approximation classes, or in other words: the role of the
class HP in average-case non-approximability proofs.
zurück zum Seminarplan
Piyush P Kurur: On the complexity of computing the units of a number field
Let $K$ be a number field with ring of integers $O_K$. We are
interested in computing the units of the ring $O_K$. We will prove that
the above mentioned problem is in the complexity class SPP. As a result
we show that the above problem is in and "low" for various complexity
classes like PP, Parity-P, Mod_kP etc. Also the problem is unlikely to
be NP-hard.
I will give a brief introduction to the relavant algebraic number
theory and complexity theory. If time permits, I will also mention the
complexity upperbounds for relate problems viz. Principal ideal testing
and computing the Class group.
zurück zum Seminarplan
Matthias Schwan: Das Sicherheitsmodell Zugriffsmatrix
Um einen hohen Qualitätsstandard bei der Konstruktion von
IT-Sicherheitssystemen zu erreichen, ist die Formulierung präziser
Sicherhietseigenschaften notwendig. Durch Modellbildung können für
bestimmte Systeme auf hohem Abstraktionsgrad die Eigenschaften bewiesen
werden.
Der Vortrag beginnt mit einer Einführung der Sciherheitsmodelle und
deren Bedeutung in der IT-Sicherheit. Daraufhin wird das formale Modell
der Zugriffsmatrix vorgestellt und Sicherheitseigenschaften formuliert.
Es wird gezeigt, dass es im allgemeinen Fall unentscheidbar ist, die
"Sicherheit" eines Modells festzustellen. Es wird sich im wesentlichen
auf die Arbeit von Harrison, Ruzzo und Ullman (HRU-Modell)
gestützt.
zurück zum Seminarplan
Arfst Nickelsen: 1-tt-Reduktionen zwischen Teilinformationsklassen
In Teil 1 wurde gezeigt, dass es Sprachen in P[BOTTOM] gibt, die
NICHT polynomiell 1-tt-reduzierbar auf Sprachen in P[SEL] sind.
Entspechendes gilt auch dann noch, wenn man sowohl der
Reduktionsmaschine als auch dem Selektor Zugriff auf ein Orakel aus PH
gibt.
Dieses Mal werden positive Ergebnisse gezeigt:
- Jede Sprache in P[2-SIZE_2] lässt sich 1-tt-reduzieren auf eine Sprache in P^NP[MIN_2], wenn die Reduktion Zugriff auf ein NP-Orakel hat.
- Jede Sprache in P[SEL_2 + Xor] lässt sich 1-tt-reduzieren auf eine Sprache P^NP[SEL], wenn die Reduktion Zugriff auf ein NP-Orakel hat.
- Jede Sprache in P[TOP u BOTTOM] lässt sich 1-tt-reduzieren auf eine Sprache P^(Sigma_2)[SEL u BOTTOM], wenn die Reduktion Zugriff auf ein Sigma_2-Orakel hat.
zurück zum Seminarplan
Till Tantau: Logspace Optimierungsprobleme und ihre Approximierbarkeit
Optimierungsprobleme haben oft eine reichhaltigere Struktur als
Entscheidungsprobleme. So ist beispielsweise das zum Clique-Problem
gehörige Optimierungspronlem (vermutlich) ungleich schwieriger als das
zum Rucksack-Problem gehörige -- obwohl beide Probleme NP-vollständig
sind.
Im Vortrag sollen nun als neues Konzept Logspace-Optimierungsprobleme
eingeführt werden. Die eingeführten Klassen NLO und LO verhalten sich
zu NL und L wie NPO und PO zu NP und P. Wie im Polynomialzeitfall
können Entscheidungsprobleme die gleiche Komplexität besitzen
(beispielsweise NP-vollständig sein), ihre zugehörigen
Optimierungsprobleme jedoch unterschiedlich schwierig sein. So ist das
Problem zu entscheiden, ob ein Graph einen Weg einer bestimmten
Maximallänge zwischen zwei Knoten enthält, sowohl für DAGs als auch
für Tournaments NL-vollständig. Die zugehörigen
Optimierungsprobleme, nämlich in DAGs bzw. Tournaments möglichst
kurze Pfade zu finden, verhalten sich unterschiedlich: für DAGs ist
das Problem nicht logspace-approximierbar, für Tournaments existiert
ein Logspace-Approximationsschema
zurück zum Seminarplan
Olaf Beyersdorff: Tautologien aus Pseudozufallszahlgeneratoren
Von Krajicek und Alechnovich et al. wurde eine Methode
vorgeschlagen, aus Pseudozufallsgeneratoren Tautologiefolgen zu
gewinnen, die für aussagenlogische Beweissysteme hart sind, d.h. keine
polynomiell grossen Beweise besitzen. Dies sind sogenannte Tauformeln,
die ausdrücken, dass ein String ausserhalb des Bildes einer gegebenen
Polynomialzeitfunktion (des PRG) ist.
Anhand von Resolution und der Nisan-Wigderson-Konstruktion wird die
Methode, der Arbeit von Alechnovich et al. folgend, dargestellt.
zurück zum Seminarplan
Birgit Schelm: Vollständige Probleme für Average Case Approximationsklassen
Die Schwierigkeit bei der Suche nach einer optimalen Lösung für
ein NP-Optimierungsproblem besteht darin, in einer möglicherweise
exponentiell grossen Lösungsmenge die Lösung mit der optimalen
Bewertung zu finden. Falls P ungleich NP, so lassen sich nicht für
alle NP-Optimierungsprobleme Algorithmen angeben, die solche Lösungen
in polynomieller Zeit finden. Auch die Suche nach möglichst guten
Lösungen, d.h. Lösungen, deren Bewertung nur um einen konstanten
Faktor von der Bewertung der optimalen Lösung abweicht, ist für viele
NP-Optimierungsprobleme nicht in polynomieller Zeit möglich, es ein
denn P=NP.
Ähnlich wie bei NP-Entscheidungsproblemen stellt sich auch im Bereich
der Approximierbarkeit von NP-Optimierungsproblemen die Frage, ob sich
diese negativen Ergebnisse nur auf einige wenige in der Praxis unter
Umständen nur selten auftretende Instanzen beziehen, oder ob bereits
durchschnittliche Instanzen schwer approximierbar sind. Um den Begriff
der Durchschnittlichkeit einer Instanz zu formalisieren, wird bei der
Untersuchung der Durchschnittskomplexität eines
NP-Optimierungsproblems zusätzlich eine Wahrscheinlichkeitsverteilung
auf den Instanzen angegeben, die den Grad der Durchschnittlichkeit
jeder Instanz widerspiegelt. Diese Paare aus NP-Optimierungsproblem und
Wahrscheinlichkeitsverteilung werden als randomisierte
NP-Optimierungsprobleme bezeichnet.
Anders als bei der Betrachtung der Durchschnittskomplexität von
NP-Entscheidungsproblemen, lässt sich bei den NP-Optimierungsproblemen
das durchschnittliche Verhalten in Bezug auf zwei Parameter
untersuchen. Zum einen kann die durchschnittliche Komplexität der
Laufzeit betrachtet werden, zum anderen die im Durchschnitt erreichbare
Approximationsgüte.
Der Vortrag konzentriert sich nur auf die Approximierbarkeit mit
durchschnittlich polynomieller Laufzeit und stellt eine Reduktion vor,
die diese Approximierbarkeit erhält. Mit Hilfe dieser Reduktion lässt
sich dann ein Vollständigkeitsbegriff für Klassen von randomisierten
NP-Optimierungsproblemen definieren und vollständige Probleme für
einige dieser Klassen angeben.
zurück zum Seminarplan
Heribert Vollmer: Die Komplexität von Constraint-Satisfaction-Problemen
Ein Constraint-Satisfaction-Problem (CSP) besteht aus einer Folge von Einschränkungen an einen Vektor von Variablen. Eine Lösung eines CSPs ist eine Belegung der Variablen, die alle Einschränkungen erfüllt. Wir untersuchen Boolsche Constraint-Satisfaction-Probleme, bei denen als Einschränkungen beliebige Boolsche Relationen verwendet werden dürfen.
Thomas Schaefer erzielte im Jahre 1978 ein bemerkenswertes Resultat: Er konnte zeigen, dass für jede mögliche Menge von erlaubten Constraints das Problem, von einem CSP festzustellen, ob es eine Lösung besitzt, entweder NP-vollständig ist oder in Polynomialzeit lösbar ist (und nicht etwa in einem der -- unter der Annahme "P ungleich NP" existierenden -- unendlich vielen Zwischengrade liegt). Neben diesem sog. Erfüllbarkeitsproblem wurden seitdem viele weitere Fagestellungen über CSPs komplexitätstheoretisch klassifiziert.
Im Vortrag wird nach einer Einführung in das Themengebiet der Boolschen Constraint-Satisfaction-Probleme die Fargestellung untersucht, wie schwierig es ist, festzustellen, ob zwei gegebende CSPs die gleiche Menge von Lösungen besitzen.
zur Abstractübersichtzurück zum Seminarplan
Arfst Nickelsen: Membership comparable and p-selective Sets
Im Vortrag soll das im Titel genannte Paper von R.Beigel, L.Fortnow
und A.Pavan vorgestellt werden.
Darin wird unter anderem gezeigt:
-
- Es gibt eine Sprache A in P-mc(2), so dass für alle p-selektiven
Sprachen B gilt:
A ist nicht btt-reduzierbar auf B. - Verstärkung von 1.a.:
Für jede Konstante c gibt es eine Sprache A in P-mc(2), so dass für alle p-selektiven Sprachen B gilt:
A ist nicht in n^c-tt-reduzierbar auf B.
- Es gibt eine Sprache A in P-mc(2), so dass für alle p-selektiven
Sprachen B gilt:
Ist P=NP, so ist jede 1-cheatable Sprache 1-tt-reduzierbar auf eine p-selektive Sprache.
zurück zum Seminarplan
Till Tantau: Anfragekomplexität von membership-vergleichbaren Sprachen
Wieviele Anfragen an k-membership-vergleichbare Sprachen sind
nötig, um alle (k+1)-membership-vergleichbaren Sprachen zu
entscheiden?
Diese Anzahl ist für k>=2 mindestens linear und höchstens
kubisch. Hieraus kann man folgern, dass es mehr O(log
n)-membership-vergleichbare Sprachen gibt, als Sprachen, die auf
P-selektive Sprachen tt-reduzierbar sind.
zurück zum Seminarplan
Johannes Köbler: Die Komplexität des Erlernens von Konzeptklassen durch Fragen
We use the notion of general dimension to show that any p-evaluable
concept class with polynomial query complexity can be lerned in
polynomial time with the help of an oracle in the polynomial hierarchy,
where the complexity of the required oracle depends on the query-types
used by the learning algorithm.
In particular, we show that for subset and superset queries an oracle
in Sigma P^3 suffices. Since the concept class of DNF formulas has
polynomial query complexity with respect to subset and superset
querieswith DNF formulas as hypotheses, it follows that DNF formulas
are properly learnable in polynomial time with subset and superset
queries and the help of an oracle in Sigma P^3. We also show that the
required oracle in our main theorem can not be replaced by an oracle in
a lower level of the polynomial-time hierarchy, unless the hierarchy
collapses.
This is joint work with Wolfgang Lindner
zurück zum Seminarplan
Till Tantau: Der Kreuzproduktsatz in der Logik
Bei der Untersuchung der Aufzählbarkeit von Funktionen stösst man
häufig auf ein überraschendes Phänomen: gleichartig lautende Sätze
gelten sowohl in der Rekursionstheorie als auch in der
Automatentheorie, nicht aber in der (ressourcenbeschränkten)
Komplexitätstheorie.
Im Vortrag soll für den Kreuzproduktsatz aufgezeigt werden, warum
dies der Fall ist. Dazu wird ein wesentlich allgemeinerer
Kreuzproduktsatz formuliert, der rein logischer Natur ist. Die bereits
bekannten Kreuzproduktsätze aus der Rekursions- und Automatentheorie
sind Spezialfälle dieses Satzes aus der Logik.
zurück zum Seminarplan
Matthias Schwan: Biometrische Identifikationssysteme
Die Identifikation und Authentifikation einer Person anhand
körpereigener Merkmale erscheint intuitiv als eine der sichersten
Methoden.
Doch bedarf entgegen der gewohnten Komplexitätsabschätzung
kryptografischer Algorithmen das Abschätzen der Mechanismenstärke
eines biometrischen Systems anderer Methoden.
Der Vortrag führt in das Thema Biometrie ein und behandelt aktuelle
Fragen.
zurück zum Seminarplan
Birgit Schelm: Vollständige Probleme für Average Case Approximationsklassen
Im Vortrag wird ein generisches vollständiges Problem für die Klasse DistNPO, die Klasse aller NP-Optimierungsprobleme mit g-berechenbaren Eingabeverteilungen, vorgestellt.
zur Abstractübersichtzurück zum Seminarplan
Till Tantau: Ein Beweis des Kardinaltätssatzes für endliche Automaten für zwei Worte
Die Kardinalitätsvermutung für endliche Automaten besagt, dass
jede Sprache regulär ist, deren n-fache Anzahlfunktion sich
n-aufzählen lässt mittels eines endlichen Automaten.
Im Vortrag soll diese Vermutung für den Fall n=2 beweisen werden. Der
Beweis stützt sich auf drei unterschiedliche Hilfsmittel:
- den Nonspeedup-Satz für endliche Automaten
- auf Büchis erststufige (!) logische Charakterisierung der regulären Sprachen
- auf eine Variante der Easy-Hard-Argumentationen von Kadin
zurück zum Seminarplan
Till Tantau: Drei gute Gründe an die Kardinaltätsvermutung für endliche Automaten zu glauben
Der Kardinaltätssatz für Turing-Maschinen besagt, dass eine
Sprache rekursiv sein muss, wenn ihre n-Kardinaltätsfunktion
n-aufzählbar ist. Die Kardinatätsfunktion bildet jeweils n Worte auf
ihre Anzahl in der Sprache ab. Eine Funktion heisst n-aufzählbar, wenn
eine Turingmaschine bei jeder Eingabe eine Menge von höchstens n
Möglichkeiten für den Funktionswert errechnen kann.
Im Vortrag werden drei Gründe dargestellt, weshalb der
Kardinaltätssatz auch für endliche Automaten gelten könnte.
Beispielsweise gilt er für n=2 auch für endliche Automaten.
zurück zum Seminarplan
Wolfgang Lindner: Erlernbarkeit von DNF Formeln mittels statistischer Formeln.
Im Vortrag werden obere und untere Schranken für die Anzahl der statistischen Fragen, die zum Erlernen boolscher Formeln notwenig werden, gezeigt.
zur Abstractübersichtzurück zum Seminarplan
Johannes Köbler: Vollständigkeitsresultate für Graphisomorphie
We prove that the graph isomorphism problem restricted to trees and
to colored graphs with color multiplicities 2 and 3 is many-one
complete for several complexity classes within NC2.
In particular we show that tree isomorphism, when trees are encoded as
strings, is NC1-hard under AC0-reductions. NC1-completeness thus
follows from Buss's NC1 upper bound.
By contrast, we prove that testing isomorphism of two trees encoded as
pointer lists is L-complete. Concerning colored graphs we show that the
isomorphism problem for graphs with color multiplicities 2 and 3 is
complete for symmetric logarithmic space SL under many-one reductions.
This result improves the existing upper bounds for the problem.
We also show that the graph automorphism problem for colored graphs with color classes of size 2 is equivalent to deciding whether a graph has more than a single connected component and we prove that for color classes of size 3 the graph automorphism problem is contained in SL.
zur Abstractübersichtzurück zum Seminarplan
Olaf Beyersdorff: Beschränkte Arithmetik und aussagenlogische Beweissysteme
Der Vortrag soll überblicksartig die Beziehung zwischen der Länge aussagenlogischer Beweise und der Beweisbarkeit in Theorien der beschränkten Arithmetik darstellen. Insbesondere wird eine Übersetzung arithmetischer Formeln angegeben und daraus eine Methode für untere Schranken für die Beweislänge in aussagenlogischen Beweiskalkülen abgeleitet.
zur Abstractübersichtzurück zum Seminarplan
Arfst Nickelsen: Linearer Advice für 2-approximierbare Sprachen.
Eine Sprache A ist k-approximierbar, falls ein
Polynomialzeitalgorithmus existiert, der bei Eingabe von k Wörtern
einen Pool von 2^(k-1) Bitstrings der Länge k ausgibt, der den
charakteristischen String enthält.
Es ist bekannt, das für jedes k die k-approximierbaren Sprachen in
P/O(n^2) sind (Amir, Beigel, Gasarch).
Es ist auch bekannt, das die p-selektiven in NP/(n+1) sind
(Hemaspaandra, Torenvliet).
Es wird im Vortrag gezeigt, das die 2-approximierbaren Sprachen in
P^(NP[3])/(n+3) liegen.
Der Beweis benutzt eine Technik, mit der man aus Selektorfunktionen
transitive Selektorfunktionen machen kann.
zurück zum Seminarplan
Till Tantau: Computation with Absolutely No Overhead
We study Turing machines that are allowed absolutely no space overhead. The only work spacethe achines have ist that which they can create by reusing the input bits' own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such machines, we show that a large subcalsses of the context-free languages can even be accepted in polynomial time with absolutely no space overhead.
zur Abstractübersichtzurück zum Seminarplan
Till Tantau: On the Reducibility of Sets Inside NP sets with Low Information Content - Part II
Im zweiten Teil des Vortrages sollen nun die Techniken auf Berechnungen mit logarithmischem Platz übertragen werden.
Es soll gezeigt werden, dass:
- Falls GAP in L-mc(const), so ist GAP in L.
- Falls A sich logspace Turing-reduzieren lässt auf L-sel und A logspace-selbstreduzierbar ist, so ist A in L.
- Falls die Determinatenfunktion logspace Turing-reduzierbar ist auf eine L-selektive Sprache, so ist sie in FL.
zurück zum Seminarplan
Till Tantau: On the Reducibility of Sets Inside NP sets with Low Information Content - Part I
In diesem ersten Teil eines Doppelvortrages will ich drei neue Resultate über die Reduzierbarkeit der Probleme SAT, GI und GA auf Sprachen mit geringer Informationsdichte vorstellen.
Konkret soll folgendes gezeigt werden:
- Falls eine Lösung von (1GA,GA) sich tt-reduzieren lässt auf P-mc(const), so ist GA in P.
- Falls GI in P-mc(log), so gilt GI in RP.
- Falls eine Lösung von (1SAT,SAT) sich tt-reduzieren lässt auf P-mc(const), so ist SAT in RP.
zurück zum Seminarplan
Olaf Beyerdorff: Fragmente der Peano-Arithmetik
Der Vortrag soll eine Übersicht über verschiedene Fragmente der Peano-Arithmetik mit Gewicht auf der beschränkten Arithmetik und ihren Beziehungen zur Komplexitätstheorie geben.
zur Abstractübersichtzurück zum Seminarplan
Till Tantau: Reachability in Tournaments
Abstracts:
A group of knights have gathered to hold a tournament that consists of a series of jousts between every pair of the knights. After the tournament Sir Lancelot and Sir Galahad meet and Sir Lancelot says, 'I liked your style. It is only fair you won our joust.' Sir Galahad answers, 'I am not sure. I think you won a joust against someone who won against someone who won against someone, and so forth, who won against me. Isn`t that true?' The two knights ponder on this, but it seems difficult to answer as there were so many jousts. So they go to Merlin, the magician who moves backwards in time, and pose their problem. Merlin ponders on the problem and finally proclaims: ' If some of the jousts in the tournament ended in a draw, your question is difficult to answer. But if none of them did, there is an extremely efficient algorithmen to solve it.' This talk is about that algorithm.
After a short introduction to descriptive complexity theoriy, I will show that the tournament reachability problem is first-order definable and hence has very low computational complexity. In particular, it can be decided in constant parallel time. This shows that the deciding reachability for tounaments is probably easier than deciding it for trees or dags. For the succinct graphs, which frequently arise in hardware desing, I show that the succinct reachability problem is complete for the second level of the polynomial hierarchy. In sharp contrast, succinct reachability problems for most other kinds of graphs are known to be complete for polynomial space.
zur Abstractübersichtzurück zum Seminarplan
Matthias Schwan: Die Digitale Signatur heute
Das Prinzip der elektronischen Signatur basierend auf asymmetrischen Kryptoverfahren ist wohl allen geläufig und schon lange bekannt. Doch, wer hat denn wirklich schon einmal eine Email signiert oder verschlüsselt? Bei der praktischen Umsetzung und Anwendung einer elektronischen Signatur entstehen neue Probleme.
Ich möchte die zu beantwortenden Fragen für den Aufbau einer Public-Key-Infrastructure (PKI) stellen. Dabei werden verschiedene Zertifikatsformate und das Signaturgesetz angesprochen.
Weiterhin soll die Einbindung von SmartCards in das Microsoft Betriebssystem erläutert werden.
Am Ende wollen wir uns ein Zertifikat ausgestellt von der Zertifizierungsinstanz der HU ansehen, das gemeinsam mit dem privaten Schlüssel auf einer Smartcard gespeichert ist sowie eine Email signieren und/oder verschlüsseln.
Damit sollte jeder ein Gefühl dafür bekommen, wo wir mit der Anwendung digitaler Signaturen heute stehen.
zur Abstractübersichtzurück zum Seminarplan