Beweisbare Sicherheit und Reduktionen

Beweisbare Sicherheit zeigt, dass das Brechen eines kryptografischen Schemas mindestens so schwierig ist wie das Lösen eines Problems, das als unlösbar gilt, indem eine explizite Reduktion von dem als schwierig angenommenen Problem auf jeden Angriff auf das Schema gegeben wird.

Definition

Eine Sicherheitsreduktion ist ein Beweis, der jeden effizienten Angreifer, der ein kryptografisches Schema bricht, in einen effizienten Algorithmus umwandelt, der ein als schwierig angenommenes Problem löst, wodurch gezeigt wird, dass das Schema sicher ist, es sei denn, dieses Problem ist einfach.

Scope

Dieses Thema behandelt die reduktionsbasierte Methodik kryptografischer Beweise: die Struktur einer Sicherheitsreduktion, Straffheit und konkrete Sicherheit, spielbasierte und simulationsbasierte Beweisstile, das Random-Oracle-Modell und Standardmodelle sowie die Grenzen und Kritiken des Ansatzes. Es befasst sich damit, wie Sicherheitsgarantien formuliert und begründet werden. Es schließt die spezifischen Härteannahmen sowie die Definitionen und Angreifermodelle aus, die in verwandten Themen behandelt werden.

Core questions

• Wie übersetzt eine Reduktion einen Angriff auf ein Schema in eine Lösung für ein schwieriges Problem?
• Was ist der Unterschied zwischen spielbasierten und simulationsbasierten Beweisen?
• Was bedeutet die 'Straffheit' einer Reduktion für reale Sicherheitsparameter?
• Was sind das Random-Oracle-Modell und das Standardmodell, und warum ist ersteres umstritten?
• Was sind die Grenzen und häufigen Fallstricke von Argumenten der beweisbaren Sicherheit?

Key concepts

• Sicherheitsreduktion
• spielbasierte Beweise
• simulationsbasierte Beweise
• straffe vs. lose Reduktionen
• konkrete Sicherheit
• Random-Oracle-Modell
• Standardmodell
• vernachlässigbarer Vorteil
• Härteannahme

Key theories

Reduktionistische Beweismethodik

Um die Sicherheit eines Schemas zu beweisen, nimmt man einen Angreifer an, der es bricht, und konstruiert unter Verwendung dieses Angreifers als Unterprogramm einen Algorithmus, der das zugrunde liegende schwierige Problem löst – ein erfolgreicher Angriff würde also der Härteannahme widersprechen.

Das Random-Oracle-Modell

Viele effiziente Schemata werden als sicher bewiesen, indem eine Hash-Funktion als ein echtes Zufallsorakel idealisiert wird; das Modell ermöglicht Beweise für praktische Konstruktionen, ist aber heuristisch, da keine reale Funktion ein Zufallsorakel ist.

Mechanisms

Bei einer Reduktion nimmt der Beweisführer einen hypothetischen Angreifer an, der das Schema mit einem nicht vernachlässigbaren Vorteil bricht, und erstellt einen Wrapper, der eine Instanz des schwierigen Problems in die Sicht des Angreifers einbettet, den Angreifer ausführt und dessen Ausgabe zur Lösung des Problems verwendet. Spielbasierte Beweise durchlaufen eine Abfolge von ununterscheidbaren Spielen vom realen Schema zu einem, bei dem der Angreifer eindeutig nicht gewinnen kann. Die Straffheit der Reduktion – wie viel Vorteil und Laufzeit verloren gehen – bestimmt die benötigten Schlüssellängen für ein angestrebtes Sicherheitsniveau.

Clinical relevance

Beweisbare Sicherheit ist der Standard, nach dem kryptografische Schemata Vertrauen und Standardisierung gewinnen: Die AES-, SHA-3- und Post-Quanten-Prozesse des NIST haben Sicherheitsnachweise stark gewichtet, und Protokolle wie TLS 1.3 wurden von reduktionistischen und maschinell überprüften Analysen begleitet. Das Verständnis von Reduktionen ermöglicht es Praktikern, zu beurteilen, was eine Sicherheitsaussage garantiert und was nicht, und Parameter zu wählen, die die Straffheit der Reduktion berücksichtigen.

Evidence & guidelines

Die moderne Praxis bevorzugt Beweise im Standardmodell, wo dies machbar ist, und behandelt Random-Oracle-Beweise als starke heuristische Evidenz und nicht als absolute Garantien. Werkzeuggestützte Frameworks (EasyCrypt, CryptoVerif) liefern maschinell überprüfte Beweise. Eine konkrete (exakte) Sicherheitsanalyse, die den Angreifervorteil als Funktion der Ressourcen quantifiziert, wird gegenüber rein asymptotischen Aussagen zur Festlegung realer Parameter bevorzugt.

History

Die reduktionistische Methodik entstand mit der Definitionsrevolution der frühen 1980er Jahre und wurde in den 1990er Jahren systematisiert. Bellare und Rogaway führten das Random-Oracle-Modell (1993) ein, um die Sicherheit praktischer Schemata zu beweisen, und später die Analyse der 'konkreten Sicherheit', um Garantien zu quantifizieren. Das Ergebnis von Canetti, Goldreich und Halevi aus dem Jahr 1998, das Schemata zeigte, die im Random-Oracle-Modell sicher, aber bei Instanziierung unsicher waren, verschärfte die Debatte über idealisierte Modelle.

Key figures

• Mihir Bellare
• Phillip Rogaway
• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali

Seminal works

• bellare1993
• katz2020
• goldreich2001

Frequently asked questions

Bedeutet ein Sicherheitsbeweis, dass ein Schema niemals gebrochen werden kann?

Nein. Ein Beweis zeigt, dass das Brechen des Schemas das Lösen eines als schwierig angenommenen Problems innerhalb eines spezifizierten Modells impliziert. Wenn die Annahme fehlschlägt, das Modell unrealistisch ist oder die Implementierung vom analysierten Schema abweicht, bleiben Angriffe möglich. Beweise reduzieren, aber eliminieren nicht das Risiko.

Warum wird das Random-Oracle-Modell als umstritten angesehen?

Es modelliert eine Hash-Funktion als eine perfekt zufällige Funktion, was keine konkrete Funktion wirklich ist. Beweise in diesem Modell sind starke Evidenz und ermöglichen effiziente Schemata, aber es gibt (konstruierte) Schemata, die im Modell sicher, aber unsicher sind, sobald das Orakel durch eine beliebige reale Hash-Funktion ersetzt wird, daher sind solche Beweise heuristisch.