Cryptography Reference
In-Depth Information
zur Verschlüsselung gewählte Angebotshälfte, z = z 1 −c ( α ) sei die andere Angebotshälfte
und r q der zur Verschlüsselung von z gewählte initiale Zähler. Damit hat die in diesem
Lauf zurückgelieferte Probe y = y ( α ) , also der Chiffretext zu z ,dieForm
y = r q · ( F ( r q ) ⊕ z (0) ) · ··· · ( F ( r q + 2 l ( n q 1)) ⊕ z ( n q 1) ) .
Es sei nun α = β ( α ) der Lauf, der genau mit α übereinstimmt, bis auf die folgenden
Änderungen. Das Bit c ( α ) werde gekippt, für α
gelte also c ( α )=1
c ( α ) . Außerdem
sei die in α gewählte Chiffre F = F ( α ) wie folgt definiert: F ( j )= F ( j ) für alle
j∈{r q ,r q + 2 l 1 ,...,r q + 2 l ( n q 1) }
und
F ( r q + 2 l i )= F ( r q + 2 l i )
z [ i
z [ i
·
l, ( i +1)
·
l )
·
l, ( i +1)
·
l )
(5.4.10)
für alle i
∈{
0 , ..., n q
1
}
.
Wegen α ∈ Coll
gilt offensich tlich auch α ∈ Coll
, da die Zähler in α genauso gewählt
sind wie in α . Die Annahme α
r q ,r q + 2 l 1 ,...,r q + 2 l n q
1 } für die Beantwortung des Angebots an keiner anderen Stelle auftreten. Der Wechsel
von F (in α )hinzu F (in α ) hat also auf die gelieferten Antworten für die von A
gestellten Orakelanfragen keinerlei Auswirkung. Insbesondere ist die Sicht von A bis zur
Unterbreitung des Angebots in α und α identisch. Folglich liefert A in beiden Läufen
dasselbe Angebot. Gemäß der Definition von α wird im Lauf α die Angebotshälfte z ,
statt z , verschlüsselt. Nach Konstruktion von F ist aber die zurückgelieferte Probe, also
der Chiffretext zu z , genau die für z im Lauf α gelieferte Probe, nämlich y .Demnach
bleibt die Sicht von A auch nach Unterbreitung des Angebots gleich. Folglich liefert A
dieselbe Ausgabe, d. h., es gilt c ( α )= c ( α ) .Aberdain α
∈ Coll
bedeutet, dass die Zähler
{
das Bit c gekippt ist, d. h.,
c ( α )=1
c ( α ) , erhalten wir, wie gewünscht, dass c ( α )= c ( α ) gilt, genau dann, wenn
c ( α )
= c ( α ) gilt. Es bleibt noch zu zeigen, dass β eine bijektive Abbildung von
Coll
nach
ist. Davon kann man sich aber leicht überzeugen (siehe Aufgabe 5.7.9).
Mit (5.4.2) und (5.4.8) ergibt sich nun für den Vorteil von U :
Coll
adv PRF ( U,
B
)= suc PRF ( U,
B
)
fail PRF ( U,
B
)
adv ( A,
S
)+1
( 1
2 + qn
2 l )
2
= adv ( A,
S
)
qn
2 l
.
2
Mit Hilfe des PRP/PRF-Switching Lemmas (Lemma 4.8.1) folgt sofort
n 2
2 l +1
adv ( A,
S
)
qn
2 l
adv PRP ( U,B )
2
2 qn + n 2
2 l +1
adv ( A,
S
)
2
und damit (5.4.1).
Nach Konstruktion ist auch klar, dass U höchstens n Orakelanfragen macht. Außerdem
ist die Laufzeit von
E A ,dienach
Annahme durch t beschränkt ist. In der Zufallswelt werden Orakelanfragen in
E U ,wenn U in der Realwelt läuft, gleich zur Laufzeit von
E U durch
 
Search WWH ::




Custom Search