Musterlösung 5

Moderator: Einführung in die Kryptographie

yagami
Mausschubser
Mausschubser
Beiträge: 72
Registriert: 5. Okt 2006 03:02

Musterlösung 5

Beitrag von yagami » 6. Jan 2012 13:36

Hallo,
Ich habe gerade ein Problem ein Schritt in der Musterlösung Übung 2 c zu verstehen... Weisst jemand wie kommt man auf |Prob[ D(X) = 1] − Prob[ D(Y ) = 1]| ≤ 2 · Prob[ Y ∈ ZN \ ZN* ] ≈ 0 von der vorherigen Zeile?
Danke im voraus,

FeG
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

Re: Musterlösung 5

Beitrag von FeG » 7. Jan 2012 18:43

Hi,

das wird denke ich klarer, wenn man es ein bisschen ausführlicher aufschreibt:

\(\begin{align*}
|Pr[D(X)=1] - Pr[D(Y) = 1]| &=
| Pr[D(X)=1 \mid Y \not\in \mathbb{Z}_N \setminus \mathbb{Z}_N^*] \cdot Pr[Y \not\in \mathbb{Z}_N \setminus \mathbb{Z}_N^*]\\
&~+ Pr[D(X)=1 \mid Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*] \cdot Pr[Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*]\\
&~- Pr[D(Y)=1 \mid Y \not\in \mathbb{Z}_N \setminus \mathbb{Z}_N^*] \cdot Pr[Y \not\in \mathbb{Z}_N \setminus \mathbb{Z}_N^*]\\
&~- Pr[D(Y)=1 \mid | Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*] \cdot Pr[Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*] | \\
&\approx | Pr[D(X)=1 \mid Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*] \cdot Pr[Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*]\\
&~- Pr[D(Y)=1 \mid Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*] \cdot Pr[Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*] |\\
&~\qquad (\mbox{since } Pr[D(X)=1 \mid Y \not\in \mathbb{Z}_N \setminus \mathbb{Z}_N^*] = Pr[D(X) = 1] \approx Pr[D(Y)=1 \mid Y \not\in \mathbb{Z}_N \setminus \mathbb{Z}_N^*])\\
&= | \underbrace{(Pr[D(X)=1 \mid Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*] - Pr[D(Y)=1 \mid Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*])}_{|\dots| \leq 1} \cdot Pr[Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*] |\\
&\leq Pr[Y \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*]\\
&\approx 0
\end{align*}\)


Meines Erachtens ist der Vorfaktor 2 in der Musterlösung also überflüssig (wenn auch natürlich nicht falsch...).

Viele Grüße
Felix

Antworten

Zurück zu „Einführung in die Kryptographie“