Grundlagen der Sicherheit
Die Grundlagen der Sicherheit bilden das rigorose mathematische Fundament der Kryptographie: präzise Definitionen dessen, was Sicherheit bedeutet, die Härteannahmen, auf denen Sicherheit beruht, und die Reduktionen, die die Sicherheit von Schemata beweisen.
Definition
Die Grundlagen der Sicherheit umfassen die definitorischen Rahmenwerke, rechnerischen Annahmen und Beweistechniken, die verwendet werden, um Sicherheitsziele präzise zu spezifizieren und rigoros zu demonstrieren, dass kryptographische Konstruktionen diese erreichen.
Scope
Dieser Bereich umfasst die Theorie, die Kryptographie zu einer Wissenschaft und nicht zu einer Kunst macht: formale Sicherheitsdefinitionen und Angreifermodelle, rechnerische Härteannahmen, die reduktionsbasierte Methodik der beweisbaren Sicherheit sowie die zentrale Rolle von Zufälligkeit und Pseudozufälligkeit. Er behandelt, wie 'sicher' definiert und demonstriert wird. Ausgenommen sind die konkreten Primitive und Protokolle, die diese Ideen instanziieren, welche in den kryptographiezentrierten Bereichen behandelt werden.
Sub-topics
Core questions
- Was bedeutet es formal, dass ein kryptographisches Schema 'sicher' ist?
- Wie werden die Fähigkeiten und Ziele eines Angreifers in einem präzisen Modell erfasst?
- Auf welchen unbewiesenen, aber plausiblen Härteannahmen beruht die Sicherheit?
- Wie beweist eine Reduktion, dass das Brechen eines Schemas ein schwieriges Problem lösen würde?
- Warum sind Zufälligkeit und Pseudozufälligkeit grundlegend für die Kryptographie?
Key concepts
- Sicherheitsdefinitionen
- Angreifermodelle
- semantische Sicherheit und Ununterscheidbarkeit
- rechnerische Härteannahmen
- Reduktionen
- Einwegfunktionen
- Pseudozufälligkeit
- vernachlässigbare Wahrscheinlichkeit
- rechnerische vs. informationstheoretische Sicherheit
Key theories
- Semantische Sicherheit und Ununterscheidbarkeit
- Goldwasser und Micali definierten die Verschlüsselungssicherheit als semantische Sicherheit – ein Chiffretext offenbart rechnerisch nichts Nützliches über den Klartext – was sich als äquivalent zur Chiffretext-Ununterscheidbarkeit erwies und vage Intuitionen durch ein präzises, erreichbares Ziel ersetzte.
- Beweisbare Sicherheit durch Reduktion
- Ein Schema wird durch eine Reduktion als sicher bewiesen, die zeigt, dass jeder effiziente Angreifer, der es bricht, in einen Algorithmus umgewandelt werden könnte, der ein als schwierig angenommenes Problem löst; die Sicherheit ist somit von der Annahme abhängig, aber rigoros.
Clinical relevance
Der grundlegende Standpunkt ist der Grund, warum moderner Kryptographie vertraut werden kann: Anstatt zu hoffen, dass ein Schema einem Angriff standhält, beweisen Designer, dass dessen Brechen so schwierig ist wie ein gut untersuchtes Problem unter einem präzise formulierten Angreifermodell. Diese Methodik untermauert die Sicherheitsaussagen jedes standardisierten Primitivs und Protokolls, leitet, welche Schemata von Regulierungsbehörden und Standardisierungsgremien genehmigt werden, und erklärt, warum ad-hoc, unbewiesene Designs missbilligt werden.
Evidence & guidelines
Die Analyse der beweisbaren Sicherheit wird heute bei der kryptographischen Standardisierung erwartet (NIST-Wettbewerbe für AES, SHA-3 und Post-Quanten-Schemata berücksichtigten alle Sicherheitsbeweise und Reduktionen). Maschinell überprüfte Beweise (EasyCrypt) und standardisierte Modelle (Random-Oracle, Standardmodell) sorgen für Rigorosität, obwohl Debatten über idealisierte Annahmen bestehen bleiben. Konstruktionen, deren Sicherheit nur auf Heuristiken beruht, werden nicht empfohlen.
History
Die Kryptographie wurde in den frühen 1980er Jahren zu einer rigorosen Wissenschaft, als Goldwasser und Micali die probabilistische Verschlüsselung und semantische Sicherheit (1982-1984) einführten und die ersten präzisen Definitionen und Beweise lieferten. Yao und Blum-Micali formalisierten die Pseudozufälligkeit, und die reduktionsbasierte Methodik verbreitete sich in den 1980er und 1990er Jahren, konsolidiert in Goldreichs 'Foundations of Cryptography'. Diese definitorische Revolution unterscheidet die moderne Kryptographie von früheren Code-Erstellungen.
Key figures
- Shafi Goldwasser
- Silvio Micali
- Oded Goldreich
- Andrew Yao
- Manuel Blum
Related topics
Seminal works
- goldwasser1984
- goldreich2001
- katz2020
Frequently asked questions
- Was bedeutet 'nachweislich sicher' eigentlich?
- Es bedeutet, dass es einen mathematischen Beweis gibt, dass das Brechen des Schemas mindestens so schwierig ist wie das Lösen eines Problems, das als unlösbar gilt, unter einem angegebenen Angreifermodell. Es ist keine absolute Garantie: Die Sicherheit ist abhängig von der Härteannahme und davon, dass das Modell die Realität getreu abbildet.
- Warum sollte man sich überhaupt auf unbewiesene Härteannahmen verlassen?
- Die meisten nützlichen kryptographischen Verfahren können nicht bedingungslos als sicher bewiesen werden – dies würde große offene Probleme wie P versus NP lösen. Stattdessen wird die Sicherheit auf eine kleine Menge langjährig untersuchter Probleme (Faktorisierung, diskreter Logarithmus, Gitter) reduziert, deren Schwierigkeit durch Jahrzehnte fehlgeschlagener Angriffe untermauert wird.