Logo des Repositoriums

Band 25 - Heft 2 (April 2002)

https://dl.gi.de/handle/20.500.12116/16111
Auflistung nach:

Auflistung Band 25 - Heft 2 (April 2002) nach Schlagwort "interactive proof systems"

1 - 1 von 1
  • Zeitschriftenartikel
    Kryptographische Protokolle und Null-Information
    (Informatik-Spektrum: Vol. 25, No. 2, 2002) Rothe, Jörg
    Ein Ziel der Komplexitätstheorie ist der Nachweis, dass Probleme nicht effizient gelöst werden können. Solche Ergebnisse wirken oft „negativ” und nicht wünschenswert. Dieser Beitrag beschäftigt sich mit ihrem „positiven” Aspekt, den Anwendungen der Ineffizienz. Während man normalerweise möglichst effiziente Algorithmen zur Lösung von Problemen entwickeln will, ist man in der Kryptographie gerade im Gegenteil daran interessiert, die Ineffizienz bestimmter Probleme nachzuweisen und anzuwenden: Ein Beweis der Ineffizienz gewisser Probleme bedeutet hier einen Zuwachs an Sicherheit in der Übertragung verschlüsselter Nachrichten. In diesem Beitrag werden Protokolle für den Schlüsseltausch und digitale Signaturen vorgestellt sowie die kryptographischen Grundbausteine solcher Protokolle, wie z. B. „Einwegfunktionen”, beschrieben. Wir gehen auch auf das ganz aktuelle Thema der Zero-Knowledge-Protokolle ein. Das sind kryptographische Protokolle, die es erlauben, dass keinerlei Information ungewollt preisgegeben wird: Mit einem Zero-Knowledge-Protokoll kann Alice Bob davon überzeugen, dass sie ein gewisses Geheimnis kennt, ohne auch nur den geringsten Teil dieses Geheimnisses zu verraten. Der hier vorgelegte Text basiert auf Auszügen des Vorlesungsskripts [22] meiner fünfstündigen Vorlesungsreihe im Rahmen der 11th Jyväskylä Summer School, die im August 2001 an der University of Jyväskylä in Finnland stattfand. Eine aktualisierte Version dieser Vorlesung ist als ein Tutorium beim 17th IFIP World Computer Congress angenommen worden, der im August 2002 in Montreal, Kanada, stattfindet. Diese Arbeit wurde unterstützt durch den grant NSF-INT-9815095/DAAD-315- PPP-gü-ab.AbstractOne goal of complexity theory is to prove problems to be not efficiently solvable. Such results often appear to be „negative” and not desirable. In contrast, this contribution considers their „positive” aspects, the applications of inefficiency. Usually, one wants to design algorithms that are as efficient as possible for solving problems. In cryptography, on the contrary, one is interested in proving and utilizing the inefficiency of certain problems: A proof of the inefficiency of such problems here means an increase in security for transmitting encrypted messages. Protocols for secret-key agreement and digital signatures are presented, as well as the cryptographic building blocks of these protocols, such as „one-way functions.” We also introduce the current topic of zero-knowledge protocols, which are cryptographic protocols that do not convey any information not meant to be disclosed: Using a zero-knowledge protocol, Alice can convince Bob that she knows a certain secret without telling what her secret is.