Lehrstuhl Kryptologie & IT-Sicherheit (CITS)

Abschlussarbeiten - Offene Themen

Multivariate quadratische Verschlüsselungsverfahren gehören zur Klasse der Post-Quantum Systeme und haben dadurch in letzter Zeit viel Aufmerksamkeit genossen. Während mit UOV ein seit 15 Jahren ungebrochenes MQ-Signaturschema existiert sieht es bei Verschlüsselungsverfahren schlecht aus. Die Liste der gebrochenen Verfahren ist lang. Die Arbeit soll sich mit den Angriffen gegen MQ-Verfahren beschäftigen und die Sicherheit neuer Verfahren untersuchen.

Betreuung: Christopher Wolf, Enrico Thomae

  Seitenanfang

Private Information Retrieval für eine Anfrage (kurz: PIR) beschäftigt sich mit dem folgenden Szenario: Ein Nutzer hat eine Datenbank mit n Elementen x_1,...x_n auf dem Server eines externen Anbieters abgelegt. Nun möchte der Nutzer einen bestimmten Datensatz x_i anfragen. Dabei soll der Betreiber der Datenbank nicht feststellen können, welchen der n Datensätze der Nutzer angefragt hat. Für dieses Szenario gibt es eine handvoll brauchbarer Lösungsansätze.

Auf der PKC 2010 haben Kiayias et al. dieses Szenario auf den Fall mehrerer Anfragen erweitert (multi-PIR). Dort wird eine untere Schranke für die nötige Kommunikationskomplexität zwischen Nutzer und Datenbank bewiesen und eine Konstruktion angegeben, die diese untere Schranke asymptotisch erreicht, jedoch große Konstanten enthält. Die vorgeschlagene Konstruktion benutzt bereits bekannte Verfahren für das einfache PIR.

In dieser Abschlussarbeit sollten die bestehenden Arbeiten zum Thema PIR und multi-PIR aufgegriffen werden und im bestmöglichen Fall eine effizientere Konstruktion für das multi-PIR Szenario gefunden werden, d.h. die asymptotische untere Schranke sollte mit kleineren Konstanten realisiert werden.

Ansprechpartner: Alexander Meurer

  Seitenanfang

The notion of chosen ciphertext security (CCA) is nowadays widely accepted as the standard security notion for public key encryption schemes. However, there are only a handful of known public key encryption schemes that can be proven to be CCA-secure in the standard model. Most of them are based on existing generic constructions. The goal of this thesis is to compare these constructions and seek for possibilities of improvement.

Betreuung: Kiltz

  Seitenanfang

Digitale Signaturen gehören zu den wichtigsten und am meisten verwendeten kryptographischen Primitiven. Trotzdem gibt es nur einige wenige praktische Digitale Signaturen, welche man auch ohne perfekt zufällige Hash Funktionen (s.g. random oracles) als sicher beweisen kann.

Ziel dieser eher theoretischen Arbeit ist es einen Überblick über die bestehenden Verfahren zu geben. Darüber hinaus sollen auch mögliche Verbesserungen untersucht werden.

Betreuung: Kiltz

  Seitenanfang

LPN steht für "Learning Parity with Noise" und ist eine kryptographische Sicherheitsannahme, welche nach dem heutigen Stand der Technik auch nicht von Quantencomputern gebrochen werden kann. Bisher gibt es nur generische Baum-basierte Digitale Signaturen, welche beweisbar so sicher sind, wie die LPN Annahme.

Diese Arbeit soll die bekannten Konstruktionen zusammenfassen und deren Effizienz vergleichen. Darüber hinaus soll versucht werden, eine nicht-generische Digitale Signatur von der LPN Annahme zu entwickeln, z.B. basierend auf der Fiat-Shamir Heuristik.

Betreuung: Kiltz

  Seitenanfang

Angriff mittels verbesserter SubsetSum-Algorithmen.

Betreuung: May

  Seitenanfang

Angriff auf die Phi-Hiding Annahme mittels gitterbasierter Algorithmen


Betreuung: May

  Seitenanfang

Derzeit werden im Bereich der Public Key Kryptographie vor allem RSA und
ECC verwendet. Falls jedoch Quantencomputer mit genügend vielen
Quantenbits zur Verfügung stehen, sind diese allerdings unsicher
(Algorithmus von Shor). Davon abgesehen besitzen beide Verfahren
teilweise unerwünschte Eigenschaften bezüglich Laufzeit, Skalierbarkeit
oder existierender Patente.

