De dragul lizibilității, ajustăm oarecum notația.
Lăsa $\Pi=(Gen,Enc,Dec)$ fi a $\mathsf{CPA}$-schemă de criptare securizată cu cheie publică cu spațiu pentru mesaje $\mathcal{M}$. Dorim să dovedim asta $\Pi^2=(Gen^2,Enc^2,Dec^2)$, cu spațiu pentru mesaje $\mathcal{M}\times\mathcal{M}$ este de asemenea $\mathsf{CPA}$-sigur, unde
$\subliniat{(pk,sk)\gets Gen^2(1^n)}$:
- $(pk_\alpha,sk_\alpha)\obține Gen(1^n)$
- $(pk_\beta,sk_\beta)\obține Gen(1^n)$
- $(pk,sk):= \big((pk_\alpha,pk_\beta),(sk_\alpha,sk_\beta)\big)$
$\underline{c\gets Enc^2(pk,m)}$:
- $(pk_\alpha,pk_\beta) := pk$
- $(m_\alpha,m_\beta) := m$
- $c_\alpha \gets Enc(pk_\alpha,m_\alpha)$
- $c_\beta \gets Enc(pk_b,m_\beta)$
- $c:=(c_\alpha,c_\beta)$
$\subliniat{m := Dec^2(sk,c)}$:
- $(sk_\alpha,sk_\beta) := sk$
- $(c_\alpha,c_\beta) := c$
- $m_\alpha := Dec(sk_\alpha, c_\alpha)$
- $m_\beta := Dec(sk_\beta, c_\beta)$
- $m := (m_\alpha,m_\beta)$.
Putem demonstra următoarea afirmație prin demonstrarea contrapozitivului, i.e
$\underline{Revendicare:}$
\begin{align*}
&\Pi\text{ este $\mathsf{CPA}$-securizat}\implies\Pi^2\text{ este $\mathsf{CPA}$-securizat} \
\iff &\Pi^2\text{ este $\lnot\mathsf{CPA}$-secure}\implies\Pi\text{ este $\lnot\mathsf{CPA}$-secure}.
\end{align*}
$\subliniat{Dovada:}$
Pentru a demonstra contrapozitivul, presupunem că există un adversar $\mathcal{A}^2$ împotriva $\Pi^2$, astfel încât $$\Pr[\mathsf{PubK}^{\mathsf{CPA}}_{\mathcal{A}^2,\Pi^2}(n)=1]>\frac{1}{2}+\ mathsf{negl}(n).$$
Cu alte cuvinte, $\mathcal{A}^2$ poate câștiga împotriva $\Pi^2$ în $\mathsf{CPA}$ joc cu avantaj deloc neglijabil.
Vom folosi acum $\mathcal{A}^2$ a construi un adversar $\mathcal{A}$ împotriva $\Pi$ în $\mathsf{CPA}$ joc.
The $\mathsf{CPA}$ jocul se desfășoară după cum urmează:
- $Gen(1^n)$ este rulat pentru a obține chei $(pk_\alpha, sk_\alpha)$.
- Adversar $\mathcal{A}$ este dată $pk_\alpha$ precum și accesul oracol la $Enc(pk_\alpha,\cdot)$. Următorul, $\mathcal{A}$ aleargă $Gen(1^n)$ a obtine $(pk_\beta, sk_\beta)$.
- Adversar $\mathcal{A}^2$ este dată $pk:=(pk_\alpha,pk_\beta)$ precum și accesul oracol la $Enc^2(pk,\cdot)$.
- $\mathcal{A}^2$ emite o pereche de mesaje distincte $m_0:=(m_{0_\alpha},m_{0_\beta}), m_1:=(m_{1_\alpha},m_{1_\beta}) \in\mathcal{M}\times\mathcal{ M}$ cu $m_{0_\beta} = m_{1_\beta}$ și $|m_0|=|m_1|$. Cu alte cuvinte, mesajele $m_0$, $m_1$ sunt diferite, dar a doua jumătate este aceeași.
- Dupa primire $m_0$ și $m_1$ din $\mathcal{A}^2$, adversarul $\mathcal{A}$ înaintează doar primele părți $m_{0_\alpha}$,$m_{1_\alpha}$ la $\mathsf{CPA}$ joc.
- Jocul alege un bit aleatoriu $b \in \{0, 1\}$, și textul cifrat de provocare $c_\alpha \gets Enc(pk_\alpha, m_{b_\alpha})$ este calculat și dat la $\mathcal{A}$. $\mathcal{A}$ continuă să aibă acces la $Enc(pk_\alpha,\cdot)$.
- Acum $\mathcal{A}$ calculează a doua jumătate a textului cifrat de provocare ca $c_\beta \gets Enc(pk_\beta, m_{0_\beta}=m_{1_\beta})$. Rețineți că $\mathcal{A}$ nu trebuie să cunoască partea de provocare $b$. Atunci, $\mathcal{A}$ trimite textul cifrat de provocare \begin{align*} c&:=(c_\alpha,c_\beta)\&:=\big(Enc(pk_\alpha, m_{b_\alpha}),Enc(pk_\beta, m_{0_\ beta}=m_{1_\beta})\big)\end{align*} la $\mathcal{A}^2$. $\mathcal{A}^2$ continuă să aibă acces la $Enc^2(pk,\cdot)$.
- $\mathcal{A}^2$ întoarce un pic de ghicire $b''$ la $\mathcal{A}$.
- $\mathcal{A}$ își stabilește propria ghicire $b':=b''$, și se întoarce $b'$ la $\mathsf{CPA}$ joc.
- Ieșirea jocului este definită a fi $1$ dacă $b'= b$, și $0$ in caz contrar.
Din reducere rezultă că, \begin{align*} \Pr[\mathsf{PubK}^{\mathsf{CPA}}_{\mathcal{A},\Pi}(n)=1]&=\Pr[\mathsf{PubK}^ {\mathsf{CPA}}_{\mathcal{A}^2,\Pi^2}(n)=1] \&>\frac{1}{2}+\mathsf{negl}(n). \end{align*}
Aici, ultima inegalitate rezultă din presupunerile noastre că $\mathcal{A}^2$ poate câștiga împotriva $\Pi^2$ în $\mathsf{CPA}$ joc cu avantaj deloc neglijabil.
În cele din urmă, aceasta demonstrează afirmația inițială că $\Pi\text{ este $\mathsf{CPA}$-securizat}\implies\Pi^2\text{ este $\mathsf{CPA}$-securizat}$. $\;\blacksquare$
