Sind asymptotische Untergrenzen für die Kryptographie relevant?

Eine asymptotische Untergrenze wie Exponentialhärte impliziert im Allgemeinen, dass ein Problem "von Natur aus schwierig" ist. Verschlüsselung, die "von Natur aus schwierig" zu knacken ist, gilt als sicher.

Eine asymptotische Untergrenze schließt jedoch nicht aus, dass eine große, aber begrenzte Klasse von Probleminstanzen einfach ist (z. B. alle Instanzen mit einer Größe von weniger als ).$10^{1000}$

Gibt es einen Grund zu der Annahme, dass eine Kryptographie, die auf asymptotischen Untergrenzen basiert, ein bestimmtes Sicherheitsniveau bietet? Erwägen Sicherheitsexperten solche Möglichkeiten oder werden sie einfach ignoriert?

Ein Beispiel ist die Verwendung von Falltürfunktionen, die auf der Zerlegung großer Zahlen in ihre Primfaktoren beruhen. Früher galt dies als von Natur aus schwierig (ich glaube, dass Exponential die Vermutung war), aber jetzt glauben viele, dass es einen Polynomalgorithmus geben könnte (wie es ihn für Primalitätstests gibt). Das Fehlen einer exponentiellen Untergrenze scheint niemanden zu interessieren.

Ich glaube, dass andere Falltürfunktionen vorgeschlagen wurden, von denen angenommen wird, dass sie NP-hart sind (siehe verwandte Frage ), und einige haben möglicherweise sogar eine nachgewiesene Untergrenze. Meine Frage ist grundlegender: Ist es wichtig, was die asymptotische Untergrenze ist? Wenn nein, hängt die praktische Sicherheit eines kryptografischen Codes überhaupt mit einer asymptotischen Komplexität zusammen?

Ich werde versuchen, eine teilweise Antwort zu geben, da mir nicht ganz klar ist, wie dieses Problem von der gesamten Crypto-Community behandelt wird (vielleicht auf Crypto.SE neu posten ?).

Ich würde sagen, es gibt zwei Arten von Kryptographen: Theoretische und Praktische . Ich werde nicht versuchen, sie auseinanderzuhalten (jeder praktische Kryptograf ist auch ein bisschen Theoretiker ...), aber ich sage das für die theoretische Kryptografie - dieses Problem spielt keine Rolle. Für jeden Sicherheitsparameter gibt es eine Instanzgröße, die diese Sicherheitsstufe bietet, und das ist normalerweise alles, was uns interessiert.

Praktische Kryptografen interessieren sich sehr für das von Ihnen angesprochene Thema. Für einen bestimmten Sicherheitsparameter (sagen wir ) versuchen Kryptografen, die effizientesten Protokolle zu entwickeln und die Konstante so weit wie möglich zu reduzieren. Suchen Sie beispielsweise nach dem AES- oder SHA-3- Wettbewerb von NIST . Die Algorithmen mussten sowohl sicher als auch effizient sein. Das Problem hierbei ist, dass der Begriff Sicherheit sich etwas von dem "theoretischen" unterscheidet und manchmal nicht wirklich asymptotisch ist.$2^{1024}$

Ein konkretes Beispiel, an das ich denken kann, ist das diskrete Protokoll oder die DDH-Annahme (die Sicherheit vieler kryptografischer Schemata basiert auf diesen Annahmen). Wir gehen davon aus, dass für einige Gruppen das Log . (Wir können nicht sicher sein: Es könnte sein, dass und dieses Problem in gelöst werden kann .) Cryptographers DO kümmert sich um die tatsächliche Zeit es braucht , um das Protokoll zu berechnen. Genauer gesagt interessieren sie sich für spezielle Fälle, für die das Berechnen des Protokolls einfach ist. In vielen Artikeln wird der Satz "Let eine Gruppe sein, in der DDH schwer ist" vorkommen. Siehe diese Umfrage$G$$O(|G|)$$\text{P}=\text{NP}$$O(\log |G|)$$G$ für Familien von Gruppen, für die angenommen wird, dass DDH nicht behandelbar ist (es sei denn, P = NP).