Cryptography Reference
In-Depth Information
AG
(
H,y
)
:
3.
Simuliere zweiten Teil von
U
.
W
Dieser Angreifer lässt sich auch leicht analysieren:
Lemma 5.5.2.
Es sei
U
ein
l
-Unterscheider für Kryptoschemen, der in jedem Lauf
genau eine Orakelanfrage stellt, und
ein symmetrisches
l
-Kryptoschema. Dann gilt
für den Angreifer
A
gemäß obiger Konstruktion:
S
adv
(
A,
S
)=
adv
RR
(
U,
S
)
.
Beweis.
Man sieht sofort, dass
suc
(
A,S
)=Prob
S
A
b
=1
=1
=Prob
S
U
b
=1
=1
=
suc
RR
(
U,S
)
S
A
gilt, denn die Sicht des durch
A
simulierten Unterscheiders
U
in
b
=1
ist genau so
S
U
b
=1
verteilt, wie die Sicht von
U
in
.
Genauso sieht man, dass
fail
(
A,S
)=Prob
S
A
b
=0
=1
=Prob
S
U
b
=0
=1
=
fail
RR
(
U,S
)
gilt. Insgesamt folgt:
adv
(
A,
S
)=
suc
(
A,
S
)
−
fail
(
A,
S
)
=
suc
RR
(
U,S
)
−
fail
RR
(
U,S
)
=
adv
RR
(
U,
S
)
.
Wir werden nun die oben beschriebene Konstruktion auf Unterscheider verallgemei-
nern, die höchstens
q
Anfragen, für
q
0
, durchführen. Dazu »zerschneiden« wir einen
solchen Unterscheider zufällig an einer der Anfragen und gehen analog zu oben vor. Diese
zusätzliche zufällige Entscheidung führt dann dazu, dass der gesamte Angreifer weniger
erfolgreich ist als der gegebene Unterscheider; für seinen Vorteil können wir nur noch den
q
-ten Teil garantieren.
Wir gehen im Folgenden von einem Unterscheider
U
aus, der in jedem Lauf
genau
q
Anfragen stellt, für
q>
0
. Sollte
U
dies nicht tun, so kann man leicht einen neuen Unter-
scheider
U
konstruieren, der sich genau wie
U
verhält, allerdings weitere Orakelanfragen
stellt, falls
U
weniger als
q
Anfragen gestellt hat. Die Antworten auf diese Anfragen wer-
den einfach ignoriert. Offensichtlich hat
U
denselben Vorteil, Erfolg und Misserfolg wie
U
.
≥
konstruieren wir zunächst einen Angreifer
A
i
nach dem oben
beschriebenen Muster. Wir können uns ohne Beschränkung der Allgemeinheit vorstellen,
dass wir
U
für jedes
i
in der Form
Für jedes
i
∈{
1
,...,q
}
V
i
;
y
i
=
H
(
x
i
)
;
W
i
(5.5.3)