In der vorliegenden Arbeit soll aus /einer/ der Verfahrensklasse
(Multivariate Quadratische Systeme, Codierungsbasiert, Hash-Bäume,
Gitterbasiert) ein Schema ausgewählt und studiert werden. Ggf. ist es
auch möglich, sich auch einen bestehenden Angriff zu stützen und diesen
zu erweitern.

Je nach Fragestellung kann die Arbeit entweder theoretisch-mathematisch
oder praktisch durchgeführt werden.


Ansprechpartner: Christopher Wolf

  Seitenanfang

AES ist vermutlich der am meisten eingesetzte kryptographische Algorithmus - noch vor elliptischen Kurven oder RSA. Wenngleich gut dokumentiert und untersucht, gab es bereits früh Zweifel daran, ob AES sog. "algebraischen" Angriffen stand halten kann. Hierbei wird eine Chiffre in Form (algebraischer) Gleichungen ausgedrückt und diese dann gelöst. Im Kontext von Stromchiffren war dies mehrfach von Erfolg gekrönt und führte letztendlich zur Formulierung der sog. "Algebraischen Immunität", die inzwischen ein festes Designkriterium für neue Stromchiffren ist. Im Gegensatz dazu gibt es für AES innerhalb der kryptographischen Gemeinschaft sowohl Argumente für wie auch gegen die Existenz effizienter algebraischer Angriffe. Allerdings ist zu ergänzen dass die meisten Argumente in der Vergangenheit entkräftet werden konnten.

In der vorliegenden Arbeit soll durch praktische Tests festgestellt werden, ob bestimmte Hypothesen über die Lösbarkeit von AES-Gleichungen zutreffen. Dies könnte Aufschluss darüber geben, inwieweit AES doch mittels algebraischer Angriffe gebrochen werden kann.

Je nach Zeitbedarf für den ersten Schritt kann dies auch auf die Stromchiffren "Trivium" sowie "Trivium/128" ausgedehnt werden, da deren Gleichungen ähnliche Eigentschaften haben.

Trotz ihrer praktischen Anteile enthält die Arbeit eine starken mathematisch Komponente.

Ansprechpartner: Christopher Wolf

  Seitenanfang

Im Bereich der Post-Quanten-Kryptographie ist es leider derzeit nur beschränkt möglich, die Laufzeiten sowie andere Eigenschaften der konkurrierenden Systeme miteinander zu vergleichen. Hauptgrund ist das Fehlen frei verfügbarer Implementierungen.

In dieser Arbeit soll aus einer der Klassen (Multivariate Quadratische Systeme, Codierungsbasiert, Hash-Bäume, Gitterbasiert) ein Schema ausgewählt und implementiert werden.

Zur Wahl stehen entweder eine hochperformante Implementierung in C/C++ oder eine eher mathematisch orientierte Implementierung zu kryptanalytischen Zwecken. Die erste soll in das europäische eBACS-Projekt einfließen, die letztere als OpenSource auf der Lehrstuhlseite zur Verfügung gestellt werden.

Ansprechpartner: Christopher Wolf

  Seitenanfang

Kryptographischen Systeme wie z.B. Blockchiffren, Stromchiffren, aber auch Identifikationsschema gelten immer dann als gebrochen, wenn sie effizient durch lineare Gleichungen ausdrückbar sind. Erinnert sei an dieser Stelle nur an LFSR (Linear Feedback Shift Registers), die mit gerade einmal 2n bekannten Bit an Schlüsselstrom rekonstruiert werden können - bei einer praktischen Periodenlänge von (2^n-1).

Soweit die Theorie. In der Praxis stellen die entstehenden Gleichungen häufig ein schwieriges Problem dar und können oft nicht gelöst werden. Interessanter Weise ist das Hauptproblem oft nicht die Zeit (O(n3)), sondern der Platzbedarf (O(n2)). Abhilfe schaffen hier dünn besetzte Gleichungen (O(n2) Zeit und O(n) Platz). Letztendlich ist dies jedoch häufig auch nicht ausreichend, so dass die Berechnungen auf mehrere Computer verteilt werden müssen. Das selbe gilt für die Berechnung der Echelon-Form für dünn besetzte Gleichungen.

In der vorliegenden Abschlussarbeit soll prototypisch ein verteilter Gleichungslöser implementiert und getestet werden. Die Gleichungen stammen dabei direkt aus kryptographischen Fragestellungen, so dass ggf. entsprechende Strukturen nutzbar sind.

Ansprechpartner: Christopher Wolf

  Seitenanfang