Kann ein PRF-Distiguisher den Algorithmus der Funktion aufrufen?

Question

Die Definition einer Funktion $F:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ Als Pseudo Random Function Family (PRF) kann sie durch einen PPT-Algorithmus implementiert werden $\mathcal F$und es gibt keinen PPT-Algorithmus $\mathcal A$ in der Lage zu unterscheiden $x\mapsto F(k,x)$ aus einer Zufallsfunktion für unbekannten Zufall $k$ und nicht verschwindende Wahrscheinlichkeit.

Ist der Algorithmus $\mathcal A$ darf den Algorithmus aufrufen $\mathcal F$ Umsetzung $(k,x)\mapsto F(k,x)$? Oder noch allgemeiner ein Teil davon?

---

Das scheint notwendig zu sein, um Folgendes zu entscheiden $G$ ist ein PRF oder nicht.

• Lassen $H:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ sei ein PRF.
• Lassen $P_c:\ \{0,1\}^n\to\{0,1\}^n$ sei ein PRP mit einem Schlüssel, der auf eine beliebige Konstante festgelegt ist $c$, mit beiden $P$ und ${P_c}^{-1}$ durch einen PPT-Algorithmus berechenbar.
• Definieren $G:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ durch (Assimilieren von Bitstrings zu ganzen Zahlen gemäß Big-Endian-Konvention) $$G(k,x)\underset{\text{def}}=\begin{cases} {P_c}(k\bmod2^{\lfloor n/2\rfloor})&\text{if }x=0^n\\ 1^n&\text{if }x=1^n\text{ and }P_c^{-1}(k)<2^{\lfloor n/2\rfloor}\\ H(k,x)&\text{otherwise} \end{cases}$$

Im Wesentlichen, $G$ ist der PRF $H$, außer es hat eine Reihe von schwachen Schlüsseln $k$ von Größe $2^{\lfloor n/2\rfloor}$, so dass was auch immer $k$, $G(k,0^n)$ist ein schwacher Schlüssel; und wann$k$ ist ein schwacher Schlüssel, $G(k,1^n)$ ist $1^n$.

Wir können einen Distinguisher für bauen $G$ Das

• reicht ein $x=0^n$bekommt $y$
• wendet den Algorithmus für an $G$ eingeben $(y,1^n)$
• testet, ob das Ergebnis ist $1^n$, was immer der Fall sein wird $G$und nur mit verschwindender Wahrscheinlichkeit für eine Zufallsfunktion.

Es scheint jedoch keinen Unterscheidungsmerkmal zu geben, wenn wir den Algorithmus auch nicht anwenden können $G$, noch analysieren, um zu extrahieren $c$.

---

Motivation ist diese Frage , die fragt, ob$F_2(k,x)\underset{\text{def}}=F(F(k,0^n),x)$ ist ein PRF, vorausgesetzt $F$ist ein PRF. Wenn das oben$G$ war ein PRF, $F=G$ wäre ein Gegenbeispiel.

Answer 1

Der Gegner $\mathcal{A}$ darf den Algorithmus aufrufen $\mathcal{F}$ (wenn es sich um PPT handelt) in einer mir bekannten PRF-Definition.

Wir sind allgemein an der Sicherheit gegen jeden möglichen PPT-Algorithmus interessiert $\mathcal{A}$ und erfordern das für jeden solchen Algorithmus $\mathcal{A}$ es hält das $\mathcal{A}$kann nur mit nicht zu vernachlässigender Wahrscheinlichkeit von einer Zufallsfunktion unterscheiden.
Wenn$\mathcal{F}$ Ist ein PPT-Algorithmus, gibt es einen Gegner $\mathcal{A}$ das schließt die ein $\mathcal{F}$Funktionalität. Dieser Gegner kann anrufen$\mathcal{F}$und wir fordern von unserer PRF, dass es auch gegen diesen Gegner sicher ist. Das gleiche Argument gilt für Teile des Algorithmus$\mathcal{F}$.

---

Soweit ich es verstanden habe, ist für Ihr Beispiel die folgende wichtige Frage:

Tut der Gegner $\mathcal{A}$ kennt $c$?

Auch hier brauchen wir Ununterscheidbarkeit gegenüber allen Gegnern eines PRF, was bedeutet, dass wir Ununterscheidbarkeit auch gegenüber einem Gegner brauchen, der dies fest kennt $c$.

Answer 2

Ja, Gegner können viele Dinge fest codieren. Dies ist ein allgemeines Thema in Krypto und TCS.

