Sichern Sie den MAC, wenn der Gegner ein Verifizierungsorakel hat

Ein Nachrichtenauthentifizierungscode (MAC) wird durch ein Dreifach effizienter Algorithmen , die die folgenden erfüllen (die Definition stammt aus Abschnitt 4.3 des Katz -Lindell Buch ):$(\mathsf{Gen}, \mathsf{MAC}, \mathsf{Verif})$

• Bei Eingabe generiert der Algorithmus einen Schlüssel .$1^n$$\mathsf{Gen}$$k \ge n$
• Bei der von generierten Eingabe und einer Nachricht generiert der Algorithmus ein Tag . Wir schreiben .$k$$\mathsf{Gen}$$m \in \{0,1\}^*$$\mathsf{MAC}$$t$$t \gets \mathsf{MAC}_k(m)$
• Bei der Eingabe eines Tripels der Algorithmus ein einzelnes Bit . Wir schreiben .$(k,m,t)$$\mathsf{Verif}$$b$$b \gets \mathsf{Verif}_k(m,t)$

Es ist erforderlich , daß für alle Ausgabe durch und alle , haben wir .$k$$\mathsf{Gen}$$m \in \{0,1\}^*$$\mathsf{Verif}_k(m, \mathsf{MAC}_k(m)) = 1$

Die Sicherheitsanforderung wird über das folgende Experiment zwischen dem Herausforderer und dem Gegner :$A$

1. $k \gets \mathsf{Gen}(1^n)$ .
2. $(m,t) \gets A^{\mathsf{MAC}_k(\cdot)}(1^n)$ .
3. Es sei bezeichnen die Menge aller Abfragen, die zu seinem Orakel gefragt.$Q$$A$
4. Die Ausgabe des Experiments wird genau dann als 1 definiert, wenn:
   • $\mathsf{Verif}_k(m, t) = 1$ und
   • $m \notin Q$ .

Der MAC wird als sicher angesehen, wenn die Wahrscheinlichkeit, dass das Experiment 1 ausgibt, in vernachlässigbar ist .$n$

Das obige Experiment ähnelt einem "ausgewählten Klartext" -Experiment gegen ein symmetrisches Verschlüsselungsschema, bei dem der Gegner Chiffretexte erhalten kann, die Nachrichten seiner Wahl entsprechen. Bei einem stärkeren Angriff, der als "gewählter Chiffretext" -Angriff bezeichnet wird, erhält der Gegner auch Zugriff auf ein Entschlüsselungsorakel.

Meine Frage lautet also:

Was passiert, wenn wir dem MAC-Gegner erlauben, auch auf ein Verifizierungsorakel zuzugreifen? Mit anderen Worten, was ist, wenn Zeile 2 des Experiments durch Folgendes ersetzt wird:

$(m,t) \gets A^{\mathsf{MAC}_k(\cdot),\ \ \mathsf{Verif}_k(\cdot, \cdot)}(1^n)$ .

Beachten Sie, dass im neuen Experiment nur Abfragen enthält, die vom Orakel .$Q$$A$$\mathsf{MAC}_k$

Wenn es eine sichere ist Message Authentication Code nach jeder Definition,
dann gibt es ein System, das die Definition stuft das Buch als eine sichere
Nachrichtenauthentifizierungscode und Ihre Definition klassifiziert als unsicher.

Lassen Sie gemäß jeder Definition sicher sein. Da die Definition des Buches schwächer ist als Ihre Definition, ist sie gemäß der Definition des Buches besonders sicher. Korrigieren Sie eine effizient berechenbare und effizient invertierbare Codierung geordneter Paare, indem Sie beispielsweise eine effizient berechenbare und effizient invertierbare präfixfreie Darstellung des linken Eintrags mit dem rechten Eintrag verketten . Lassen Sie arbeiten, indem Sie die Ausgabe von$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.02 in},\hspace{-0.05 in}\operatorname{Verif}\hspace{.02 in}\rangle\:$$\;\;$




$\operatorname{MAC}_k\hspace{-0.09 in}'$$\operatorname{MAC}_k$mit der leeren Zeichenfolge.
Lassen Sie genau dann akzeptieren, wenn [[ die Nachricht und den linken Eintrag des Tags akzeptieren würde ] und [der rechte Eintrag der Eingabe a ist Präfix von ]]. ist eindeutig effizient und erfüllt die Anforderung. Da [die Tags mit der leeren Zeichenfolge für koppeln] und [den linken Eintrag der Ausgabe von] einen möglichen Gegner angreift, der das Buch angreift $\operatorname{Verif}_k\hspace{-0.09 in}'$$\operatorname{Verif}_k$
$k$$\;\;$ $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$$\;\;\;$

