Memory-efficient algorithms for solving subset sum and related problems with cryptanalytic applications
- Diese Dissertation thematisiert Algorithmen zum Lösen des Subset Sum Problems (zu deutsch: Teilsummen-Problem), einem fundamentalen Problem der theoretischen Informatik. Bei den entwickelten Algorithmen wird, mit Hinblick auf deren Praktikabilität, ein besonderer Fokus auf Ihre Speichereffizienz gelegt. Zudem wird die Rolle des Subset Sum Problems als Meta-Problem der Kryptoanalyse beleuchtet indem Relationen zu kryptographisch relevanten Problemen, wie etwa dem Diskreten Logarithmus Problem (DLP) und dem Learning Parity with Noise Problem (LPN, zu deutsch: Paritätslernen mit Störungen), betrachtet werden. Die Hauptresultate dieser Arbeit sind die schnellsten, bislang bekannten Algorithmen für das DLP und das LPN Problem in speicherlimitierten Umgebungen sowie der schnellste Algorithmus zum Lösen des Subset Sum Problems bei polynomiellen Speicherrestriktionen.
Download full text files
Additional Services
| Author: | Andre EsserGND |
|---|---|
| URN: | urn:nbn:de:hbz:294-73984 |
| DOI: | https://doi.org/10.13154/294-7398 |
| Referee: | Alexander MayORCiDGND, Nils-Gregor LeanderORCiDGND |
| Document Type: | Doctoral Thesis |
| Language: | English |
| Date of Publication (online): | 2020/08/10 |
| Date of first Publication: | 2020/08/10 |
| Publishing Institution: | Ruhr-Universität Bochum, Universitätsbibliothek |
| Granting Institution: | Ruhr-Universität Bochum, Fakultät für Mathematik |
| Date of final exam: | 2020/05/20 |
| Creating Corporation: | Fakultät für Mathematik |
| GND-Keyword: | Kryptologie; Kryptoanalyse; Speicher (Informatik); Algorithmus; Effizienz |
| Dewey Decimal Classification: | Naturwissenschaften und Mathematik / Mathematik |
| faculties: | Fakultät für Mathematik |
| Licence (German): |  Keine Creative Commons Lizenz - es gelten der Veröffentlichungsvertrag und das deutsche Urheberrecht |