In diesem Beitrag werde ich eine grundlegendere Sichtweise vorstellen und einige formale Definitionen überprüfen, um hoffentlich zu beantworten, (1) warum / welche Hardcodierung zulässig ist und (2) wie dies in Kryptodefinitionen behandelt wird. Da die Antwort auf (2) so grundlegend ist, finden Sie hier eine Kopie von unten:

Takeaway: Bei der Formalisierung von Sicherheitsdefinitionen werden Werte, die Gegner nicht kennen sollten, durch Zufallsvariablen modelliert, über die die Wahrscheinlichkeit des Gewinns des Experiments übernommen wird. Diese werden häufig gleichmäßig zufällig aus einer exponentiell großen Menge ausgewählt.

Diskussion basierend auf der Definition von PRFs

Betrachten wir eine ziemlich formale Definition eines PRF (vgl. [KL14]):

Def. (PRF): Eine effizient berechenbare Funktion$F\colon\{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$wird als Pseudozufallsfunktion (PRF) bezeichnet, wenn für alle PPT-Gegner$\mathcal{A}$ es gibt eine vernachlässigbare Funktion $\mathrm{negl}\colon\mathbb{N}\to\mathbb{N}$ so dass für alle $n \in \mathbb{N}$ wir haben $$\left|\Pr_{k\leftarrow_€\ \{0,1\}^n}[\mathcal{A}(1^n, F(k,-))=1] - \Pr_{f\leftarrow_€\ \{0,1\}^n\to\{0,1\}^n}[\mathcal{A}(1^n, f(-))=1]\right|\leq \mathrm{negl}(n).$$

Wenn Sie mit der Notation nicht vertraut sind: die Notation $\Pr_{k\leftarrow_€\ \{0,1\}^n}[\cdot]$ bedeutet, dass die Wahrscheinlichkeit von $\cdot$wird über die Probenahme von übernommen$k$ von $\{0,1\}^n$ gleichmäßig zufällig (bezeichnet durch $\leftarrow_€$;; sollte eigentlich ein Dollarzeichen sein, aber der Renderer von StackExchange mag das nicht). Analog für den richtigen Begriff in der obigen Ungleichung wo$f\leftarrow_€\{0,1\}^n\to\{0,1\}^n$ bedeutet, dass $f$wird von allen Funktionen abgetastet$\{0,1\}^n\to\{0,1\}^n$ gleichmäßig zufällig.

Betrachten Sie diese Definition nun im folgenden Kontext:

Wie im ursprünglichen Beitrag, lassen $H$ sei ein PRF, $c$ eine beliebige feste Konstante, $P_c$ ein PRP und $G$ eine Funktion.

Fragen Sie sich jetzt:

Warum sollten Gegner nicht verwendet werden dürfen? $H$, $c$, $P_c$, oder $G$?

Die Definition erstreckt sich eindeutig über alle PPT-Gegner.

Selbst wenn es sinnvoll wäre, wie würden Sie (in der mathematischen Formalisierung) Gegnern verbieten, "externe Variablen" zu verwenden? Was sind überhaupt "externe Variablen"?

Ich habe selbst keine präzise Antwort auf diese Fragen. Stattdessen sollten sie nur Ihre aktuelle Intuition auf den Formalismus neu kalibrieren. Das Nichtzulassen von Dingen, die nicht einmal klar spezifiziert sind ("äußere Dinge"), ist nicht trivial und macht meistens keinen Sinn. In der Tat könnten wir Kerckhoffs Prinzip so formulieren , dass der Gegner alles fest codieren darf, außer dem Schlüssel, den man nicht zulässt. Aber hier ist "der Schlüssel" eine klare Spezifikation und ein Verbot, das im Formalismus sehr gut gehandhabt werden kann. Siehe unten.

Wie wird es Gegnern in der obigen formalen Definition untersagt, den Schlüssel fest zu codieren? $k$?

Diese Frage mag zwar intuitiv sinnvoll sein, ist aber schlecht gestellt! (Einige Logiker bevorzugen es, solche Fragen mit "mu" zu beantworten . )

Was macht "der Schlüssel $k$"beziehen sich auf? Meinst du die $k$aus der Definition? Aber das ist für Gegner nicht sichtbar$\mathcal{A}$: Schauen Sie sich die Reihenfolge der Quantifizierer an. In etwa wird die folgende Kette von Variablen eingeführt (im CS-Jargon "gebunden"):

$\forall \mathcal{A}\ \exists \mathrm{negl}\ \forall n\ \ldots\ \Pr_{k\leftarrow_€\ \{0,1\}^n}[\ldots]\ \ldots$

Da Gegner $\mathcal{A}$ sind mehr außerhalb gebunden (dh zuerst) als $k$Aus der POV der Gegner gibt es keinen "Schlüssel" $k$". Wichtig ist, dass dieses Argument besagt, dass Gegner den Schlüssel möglicherweise nicht syntaktisch erfassen können."$k$". ^* Die einzige Stelle in der obigen Definition, an der" der Schlüssel$k$"syntaktisch macht Sinn im Körper von $\Pr_{k\leftarrow_€\ \{0,1\}^n}[\mathcal{A}(1^n, F(k,-))=1]$dh das Subterm $\mathcal{A}(1^n, F(k,-))=1$. Dies ist der einzige Begriff, der syntaktischen Zugriff auf "den Schlüssel" hat$k$".

Wohlgemerkt, es gibt mindestens zwei verschiedene (sich aber nicht gegenseitig ausschließende) semantische Wege, die ich mir vorstellen kann, um einige / viele Schlüssel zu erhalten:

1. Gegner könnten alle möglichen Werte von aufzählen $\{0,1\}^n$ Das $k$kann gebunden werden. Glücklicherweise ist für PPT-Gegner ein solches Bruteforcing mit einer exponentiellen (oder sogar superpolynomiellen) Größe im Sicherheitsparameter unmöglich$n$.
2. Für jeden möglichen Wert von $k$ (dh in $\{0,1\}^n$) könnte es einen Gegner geben$\mathcal{A}_k$ das kommt darauf an $k$ und erfüllt tatsächlich $\Pr[\mathcal{A}_k(1^n, F(k, -))] = 1] = 1$ und $\Pr_{f\leftarrow_€\ \{0,1\}^n\to\{0,1\}^n}[\mathcal{A}(1^n, f(-)) = 1] = 0$. Dies sieht fast so aus, als würde dies unsere gesamte Sicherheitsdefinition für PRFs seitdem unbrauchbar machen$|1 - 0| = 1$und das kann niemals weniger als eine vernachlässigbare Funktion sein. Beachten Sie jedoch entscheidend, dass ich sagte, dass es erfüllt$\Pr[\mathcal{A}_k(1^n, F(k, -))] = 1] = 1$ und nicht $\Pr_{k\leftarrow_€\{0,1\}^n}[\mathcal{A}_k(1^n, F(k, -))] = 1] = 1$. Es macht einen großen Unterschied, ob die Wahrscheinlichkeit über eine Stichprobe einer Zufallsvariablen übernommen wird oder nicht.