Definition der Sicherheit von kann kein Nicht- haben vernachlässigbare Wahrscheinlichkeit , die Sicherheitsdefinition des Buches für , Die Definition des Buches wird ebenfalls klassifiziert$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$
$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.02 in},\hspace{-0.05 in}\operatorname{Verif}\hspace{.03 in}\rangle\:$$\:$
$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{-0.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ als sicherer Nachrichtenauthentifizierungscode.
Sobald ein Gegner jedoch ein gültiges Nachricht-Tag-Paar für erhält , Adaptive Abfragen an reichen aus, um zu lernen , was Fälschungen für jede Nachricht ermöglichen würde. Somit klassifiziert Ihre Definition$k$$\:2\hspace{-0.03 in}\cdot \hspace{-0.03 in}(\operatorname{length}(k)\hspace{-0.04 in}+\hspace{-0.05 in}1)\:$
$\operatorname{Verif}_k\hspace{-0.09 in}'$$k\hspace{.01 in}$
$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{-0.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ as unsicher. QED$\;\;\;$

Die starken Unverfälschbarkeitsversionen der beiden Definitionen sind gleichwertig.

(Die "starke Unverfälschbarkeit" -Versionen werden erhalten, indem durch die in meinem nächsten Satz angegebene Menge ersetzt wird. Dies ist erforderlich, damit die Encrypt-Then-Mac- Konstruktion Chiffretext-Integrität bietet und IND-CCA2 ist.)$Q$
$Q^+$

Initialisieren Sie als leere Menge und setzen Sie in jedes Mal, wenn on ausgibt eine Abfrage von . Definieren Sie eine Abfrage, die nur dann versucht werden soll , wenn sie an ein Paar, das bereits in . Definieren Sie eine Abfrage so, dass sie nur dann frühzeitig versucht wird, wenn sie versucht wird und nicht nach einer versuchten Abfrage erfolgt ist, die akzeptiert. $\:Q^+\:$$\: \langle m,\hspace{-0.03 in}t\rangle \:$$\:Q^+$
$\operatorname{MAC}_k$$t$$m$

$\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$$\:Q^+\:$

$\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$


$B^{\hspace{.02 in}\operatorname{MAC}_k(\cdot)}\hspace{-0.02 in}\left(\hspace{-0.03 in}1^n,\hspace{-0.02 in}q,\hspace{.02 in}j\hspace{-0.01 in}\right) \;$interagiert mit wie folgt:$A$

mit weniger als zufälligen Bitsfast gleichmäßig. "Forward" alle ‚s Abfragen und geben , das von Oracle (actual) ausgegeben , gib als die Ausgaben auf dem ersten bis versuchen Abfragen, und geben$\hspace{.02 in}j$$\;\; r \: \in \: \left\{\hspace{-0.03 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.03 in}3,...,\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.04 in}2\hspace{.02 in},\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.05 in}1,\hspace{-0.02 in}q\hspace{-0.02 in}\right\} \;\;$
$A$$\:\operatorname{MAC}_k(\cdot)\:$$\:\operatorname{MAC}_k(\cdot)\:$
$A$$0$$r\hspace{-0.04 in}-\hspace{-0.05 in}1$
$1$ als von bei Abfragen, die nicht versucht werden. Wenn führt eine te versuchende Abfrage durch und gibt dann aus, was diese Abfrage war. Wenn gibt die Ausgabe aus und gibt dann dieselbe Ausgabe aus. Wenn die Zufälligkeit von allem behoben ist, wenn$\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$
$\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$$r$
$\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$


$\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$macht genau früh versuchende Abfragen und ist erfolgreich in der starken Unverfälschbarkeitsversion Ihres Experiments, dann Erfolgreich im Experiment des Versionsbuchs für starke Unverfälschbarkeit.$\:r\hspace{-0.03 in}-\hspace{-0.04 in}1\:$
$B^{\hspace{.02 in}A,\operatorname{MAC}_k(\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n,\hspace{-0.02 in}q,\hspace{.02 in}j\hspace{-0.01 in}\right)\:$

Daher ist eine konstruktive geradlinige Reduktion vom Erfolg der starken Unverfälschbarkeitsversion Ihres Experiments mit einer Wahrscheinlichkeit von mindestens in einer Weise, die weniger als frühzeitige Abfragen ermöglicht, zum Erfolg in der starken Unverfälschbarkeitsversion des Buchexperiments mit Wahrscheinlichkeit größer als. verwendet weniger als zufällige Bits, muss Einfügungen in und Mitgliedschaftstests für [eine Menge mit weniger als$B$$\epsilon$
$q$
$\;\; \left(\hspace{-0.03 in}\frac1q\hspace{-0.03 in}-\hspace{-0.03 in}\frac{q}{2\text{^}j}\hspace{-0.04 in}\right)\cdot \epsilon \;\;\;$
$B$$\hspace{.02 in}j$
$q$Elemente, von denen jedes ein geordnetes Paar , dessen
linke Eintrag ist einer der inneren Algorithmus Abfragen und rechten Eintrag , dessen ist ‚s Antwort auf diese Abfrage] und hat darüber hinaus nur eine geringfügige zusätzliche Komplexität.$\:\operatorname{MAC}_k\:$
$\operatorname{MAC}_k\hspace{-0.02 in}$$\:$

"Ignoriere das Orakel " ist eine konstruktive geradlinige Reduktion vom Erfolg in der starken Unverfälschbarkeitsversion des Buchexperiments zum Erfolg in der starken Unverfälschbarkeitsversion deines Experiments, und diese Reduktion ist fast vollkommen eng. Daher liefert die Version Ihrer Definition mit starker Unverfälschbarkeit dieselben asymptotischen MACs wie die Version mit starker Unverfälschbarkeit, mit der das Buch experimentiert. $\operatorname{Verif}_k$