Kurz und gut

Krzysztof Pietrzak, Assistant Professor am IST Austria, präsentiert gemeinsam mit Eike Kitz und Mario Szegedy ein neues Verfahren zur Erstellung beweisbar sicherer digitaler Signaturen, die kürzer und damit kompakter sind als bisher möglich. Das Forscherteam wird seine Ergebnisse nächste Woche bei der jährlichen CRYPTO Konferenz  in Santa Barbara (USA) – einer der beiden wichtigsten  akademischen Konferenzen auf dem Gebiet der Kryptographie – vorstellen. Dieses Ergebnis ist das Resultat einer Zusammenarbeit zwischen den Kryptologen Kiltz und Pietrzak und dem Kombinatorik-Experten Szegedy, welcher als Visiting Professor in der Gruppe von Herbert Edelsbrunner am IST Austria tätig war.

Ein digitales Signaturschema dient zur Authentifizierung von Nachrichten: Mit einem geheimen Schlüssel kann für jede Nachricht effizient eine digitale Signatur erstellt werden. Der Empfänger der Nachricht kann mit dem entsprechenden öffentlichen Schlüssel verifizieren, dass die Signatur zur Nachricht passt, die Nachricht also wirklich vom angegebenen Absender stammt.

Die beiden wichtigsten Parameter eines Signaturschemas sind die Signaturlänge L und die Sicherheit N, die in bits gemessen wird. Hierbei bedeuten N-bits Sicherheit, dass mindestens 2^N  Berechnungsschritte benötigt werden, um das Schema zu brechen, also um eine gültige Signatur ohne den geheimen Schlüssel zu finden. Bei 100-bit Sicherheit würde man also gigantische 2^100 Schritte für einen erfolgreichen Angriff benötigen. Da man eine Signatur durch simples Ausprobieren aller 2L Möglichkeiten finden kann, muss die Signatur mindestens so lange sein wie die gewünschte Sicherheit N. Um N-bit Sicherheit zu erreichen, muss die Signatur also so lang oder länger sein als die gewünschte Sicherheit (L≥N). Die kürzesten bisher bekannten Signaturen sind doppelt so lang wie die gewünschte Sicherheit (L=2N) und damit weit von dieser unteren Schranke entfernt. In ihrer Publikation zeigen die Wissenschaftler ein neues Signaturschema, bei dem die Signaturlänge die optimale untere Schranke erreicht, die Signatur also nur so lang wie die gewünschte Sicherheit ist (L=N). Damit ist die mit dem neu entwickelten Verfahren erhaltene Signatur um einiges kürzer als die kürzesten Signaturen, die mit bestehenden Verfahren möglich waren.

Kurze Signaturen sind vor allem im Kontext von Netzwerken wie dem Internet interessant. Bei manchen Protokollen müssen alle versendeten Pakete authentifiziert werden. Kürzere Signaturen ersparen hier eine Menge an zusätzlicher Kommunikation, welche für die Authentifizierung notwendig wird. Dadurch können digital signierte Dokumente schnell, aber trotzdem sicher verschickt werden.