Notwendige Bedingungen für Sicherheitsdefinitionen

Zusammenfassend gibt es drei notwendige Bedingungen für den intuitiven, aber informellen Satz "Gegner kennen den Schlüssel nicht":

1. Syntaktisch sind Schlüssel an der Stelle, an der Gegner gebunden sind, nicht zugänglich.
2. semantisch werden Schlüssel aus einer Menge mit der Größe Superpolynom im Sicherheitsparameter abgetastet.
3. und wieder semantisch sind Schlüssel gebundene Zufallsvariablen, die Wahrscheinlichkeiten übernehmen.

Wenn eine dieser Bedingungen nicht erfüllt ist, ist die Sicherheitsdefinition höchstwahrscheinlich nicht sinnvoll und erfasst nicht das, was wir für erforderlich halten.

Takeaway: Bei der Formalisierung von Sicherheitsdefinitionen werden Werte, die Gegner nicht kennen sollten, durch Zufallsvariablen modelliert, über die die Wahrscheinlichkeit des Gewinns des Experiments übernommen wird. Diese werden häufig gleichmäßig zufällig aus einer exponentiell großen Menge ausgewählt.

Damit ist die Antwort auf Frage (1) abgeschlossen, warum / welche Hardcodierung zulässig ist.

Ein weiteres Beispiel mit "öffentlichen Werten" in Krypto

Hier ist ein weiteres Beispiel für eine Sicherheitsdefinition aus [Sch20]:

Def. (Datenschutz von RingCT): Ein RingCT-Schema$\Omega$ist privat, wenn für alle PPT-Gegner$\mathcal{A}$ und positive ganze Zahlen $\alpha, \beta \in \mathrm{poly}(\lambda)$, $$\Pr[\mathrm{Privacy}_{\Omega,\mathcal{A}}(\lambda, \alpha, \beta) = 1] \leq \frac{1}{2} + \mathrm{negl}(\lambda)$$

Was ist ein RingCT-Schema und wie ?$\mathrm{Privacy}$definiert ist, spielt überhaupt keine Rolle. Nützlicher für diese Diskussion ist der Umfang von$\alpha$ und $\beta$.

