Cryptography Reference
In-Depth Information
Bemerkung
5.4.1
.
Für die R-CBC-Betriebsart können ähnliche Aussagen wie in Satz 5.4.1
und Folgerung 5.4.1 gemacht werden, allerdings ist, wie bereits erwähnt, der Beweis
aufwändiger.
Im Rest des Abschnitts widmen wir uns dem Beweis von Satz 5.4.1. Es seien dazu
t, n, q, l
sowie
)
wie in den Voraussetzungen des Satzes gegeben.
Wir werden im Folgenden zunächst annehmen, dass
B
,
S
und
A
=(
AF
,
AG
B
eine pseudozufällige Funktion
ist, statt einer pseudozufälligen Permutation (siehe Abschnitt 4.8). Unsere Aussagen
werden also zunächst adv
PRF
(
U,
)
betreffen. Den
Schritt zu adv
PRP
(
U,B
)
wird uns dann das PRF/PRP-Switching Lemma (Lemma 4.8.1)
erlauben.
Die Konstruktion des Unterscheiders
U
für
B
)
statt adv
(
U,
B
)=
adv
PRP
(
U,
B
B
aus
A
ist sehr leicht. Der Unterscheider
U
E
A
, wobei allerdings der erste Schritt, die Chiffrewahl,
weggelassen wird (siehe unten). Auch die Ausgabe von
U
wird genau die Ausgabe des
simulierten Experimentes sein.
Da
U
als Orakel lediglich eine Blockchiffre
F
zur Verfügung steht,
A
aber erwartet,
dass Orakelanfragen gemäß dem R-CTR-Kryptoschema
simuliert einfach das Experiment
S
beantwortet werden, muss
U
bei Orakelanfragen von
A
sein Orakel
F
verwenden, um die R-CTR-Betriebsart zu
simulieren. Wie der folgende Algorithmus zeigt, ist dies aber einfach möglich. In diesem
Algorithmus, wie auch im weiteren Verlauf des Abschnitts, bezeichnet '
' die Konkatena-
tion von Bitvektoren. Mit
x
(
i
)
bezeichnen wir, wie üblich, den
i
-ten
l
-Block im Klartext
x
.
·
l∗
,F
:
{
0
,
1
}
l
l
):
{
0
,
1
}
∗
Sim(
x
:
{
0
,
1
}
→{
0
,
1
}
1.
r
=
flip
(
l
)
.
2. Setze
m
=
|x|/l
und
y
=
r·
(
F
(
r
)
⊕ x
(0)
)
·····
(
F
(
r
+
2
l
m −
1)
⊕ x
(
m−
1)
)
.
3. Gib
y
zurück.
E
A
eine Orakelanfrage
x
,soruft
U
einfach
Sim(
x, F
)
auf. Ebenso ruft
U
die Prozedur
Sim
auf, um eine Antwort auf das Angebot von
A
zu
berechnen. Insgesamt ist der Unterscheider
U
zu
A
=(
Stellt
A
in der Simulation von
AF
,
AG
)
,der
Sim
als Prozedur
verwendet, also wie folgt definiert:
l
l
):
U
(
F
:
{
0
,
1
}
→{
0
,
1
}
{
0
,
1
}
1.
Findungsphase
(
z
0
,z
1
)=
AF
(Sim(
·
,F
))
2.
Auswahl
c
=
flip
()
;
y
= Sim(
z
c
,F
)
3.
Ratephase
c
=
AG
(Sim(
·
,F
)
,y
)
4.
Auswertung
falls
c
=
c
,sogib
1
, sonst
0
zurück
Hinter dieser Konstruktion von
U
steckt die folgende Idee: Läuft
U
in der Realwelt,
in der, nach Definition,
F
eine zufällig gewählte Blockchiffre von
B
ist, dann wird, wie
