Cryptography Reference
In-Depth Information
restlichen Zufallsbits von
α
enthält, d. h.,
α
ensteht aus
α
durch Entfernen der Teile
α
[
j
i
(
α
)
,j
i
(
α
)+
l
i
)
. Insbesondere gilt
y
i
(
α
)=
α
[
j
i
(
α
)
,j
i
(
α
)+
l
i
)
für alle
i<n
,wobei
y
i
, wie üblich, als Zufallsvariable über
t
{
0
,
1
}
aufgefasst wird. Zeigen Sie die folgenden
Aussagen:
a) Die Abbildung
π
ist bijektiv.
b) Für jede Zufallsvariable
X
:
=Prob
X
π
−
1
=
c
t
{
0
,
1
}
→X
gilt
Prob
{
X
=
c
}
◦
für jedes
c ∈X
.Beachte:
X ◦ π
−
1
ist eine Zufallsvariable über
Ω
.
l
i
.
d) Die Zufallsvariablen
y
0
,...,y
n−
1
sind paarweise unabhängig.
Hinweis: Verwenden Sie b) für den Beweis von c) und d).
Aufgabe
4.9.14 (Beweis von Aussage (4.6.4))
.
Es seien
Ω
1
und
Ω
2
endliche nicht leere Men-
gen und
Ω
2
⊆ Ω
2
nicht leer. Wir betrachten die beiden Wahrscheinlichkeitsräume
(
Ω
1
×
Ω
2
,
2
Ω
1
×Ω
2
,P
)
und
(
Ω
1
×
=1
/
2
l
i
für alle
i<n
und
c
c) Es gilt
Prob
{
y
i
=
c
}
∈{
0
,
1
}
Ω
2
,
2
Ω
1
×Ω
2
,P
)
,wobei
P
bzw.
P
die Gleichverteilung auf
Ω
1
×
Ω
2
bzw.
Ω
1
× Ω
2
bezeichne. Zeigen Sie zunächst, dass
P
(
E|Ω
1
×Ω
2
)=
P
(
E∩
(
Ω
1
×Ω
2
))
für alle
E
Ω
2
gilt. Folgern Sie daraus, zusammen mit den Aussagen aus Aufga-
be 4.9.13, dass Gleichung (4.6.4) gilt.
Aufgabe
4.9.15 (bedingte Wahrscheinlichkeiten und der Algorithmus
A
(
x
)
⊆
Ω
1
×
)
.
In
dieser Aufgabe wollen wir zeigen, dass für die Aussage (4.6.4) die Voraussetzung, dass
der Variablen
y
genau einmal (statt lediglich höchstens einmal) ein Wert zugewiesen wird,
notwendig ist. Wir betrachten dazu die nach Beispiel 4.6.3 beschriebene verallgemeinerte
Definition der Zufallsvariablen
A
(
x
)
y
=
c
. Des Weiteren betrachten wir Algorithmus
A
aus Beispiel 4.6.4. Zeigen Sie, dass
i
y
=
c
und
c, c
∈{
∈{
0
,
1
,
2
,
3
}
0
,
1
}
existieren, so dass
Prob
{A
b
i
=
c
=
c
}
=Prob
{A
=
c
| b
i
=
c}
gilt.
Aufgabe
4.9.16 (Unterscheider auf Verschiebe-, ane und Vigenèrechiffren)
.
Beschreiben
Sie nach dem Muster von Beispiel 4.7.1 gute Unterscheider für Verschiebe- und ane
sowie Vigenèrechiffren und bestimmen Sie ihre Vorteile.
Aufgabe
4.9.17 (Unterscheider auf Vernamsystem)
.
Der Unterscheider auf das Vernam-
system aus Beispiel 4.7.1 ist nicht erfolgreich für
l
=1
. Zeigen Sie, dass dies in der
Tat für jeden Unterscheider gilt, d. h., dass es keinen
1
-Unterscheider gibt, der bzgl. des
Vernamsystems mit
l
=1
einen Vorteil
>
0
besitzt.
Aufgabe
4.9.18 (alternativer Wahrscheinlichkeitsraum: Orakel für erstes Bit)
.
Betrachten
Sie den in der Fußnote auf Seite 86 beschriebenen alternativen Produktraum zu
S
.
a) Geben Sie auf dieser Basis einen alternativen Beweis zu Aussage (4.7.3) an, in dem,
wie zuvor, eine bijektive Abbildung zwischen Läufen betrachtet wird.
b) Geben Sie einen weiteren alternativen Beweis zu Aussage (4.7.3) an, der die Unab-
hängigkeit der Zufallsvariablen
x
und
y
sowie Lemma 3.3.6 ausnutzt.
Aufgabe
4.9.19 (Orakel für erstes Bit mit Anfrage)
.
Wir betrachten die Situation aus
Beispiel 4.7.2, nehmen aber nun an, dass der (deterministische) Algorithmus
O
neben
dem Chiffretext
y
zusätzlich Zugriff auf eine
l
-Blockchiffre
F
von
B
besitzt, die er ge-
nau einmal abfragt. Das Experiment
E
bit
sowie der Unterscheider
U
sind wie in Bei-
spiel 4.7.2 definiert, wobei allerdings
O
(
y
)
durch
O
(
F,y
)
ersetzt wird. Es soll wieder
