Symmetrische Authentifizierungsverfahren - Moderne Kryptographie - page 209

Satz 9.3.1. Es seien M B wie oben definiert. Dann existiert eine (kleine) Kon-

stante c , so dass für alle l,q,t > 0 und ( l · q,q,t ) -beschränkten Fälscher F für

B und

M B ein

( q,t + c · l · q · log( q )) -beschränkter l -Unterscheider U für B existiert mit

)+ 2+ q · ( q − 1)
2 l +1

adv MAC ( F, M B ) ≤ adv ( U, B . (9.3.1)

Beweis. Es seien M B , l , q , t und F wie in der Voraussetzung des Satzes gegeben.

Gemäß Definition 4.7.2 ist die Aufgabe des zu konstruierenden Unterscheiders U ( G ) ,der
ein Chiffrierorakel G als Parameter erhält, zu bestimmen, ob die Chiffre G von

B ,

stammt
oder eine zufällige Funktion ist; wegen Lemma 4.8.1 (PRF/PRP-Switching Lemma) kön-
nen wir zunächst zufällige Funktionen statt zufällige Permutationen betrachten.
Um zwischen

B

und einer zufälligen Funktion zu unterscheiden, simuliert U ( G ) ein-
fach das gesamte Experiment

B

E M F , mit Ausnahme der Schlüsselwahl; die Aufgabe des
Etikettierorakels übernimmt dabei G .
Die Intuition hierbei ist die folgende: Falls G von B stammt, so simuliert U genau das

E M F (bis auf die Schlüsselwahl). Ist insbesondere F ein guter Fälscher, so
wird die Berechnung von F mit hoher Wahrscheinlichkeit erfolgreich und zulässig sein.
Der Unterscheider U gibt deshalb mit hoher Wahrscheinlichkeit 1 aus - glaubt also, dass
G von

Experiment

stammt. Ist dagegen G eine zufällige Funktion, dann wird, wie oben angedeutet,
die Berechnung von F mit hoher Wahrscheinlichkeit nicht sowohl erfolgreich als auch
zulässig sein. In diesem Fall gibt U also mit hoher Wahrscheinlichkeit 0 aus - glaubt also,
dass G eine zufällige Funktion ist. Insgesamt sollte U damit gut unterscheiden können,
ob G von

B

B stammt oder eine zufällige Funktion ist. Wir werden dieses Argument nun

präzisieren.
Der Unterscheider U ist wie folgt definiert:

l l ):

U ( G : { 0 , 1 } →{ 0 , 1 } { 0 , 1 }

1. Initialisierung
S = ∅
2. Berechnung eines Nachrichten-Etikett-Paares durch Simulation von F
F , wobei Anfragen x von F wie folgt beantwortet werden:
S = S x }

gib G ( x ) als Antwort zurück an den simulierten Algorithmus F
Es bezeichne ( x, t ) die Ausgabe von F .
3. Auswertung
falls die Berechnung von F erfolgreich und zulässig war, d. h. G ( x )= t und
x/

∪{

∈ S ,danngib 1 , sonst 0 aus.

S

PRF
U

b =1 ,alsodasExperiment

Man sieht nun in der Tat leicht, dass das Experiment

E M B
F

PRF
U

S für den Fall, dass G von B stammt, genau dem Experiment entspricht. Wir

erhalten insbesondere:

)=Prob S =1

PRF
U

suc PRF ( U, B b =1

= adv MAC ( F,M B ) .