Để dễ đọc, chúng tôi điều chỉnh ký hiệu một chút.
Để cho $\Pi=(Gen,Enc,Dec)$ là một $\mathsf{CPA}$-chương trình mã hóa khóa công khai an toàn với không gian tin nhắn $\mathcal{M}$. Chúng tôi muốn chứng minh rằng $\Pi^2=(Gen^2,Enc^2,Dec^2)$, với không gian tin nhắn $\mathcal{M}\times\mathcal{M}$ cũng $\mathsf{CPA}$-an toàn, ở đâu
$\underline{(pk,sk)\gets Gen^2(1^n)}$:
- $(pk_\alpha,sk_\alpha)\get Gen(1^n)$
- $(pk_\beta,sk_\beta)\get 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)$
$\underline{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)$.
Chúng ta có thể chứng minh khẳng định sau bằng cách chứng minh điều ngược lại, tức là
$\underline{Yêu cầu:}$
\begin{align*}
&\Pi\text{ là $\mathsf{CPA}$-secure}\implies\Pi^2\text{ là $\mathsf{CPA}$-secure} \
\iff &\Pi^2\text{ là $\lnot\mathsf{CPA}$-secure}\implies\Pi\text{ là $\lnot\mathsf{CPA}$-secure}.
\end{align*}
$\underline{Bằng chứng:}$
Để chứng minh điều ngược lại, chúng ta giả sử tồn tại một đối thủ $\mathcal{A}^2$ chống lại $\Pi^2$, như vậy mà $$\Pr[\mathsf{PubK}^{\mathsf{CPA}}_{\mathcal{A}^2,\Pi^2}(n)=1]>\frac{1}{2}+\ mathsf{negl}(n).$$
Nói cách khác, $\mathcal{A}^2$ có thể thắng $\Pi^2$ bên trong $\mathsf{CPA}$ trò chơi với lợi thế không đáng kể.
Bây giờ chúng ta sẽ sử dụng $\mathcal{A}^2$ để xây dựng một kẻ thù $\mathcal{A}$ chống lại $\Pi$ bên trong $\mathsf{CPA}$ trò chơi.
Các $\mathsf{CPA}$ trò chơi diễn ra như sau:
- $Gen(1^n)$ được chạy để lấy khóa $(pk_\alpha, sk_\alpha)$.
- đối thủ $\mathcal{A}$ được đưa ra $pk_\alpha$ cũng như truy cập tiên tri vào $Enc(pk_\alpha,\cdot)$. Tiếp theo, $\mathcal{A}$ chạy $Gen(1^n)$ để có được $(pk_\beta, sk_\beta)$.
- đối thủ $\mathcal{A}^2$ được đưa ra $pk:=(pk_\alpha,pk_\beta)$ cũng như truy cập tiên tri vào $Enc^2(pk,\cdot)$.
- $\mathcal{A}^2$ xuất ra một cặp thông báo riêng biệt $m_0:=(m_{0_\alpha},m_{0_\beta}), m_1:=(m_{1_\alpha},m_{1_\beta}) \in\mathcal{M}\times\mathcal{ M}$ với $m_{0_\beta} = m_{1_\beta}$ và $|m_0|=|m_1|$. Nói cách khác, các thông điệp $m_0$, $m_1$ là khác nhau, nhưng nửa thứ hai là như nhau.
- Sau khi nhận được $m_0$ và $m_1$ từ $\mathcal{A}^2$, đối thủ $\mathcal{A}$ chỉ chuyển tiếp các phần đầu tiên $m_{0_\alpha}$,$m_{1_\alpha}$ đến $\mathsf{CPA}$ trò chơi.
- Trò chơi chọn một bit ngẫu nhiên $b \in \{0, 1\}$, và bản mã thách thức $c_\alpha \gets Enc(pk_\alpha, m_{b_\alpha})$ được tính toán và trao cho $\mathcal{A}$. $\mathcal{A}$ tiếp tục có quyền truy cập vào $Enc(pk_\alpha,\cdot)$.
- Hiện nay $\mathcal{A}$ tính nửa sau của bản mã thử thách là $c_\beta \gets Enc(pk_\beta, m_{0_\beta}=m_{1_\beta})$. Lưu ý rằng $\mathcal{A}$ không cần biết chút thử thách $b$. Sau đó, $\mathcal{A}$ gửi bản mã thách thức \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*} đến $\mathcal{A}^2$. $\mathcal{A}^2$ tiếp tục có quyền truy cập vào $Enc^2(pk,\cdot)$.
- $\mathcal{A}^2$ trả về một chút đoán $b''$ đến $\mathcal{A}$.
- $\mathcal{A}$ đặt bit dự đoán của riêng mình $b':=b''$, và trả về $b'$ đến $\mathsf{CPA}$ trò chơi.
- Đầu ra của trò chơi được xác định là $1$ nếu $b'= b$, và $0$ nếu không thì.
Từ việc giảm nó sau đó, \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*}
Ở đây, bất đẳng thức cuối cùng xuất phát từ các giả định của chúng ta rằng $\mathcal{A}^2$ có thể thắng $\Pi^2$ bên trong $\mathsf{CPA}$ trò chơi với lợi thế không đáng kể.
Cuối cùng, điều này chứng minh tuyên bố ban đầu rằng $\Pi\text{ là $\mathsf{CPA}$-secure}\implies\Pi^2\text{ là $\mathsf{CPA}$-secure}$. $\;\hình vuông$
