Public-Key Verschlüsselung von der LPN-Annahme (PDF)

Diese Arbeit beschäftigt sich mit dem sogenannten Learning Parity with Noise Problem (kurz: LPN) und Public-Key Verschlüsselungsverfahren, die darauf aufbauen. Die LPN-Annahme ist eine von vielen Sicherheitsannahmen, die in der Kryptographie Verwendung finden. Andere bekannte Annahmen/ Probleme sind die diskreter-Logarithmus-Annahme, die Diffie-Hellman-Annahmen und die RSA-Annahme, welche von sogenannten Quantencomputern gebrochen werden könnten und Verfahren, die auf diesen Annahmen basieren, wären dann unbrauchbar. Quantenrechner beruhen auf einem noch theoretischen Konzept, aber es ist nur noch eine Frage der Zeit, bis diese sehr leistungsstarken Computer einsatzfähig werden. Das LPN-Problem kann jedoch auch nicht von Quantencomputern gelöst werden und daher ist es wichtig, Kryptosysteme zu entwickeln, die auf der LPN-Annahme aufbauen.
Das LPN-Problem hat in der Kryptographie viel Verwendung gefunden. Es wird zum Beispiel in den bekannten HB-Protokollen von Hopper und Blum verwendet, deren Sicherheit auf der Härte des LPN-Problems basiert. In dieser Arbeit wird das Public-Key Kryptosysteme beleuchtet: zum Verschlüsseln wird ein öffentlicher Schlüssel und zum Entschlüsseln ein geheimer Schlüssel benutzt.