Mai Gegner $\mathcal{A}$ Hardcode $\alpha$ und $\beta$?

Ja, sie können sogar aus zwei verschiedenen Gründen (von denen einer ausreichen würde): - Bedingung 1. von oben ist gebrochen: syntaktisch - wie aus der Logik bekannt, können wir aufeinanderfolgende universelle Quantifizierer wie in neu ordnen $\forall \mathcal{A} \forall \alpha \forall \beta \ldots$so viel wir wollen. Daher können wir nachbestellen$\forall \alpha \forall \beta \forall \mathcal{A} \ldots$. - Bedingung 3. von oben ist gebrochen:$\alpha, \beta$sind keine gebundenen Zufallsvariablen, über die die Wahrscheinlichkeit genommen wird. Also für jeden solchen$\alpha, \beta$ Sie können mit einem Gegner kommen $\mathcal{A}_{\alpha, \beta}$.

Ein weiteres Beispiel von TCS

Am Anfang habe ich versprochen, dass das (Nicht-) Zulassen von Hardcoding-Dingen auch ein Thema in der theoretischen Informatik ist. Genauer gesagt geschieht dies in der Komplexitätstheorie , einem Teilfeld, das auch eng mit der Kryptographie verbunden ist.

Dort definieren wir Sprachen $L \subseteq \{0,1\}^\ast$ als Sets und fragen uns dann, wie schwer es für eine Turing-Maschine ist, sich für einige zu entscheiden $w \in \{0,1\}^\ast$ dass es als Eingabe bekommt ob $w \in L$oder nicht. Konkret definieren wir:

Def. (Entscheidbare Sprache).: Eine Sprache$L$ist entscheidbar, ob es eine Turingmaschine gibt$M$ so dass

• für alle $w \in L$, $M$ mit Eingabe $w$ hält akzeptabel an,
• und für alle $w' \not\in L$, $M$ mit Eingabe $w'$ lehnt ab.

Erinnern Sie sich an die drei oben genannten Bedingungen, die erforderlich sind, damit Sicherheitsdefinitionen in Krypto sinnvoll sind. Wie passen sie hierher?

Bedingung 1 ist seitdem erfüllt $w$ und $w'$ sind innerer gebunden als $M$. Obwohl$M$ empfängt beide als Eingaben - was in Krypto unvorstellbar wäre, wenn sie Schlüssel wären, gibt es immer noch einen entscheidenden Unterschied zwischen $M$ erforderlich, um mit all diesen Eingaben fertig zu werden und $M$muss für alle diese Eingänge vorhanden sein. (Letzteres wäre$\forall w \in L.\ \exists M.\ \ldots$) Dieser Unterschied ist ein häufiger Punkt der Verwirrung, wenn wir nehmen $L$das seine Halting Problem (eine un entscheidbar Sprache). Für jeden ("fest")$w \in H$ Es gibt eine Turingmaschine $M_w$ das akzeptiert iff. $w \in H$. ²

Darüber hinaus ist auch hier Bedingung 2. erfüllt, da Sprachen in der Regel zählbar unendlich sind. (Andernfalls wäre es langweilig, über die Komplexität der Berechnungen zu sprechen, wenn sie endlich wären.)

Schließlich ist Bedingung 3 hier nicht anwendbar, da keine Wahrscheinlichkeiten beteiligt sind.

---

Fußnoten und Referenzen

¹ : Die Erklärung, wie ich "syntaktisch" meine, erfordert einen CS-Hintergrund: Wann immer Sie die Sicherheitsdefinition instanziieren, an der Stelle, an der Sie den Gegner instanziieren$\mathcal{A}$ mit einem Begriff $t$, $t$ kann unmöglich einige enthalten $k$ da $k$ ist in diesem Zusammenhang einfach nicht sichtbar.

² : Mit klassischer Logik könnte man das für alle argumentieren$w \in \{0,1\}^\ast$, entweder $w \in H$ oder $w \not\in H$. Nehmen Sie im ersten Fall die Maschine, die sofort als akzeptiert$M_w$und im zweiten Fall nehmen Sie die Maschine, die sofort ablehnt.

[KL14]: Katz, J. & Lindell, Y. (2014). Einführung in die moderne Kryptographie. CRC Drücken Sie.

[Sch20]: Dominique Schröder. (2020). Kryptowährungen zur Wahrung der Privatsphäre. Unveröffentlichte Vorlesungsunterlagen für den gleichnamigen Kurs des Autors im Sommer 2020 an der FAU Erlangen-Nürnberg.https://www.chaac.tf.fau.eu/teaching/lectures/.