Tight Reductions in Cryptography
In der modernen Kryptographie werden neue Kryptosysteme normalerweise zusammen mit einem Sicherheitsbeweis konstruiert. Ein solcher Sicherheitsbeweis besteht in der Regel aus einer Reduktion (im komplexitätstheoretischen Sinne) von einem gut untersuchten Berechnungsproblem P, von dem angenommen wird dass es nicht effizient lösbar ist, auf das Brechen des Kryptosystems (in einem wohldefinierten Sinne). Klassische Beispiele für P sind das Problem der Faktorisierung großer Zahlen, oder das diskrete Logarithmusproblem in bestimmten algebraischen Gruppen. Die Reduktion konstruiert aus einem hypothetischen, effizienten Angreifer A auf das Kryptosystem einen effizienten Algorithmus R(A) für das Berechnungsproblem P. Unter der Annahme, dass kein effizienter Algorithmus für P existiert, kann also auch A nicht existieren. Das Kryptosystem ist also sicher.
Die "Qualität" einer Reduktion kann gemessen werden, indem man die Laufzeit und Erfolgswahrscheinlichkeit von R(A) mit der Laufzeit und Erfolgswahrscheinlichkeit von A vergleicht. Idealerweise sollten R(A) und A ungefähr die gleiche Laufzeit haben. In diesem Falle sagt man, dass die Reduktion "scharf" ("tight") ist. Allerdings beschreiben die meisten Sicherheitsbeweise in der Literatur nicht-scharfe Reduktionen, bei denen R(A) entweder eine signifikant größere Laufzeit als A hat, oder eine signifikant geringere Erfolgswahrscheinlichkeit (oder gar beides). Die Reduktion "verliert" also entweder Effizienz oder Wirksamkeit.
Die Schärfe von Reduktionen beeinflusst direkt die Größe kryptographischer Parameter, und hat damit auch direkte Auswirkungen auf die Effizienz von Kryptosystemen. Daher sind scharfe Reduktionen ein interessantes Forschungsthema in der Kryptographie. Nach dem aktuellen Stand der Forschung gibt es jedoch eine Reihe offener Fragen:
- Wie können Kryptosysteme mit scharfer Reduktion konstruiert werden?
- Welche spezifischen Kriterien muss ein Kryptosystem erfüllen, um eine scharfe Reduktion zu erlauben bzw. nicht zu erlauben?
- Können wir scharfe Reduktionen für existierende Kryptosysteme finden, oder zeigen dass solche nicht existieren?
- Können wir die bekannten Techniken, um untere und obere Schranken für die Schärfe von Reduktionen zu zeigen, verbessern?
Das Ziel dieses Projektes ist, Fortschritte bei der Beantwortung dieser Fragen zu machen. Insbesondere werden im Projekt verschiedene konkrete Ideen zur Beantwortung wichtiger Teilfragen bearbeitet.
