Vernachlässigbare Funktion in der Kryptographie

Question

Im Bereich der Kryptographie und Berechnungskomplexität gibt es einen Begriff einer vernachlässigbaren Funktion.

Ich habe einige Schwierigkeiten, die Intuition hinter diesem Begriff zu verstehen. Im Folgenden sind einige Definitionen aus Kapitel 9. Kryptographie aus der Komplexität der Lehrbuchberechnung. Ein moderner Ansatz von Arora und Barak mit umfassender Einsatz einer vernachlässigbaren Funktion. Da meine Frage nach jeder Definition über vernachlässigbare Funktion.

Bevor wir weiter fortfahren, stellen wir eine einfache Definition vor, die die Notation in diesem Kapitel erheblich vereinfacht.

Definition der vernachlässigbaren Funktion. Eine Funktion $ epsilon: mathbb {n} rightarrow [0,1] $ wird als vernachlässigbar bezeichnet, wenn $ epsilon (n) = n^{- Omega (1)} $.

Da vernachlässigbare Funktionen mit zunehmendem Wachstum ihres Eingangs tendenziell sehr schnell null sind, können Ereignisse, die mit vernachlässigbarer Wahrscheinlichkeit auftreten, in den praktischsten und theoretischen Umgebungen sicher ignoriert werden.

So weit so gut, dass es nur die Definition der vernachlässigbaren Funktion ist, ist der einzige Punkt, warum wir uns um diese Funktion kümmern müssen, wenn sie "Kann sicher ignoriert werden".

Der Begriff der rechnerischen sicheren Funktion. frac {1} {2}+ epsilon (n) $.

Weniger intuitive Verwendung einer vernachlässigbaren Funktion. Wie ich verstanden habe, ist im Allgemeinen $ a $ CAN mit Wahrscheinlichkeit 0,5 erraten einheitlich verteilt $ x_i $, daher macht es die Erwartung der erwarteten niedrigeren Erfolgsgrenze $ leq frac {1} {2} $, es ist jedoch $ $ Leq frac {1} {2} + epsilon (n) $, wir können "sicher ignorieren" $ epsilon (n) $ Warum zu erwähnen, und der zweite Punkt ist möglich, $ a $ einige fest auszuführen Endliche Häufigkeit, um die Wahrscheinlichkeit unendlich nahe bei 1 zu erhalten?

Definition der Einweg-Funktion. $ x in_r {0,1 }^n, y = f (x), pr [a (y) = x 'st f (x') = y] < epsilon (n) $

In diesem Fall ist die Verwendung einer vernachlässigbaren Funktion sehr intuitiv, die Erfolgswahrscheinlichkeit wird durch vernachlässigbare Funktion $ epsilon (n) $ oberen begrenzt. Ich bin mir nicht sicher, wie es mit dem Existenz eines rechnerischen Verschlüsselungsschemas korreliert ist (natürlich ist durch Verschlüsselungsschema vorzuziehen). Wenn $ epsilon (n) $ jedoch sicher ignoriert werden kann, als es in Ordnung ist.

Das Problem ist, dass ich nicht ganz verstehe, warum wir vernachlässigbare Funktion brauchen. Mit wenigen Definition versuchte ich, genauer zu sein, was genau ich nicht verstehe.

Ich würde mich freuen, wenn jemand das Licht auf die Verwendung einer vernachlässigbaren Funktion werfen kann

Answer 1

Wenn Sie einen Algorithmus $ a $ mit vernachlässigbarer Wahrscheinlichkeit $ epsilon (n) $ von Erfolg für einen Eingang von Länge $ n $ Die Anzahl der Male bis zum ersten Erfolg ein geometrisch verteilt Zufällige Variable $ s $. Der erwartete Wert von $ S $ ist

$$ mathbb {e} (s) = frac {1} { epsilon (n)} = n^{ Omega (1)} quad. $$

Ein Angreifer, der ein Vielfaches $ ein $ Polynom (z. B. $ P (n) $) verwendet, kann also keine nicht vernachlässigbare Erfolgswahrscheinlichkeit haben, die wir durch den Vergleich der erwarteten Werte sehen werden. Sei $ a '$ der Algorithmus, der $ A $ $ P (n) $ -mal wiederholt, und die zufällige Variable, die die Anzahl der $ a' $ repräsentiert, muss wiederholt werden, bis der erste Erfolg als $ S '$ bezeichnet wird. Dann:

$$ mathbb {e} (s) leq p (n) mathbb {e} (s ') quad, $$

Eine nicht vernachlässigbare Erfolgswahrscheinlichkeit für $ a '$ würde also eine nicht vernachlässigbare Wahrscheinlichkeit für $ a $ bedeuten, da das Produkt zweier Polynome wieder polynomisch ist. Das Zulassen vernachlässigbarer Wahrscheinlichkeiten schadet also keinen Schaden (zumindest für polynomisch begrenzte Gegner).

Dies enthält im Wesentlichen einen indirekten Beweis dafür, dass $ P (n) Epsilon (n) $ für jedes Polynom $ p $ nach wie vor vernachlässigbar ist, was auch direkt nachgewiesen werden kann: $ p $ wird von seinem größten Exponenten dominiert, also $ P ($ P ($ P ($ P) dominiert. n) in mathcal o (n^c) $ für einige $ c in mathbb {n} $. Andererseits $ epsilon (n) in o (n^{-d}) $ für alle $ d in mathbb {n} $. Definieren Sie $ d '= dc $ und Sie erhalten $ epsilon (n) in o (n^{-(d'+c)}) $ für alle $ d ' in mathbb {n} $. So $ p (n) epsilon (n) in o (n^{-(d '+c)}) mathcal o (n^c) = o (n^{-d'}) $ für alle $ D ' in mathbb {n} $, was wieder vernachlässigbar ist.

Wenn Sie auf einer Wahrscheinlichkeit von $ 0 $ (oder $ frac {1} {2} $ im Fall von Unterscheidungsgebern) bestehen, werden viele Anwendungen (fast) unmöglich. Betrachten Sie eine kryptografische Hash -Funktion $ H $ und ein unbekanntes Argument $ x $. Die Wahrscheinlichkeit, ein Vorab -$ x '$ st $ h (x') = H (x) $ zu finden, das alle $ x $ übernommen wurden, kann nicht $ 0 $ betragen, da das Testen aller möglichen Inputs schließlich zum Erfolg führen. Sie könnten jedoch die Wahrscheinlichkeit mit $ 2^{-n^{ Omega (1)}} $ oder ähnlich begrenzen und nur diese Funktionen aufrufen. Die meiste Zeit werden jedoch nur unbegrenzte Gegner oder effiziente (dh polynomisch begrenzte) Gegner in Betracht gezogen, sodass die unterschiedlichen Begriffe keine Rolle spielen, da ein effizienter Gegner niemanden brechen kann und unbegrenzt beide können.