Annahmen zur rechnerischen Schwierigkeit

Annahmen zur rechnerischen Schwierigkeit sind unbewiesene, aber gut untersuchte Vermutungen – wie die Schwierigkeit der Faktorisierung, diskreter Logarithmen und Gitterprobleme –, auf denen die Sicherheit kryptografischer Schemata letztlich beruht.

Definition

Eine Annahme zur rechnerischen Schwierigkeit ist eine Vermutung, dass ein bestimmtes Rechenproblem von keinem realistischen Angreifer effizient (in polynomialer Zeit) gelöst werden kann, und dient als Grundlage, auf der die beweisbare Sicherheit aufgebaut ist.

Scope

Dieses Thema behandelt die Annahmen, auf denen die Kryptographie basiert: die Existenz von Einwegfunktionen, zahlentheoretische Probleme (Faktorisierung, RSA, diskreter Logarithmus) sowie die Gitter- und Codeprobleme, die in der Post-Quanten-Kryptographie verwendet werden. Es befasst sich mit der Hierarchie zwischen den Annahmen, der Unterscheidung zwischen Worst-Case- und Average-Case-Schwierigkeit und der Überprüfung von Annahmen. Ausgenommen sind die Reduktionsmechanismen, die Annahmen mit Schemata verbinden, und die Sicherheitsdefinitionen selbst, die in verwandten Themen behandelt werden.

Core questions

• Warum muss kryptografische Sicherheit auf unbewiesenen Schwierigkeitsannahmen beruhen?
• Was sind die wichtigsten Annahmen (Einwegfunktionen, Faktorisierung, diskreter Logarithmus, Gitter)?
• Wie verhalten sich Annahmen in ihrer Stärke zueinander?
• Was ist der Unterschied zwischen Worst-Case- und Average-Case-Schwierigkeit?
• Wie werden Kandidaten für schwierige Probleme geprüft, und was passiert, wenn eines fällt?

Key concepts

• Einwegfunktion
• Falltürfunktion
• Annahme der Ganzzahlfaktorisierung
• Annahme des diskreten Logarithmus
• RSA- und Diffie-Hellman-Annahmen
• Lernen mit Fehlern (LWE)
• Worst-Case vs. Average-Case-Schwierigkeit
• P versus NP
• Annahmenhierarchie

Key theories

Einwegfunktionen als minimale Annahme

Die Existenz von Einwegfunktionen – leicht zu berechnen, schwer umzukehren – ist für einen Großteil der symmetrischen Kryptographie notwendig und hinreichend und stellt die grundlegendste Annahme dar; fast die gesamte Kryptographie setzt zumindest dies voraus.

Zahlentheoretische und Gitterannahmen

Die Public-Key-Kryptographie basiert auf strukturierten Problemen – Ganzzahlfaktorisierung, dem RSA-Problem und diskreten Logarithmen (klassisch) sowie Learning-with-Errors- und Shortest-Vector-Problemen in Gittern (Post-Quanten) – die jeweils durch Jahrzehnte kryptoanalytischer Prüfung gestützt werden.

Mechanisms

Die Kryptographie benötigt Probleme, die im Durchschnitt (über zufällige Instanzen) schwer sind, nicht nur im Worst Case, da Schlüssel zufällig gewählt werden. Annahmen sind in einer groben Hierarchie organisiert: Ein Bruch einer schwächeren Annahme (z. B. Faktorisierung) führt oft zum Bruch von darauf aufgebauten Schemata, während Reduktionen Annahmen miteinander in Beziehung setzen. Gitterannahmen sind bemerkenswert für Worst-Case-zu-Average-Case-Reduktionen, die ein stärkeres Vertrauen vermitteln. Das Vertrauen in eine Annahme resultiert eher aus anhaltenden, erfolglosen kryptoanalytischen Bemühungen als aus einem Beweis.

Clinical relevance

Schwierigkeitsannahmen bestimmen, was sicher eingesetzt werden kann und was nicht. Die Entdeckung, dass Quantencomputer die Faktorisierung und diskreten Logarithmen (mittels Shor-Algorithmus) brechen würden, entwertete die Annahmen hinter RSA und der Elliptische-Kurven-Kryptographie gegenüber Quantenangreifern und trieb direkt die Umstellung auf gitterbasierte Post-Quanten-Standards voran. Die Wahl von Schemata, die auf gut untersuchten Annahmen basieren, und die Überwachung ihres Status sind für die langfristige Sicherheit unerlässlich.

Evidence & guidelines

Standardisierungsgremien bevorzugen Annahmen mit langer kryptoanalytischer Erfolgsbilanz; der Post-Quanten-Prozess des NIST bewertete explizit die Reife und das Vertrauen in die zugrunde liegenden Gitter-, Code- und Hash-Annahmen. Best Practice vermeidet exotische oder neu vorgeschlagene Annahmen für hochsichere Systeme und bevorzugt konservative, gut geprüfte Probleme, wobei die Schlüssellängen gegen die besten bekannten Angriffe festgelegt werden.

History

Die Abhängigkeit von der Schwierigkeit entstand mit der Public-Key-Kryptographie im Jahr 1976, als Diffie und Hellman die Sicherheit an den diskreten Logarithmus und RSA an die Faktorisierung knüpften. In den 1980er Jahren wurden Einwegfunktionen und die Unterscheidung zwischen Worst-Case und Average-Case formalisiert. Ajtais Worst-Case-zu-Average-Case-Reduktionen (1996) und Regevs Learning-with-Errors-Problem (2005) etablierten Gitterannahmen, die als quantenresistente Grundlagen an Bedeutung gewannen und die neuen Post-Quanten-Standards untermauern.

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

Warum können wir nicht einfach beweisen, dass diese Probleme schwer sind?

Der Beweis, dass ein Problem super-polynomiale Zeit erfordert, würde tiefgreifende offene Fragen der Komplexitätstheorie (insbesondere P versus NP) lösen, die ungelöst bleiben. Daher stützt sich die Kryptographie auf Annahmen, deren Plausibilität aus jahrzehntelangen erfolglosen Versuchen resultiert, sie effizient zu lösen.

Was passiert, wenn eine Schwierigkeitsannahme gebrochen wird?

Jedes Schema, dessen Sicherheit auf dieser Annahme beruht, wird potenziell unsicher und muss ersetzt werden. Aus diesem Grund führte die Quantenbedrohung für Faktorisierung und diskrete Logarithmen zu einer globalen Migration zu Schemata, die auf anderen, quantenresistenten Annahmen basieren.