# Cryptography 3

Xin chào mọi người đã quay lại với phần 3 trong chuỗi cryptography series. Tôi khuyên các bạn nên đọc [phần 2](https://dangduongminhnhat.github.io/posts/cryptography/p2/) trước khi bước vào bài này. Các bạn có thể tìm hiểu thêm các bài viết khác trong series này tại [đây](https://dangduongminhnhat.github.io/posts/cryptography/).

Trong bài viết này ta sẽ đi sâu vào an toàn ngữ nghĩa và tìm hiểu các ví dụ, hệ quả của khái niệm đó. Oke cùng tìm hiểu nào.

---

## **Tính toán các bit riêng lẻ của một thông điệp**

Nếu một hệ mã hóa là an toàn, thì không chỉ việc khôi phục toàn bộ thông điệp là điều khó khăn, mà việc tính toán bất kỳ thông tin một phần nào về thông điệp đó cũng phải khó khăn.

Ở đây, chúng ta sẽ không chứng minh một định lý tổng quát hoàn toàn, mà thay vào đó sẽ xét một ví dụ cụ thể. Giả sử $\mathcal{E} = (E, D)$ là một hệ mã được định nghĩa trên $(\mathcal{K}, \mathcal{M}, \mathcal{C})$, trong đó $\mathcal{M} = \{0, 1\}^L$. Với $m \in \mathcal{M}$, ta định nghĩa $\mathsf{parity}(m)$ là $1$ nếu số lượng bit $1$ trong $m$ là lẻ, và là $0$ nếu số lượng bit $1$ là chẵn. Nói cách khác, $\mathsf{parity}(m)$ là phép XOR của tất cả các bit trong $m$.

Chúng ta sẽ chỉ ra rằng nếu $\mathcal{E}$ là *an toàn ngữ nghĩa* (semantically secure), thì khi cho trước bản mã $c$ của một thông điệp ngẫu nhiên $m$, việc dự đoán $\mathsf{parity}(m)$ là điều khó. Vì $\mathsf{parity}(m)$ là một bit đơn lẻ, bất kỳ đối thủ nào cũng có thể dự đoán giá trị này đúng với xác suất $1/2$ bằng cách đoán ngẫu nhiên. Nhưng điều chúng ta muốn chỉ ra là không có đối thủ hiệu quả nào có thể làm tốt hơn đáng kể so với việc đoán ngẫu nhiên.

Với cách chứng minh tương tự trong bài [Cryptography 2](https://dangduongminhnhat.github.io/posts/cryptography/p2/), giả sử có một đối thủ hiệu quả $\mathcal{A}$ có thể dự đoán $\mathsf{parity}(m)$ với xác suất $1$. Điều này có nghĩa là với mọi thông điệp $m$, mọi khóa $k$, và mọi bản mã $c$ của $m$, khi chúng ta đưa $c$ cho $\mathcal{A}$, nó sẽ xuất ra giá trị $\mathsf{parity}(m)$. Khi đó, ta có thể dùng $\mathcal{A}$ để xây dựng một đối thủ $\mathtt{SS}$ (semantic security) là $\mathcal{B}$, hoạt động như sau: Đối thủ $\mathcal{B}$ chọn hai thông điệp $m_0$ và $m_1$ một cách tùy ý, nhưng sao cho $\mathsf{parity}(m_0) = 0$ và $\mathsf{parity}(m_1) = 1$. Sau đó, nó gửi hai thông điệp này đến "người thách đấu" trong trò chơi $\mathtt{SS}$ của nó, và nhận về một bản mã $c$, rồi chuyển $c$ cho $\mathcal{A}$. Khi nhận được $c$, đối thủ $\mathcal{A}$ xuất ra một bit $\hat{b}$, và $\mathcal{B}$ cũng xuất ra chính bit này làm đầu ra của nó. Dễ thấy rằng lợi thế $\mathtt{SS}$ của $\mathcal{B}$ là chính xác bằng $1$: khi "người thách đấu" mã hóa $m_0$, $\mathcal{B}$ luôn xuất ra $0$, và khi mã hóa $m_1$, $\mathcal{B}$ luôn xuất ra $1$. Điều này dẫn đến vô lý vì $\mathcal{B}$ là an toàn ngữ nghĩa. Do vậy nếu $\mathcal{E}$ là an toàn ngữ nghĩa, thì không có đối thủ hiệu quả nào có thể dự đoán $\mathsf{parity}$ với xác suất $1$. Tuy nhiên, ta còn có thể nói mạnh hơn: nếu $\mathcal{E}$ là an toàn ngữ nghĩa, thì không có đối thủ hiệu quả nào có thể dự đoán $\mathsf{parity}$ với xác suất lớn hơn đáng kể so với $1/2$. Để phát biểu điều này một cách chính xác, ta định nghĩa một trò chơi tấn công:

---

### **Trò chơi tấn công dự đoán parity**

Với một hệ mã $\mathcal{E} = (E, D)$ được định nghĩa trên $(\mathcal{K}, \mathcal{M}, \mathcal{C})$, và một đối thủ $\mathcal{A}$ được cho trước, trò chơi tấn công diễn ra như sau:

* Người thách đấu chọn $m \xleftarrow{R} \mathcal{M},\ k \xleftarrow{R} \mathcal{K},\ c \xleftarrow{R} E(k, m)$ và gửi $c$ cho đối thủ.
* Đối thủ xuất ra một bit $\hat{b} \in \{0, 1\}$.

Gọi $W$ là sự kiện $\hat{b} = \mathsf{parity}(m)$. Ta định nghĩa lợi thế dự đoán parity của $\mathcal{A}$ đối với $\mathcal{E}$ là:

$$
\mathtt{Parity}\text{adv}[\mathcal{A},\mathcal{E}] := \left| \Pr[W] - \frac{1}{2} \right|.
$$

---

### **Định nghĩa (dự đoán parity)**

Một hệ mã $\mathcal{E}$ được gọi là *an toàn đối với dự đoán parity* nếu với mọi đối thủ hiệu quả $\mathcal{A}$, giá trị $\mathtt{Parity}\text{adv}[\mathcal{A},\mathcal{E}]$ là không đáng kể (*negligible*).

---

**Định lý 1.** Cho $\mathcal{E} = (E, D)$ là một hệ mã được định nghĩa trên $(\mathcal{K}, \mathcal{M}, \mathcal{C})$ với $\mathcal{M} = \{0, 1\}^L$. Nếu $\mathcal{E}$ là an toàn ngữ nghĩa, thì $\mathcal{E}$ cũng an toàn đối với dự đoán parity.

**Chứng minh.** Tương tự như trong chứng minh của Định lý 1 trong bài [Cryptography 2](https://dangduongminhnhat.github.io/posts/cryptography/p2/), ta chứng minh bằng cách *security reduction*. Cụ thể, chúng ta sẽ chỉ ra rằng với mọi đối thủ dự đoán parity $\mathcal{A}$ tấn công $\mathcal{E}$ trong Trò chơi tấn công dự đoán parity, tồn tại một đối thủ $\mathtt{SS}$ $\mathcal{B}$ tấn công $\mathcal{E}$ trong Trò chơi tấn công trong bảo mật ngữ nghĩa ở bài [Cryptography 2](https://dangduongminhnhat.github.io/posts/cryptography/p2/), trong đó $\mathcal{B}$ chỉ đơn giản là một "vỏ bọc" xung quanh $\mathcal{A}$, sao cho:

$$
\mathtt{Parity}\text{adv}[\mathcal{A},\mathcal{E}] = \frac{1}{2} \cdot \mathtt{SS} \text{adv}[\mathcal{B},\mathcal{E}].
$$

Giả sử $\mathcal{A}$ là một đối thủ có thể dự đoán parity với xác suất $1/2 + \varepsilon$, tức là:

$$
\mathtt{Parity}\text{adv}[\mathcal{A},\mathcal{E}] = |\varepsilon|.
$$

Đây là cách ta xây dựng đối thủ $\mathtt{SS}$ $\mathcal{B}$:

* $\mathcal{B}$ tạo một thông điệp ngẫu nhiên $m_0$, và đặt $m_1 \leftarrow m_0 \oplus (0^{L-1} || 1)$, tức là $m_1$ giống với $m_0$, ngoại trừ bit cuối cùng bị đảo ngược. Như vậy, $m_0$ và $m_1$ có parity trái ngược nhau.

* $\mathcal{B}$ gửi cặp $(m_0, m_1)$ đến "người thách đấu" $\mathtt{SS}$ của nó, nhận bản mã $c$ từ người thách đấu, và chuyển tiếp $c$ cho $\mathcal{A}$.

* Khi $\mathcal{A}$ xuất ra một bit $\hat{b}$, $\mathcal{B}$ sẽ xuất ra $1$ nếu $\hat{b} = \mathsf{parity}(m_0)$, và xuất ra $0$ nếu khác.

Với $b = 0, 1$, gọi $p_b$ là xác suất mà $\mathcal{B}$ xuất ra $1$ nếu người thách đấu $\mathtt{SS}$ mã hóa $m_b$. Khi đó, theo định nghĩa:

$$
\mathtt{SS} \text{adv}[\mathcal{B},\mathcal{E}] = |p_1 - p_0|.
$$

Chúng ta khẳng định rằng $p_0 = 1/2 + \varepsilon$ và $p_1 = 1/2 - \varepsilon$. Lý do là vì bất kể $m_0$ hay $m_1$ được mã hóa, phân phối của $m_b$ vẫn là ngẫu nhiên trong $\mathcal{M}$, nên trong trường hợp $b = 0$, $\mathcal{A}$ sẽ xuất ra $\mathsf{parity}(m_0)$ với xác suất $1/2 + \varepsilon$, và khi $b = 1$, $\mathcal{A}$ sẽ xuất ra $\mathsf{parity}(m_1)$ với xác suất $1/2 + \varepsilon$, tức là xuất ra $\mathsf{parity}(m_0)$ với xác suất $1 - (1/2 + \varepsilon) = 1/2 - \varepsilon$.

Do đó:

$$
\mathtt{SS} \text{adv}[\mathcal{B},\mathcal{E}] = |p_1 - p_0| = 2|\varepsilon| = 2 \cdot \mathtt{Parity}\text{adv}[\mathcal{A},\mathcal{E}],
$$

và điều này chứng minh định lý. □

Như vậy, chúng ta đã chỉ ra rằng nếu một đối thủ có thể dự đoán hiệu quả parity của một thông điệp, thì đối thủ đó có thể dùng để phá vỡ tính an toàn ngữ nghĩa. Ngược lại, nếu một đối thủ có thể phá tính an toàn ngữ nghĩa, thì hắn cũng có thể dự đoán hiệu quả một số đặc tính (predicate) nào đó của thông điệp (điều này bạn đọc có thể tự chứng minh chiều ngược lại).

---

## **Hệ quả của tính an toàn ngữ nghĩa**

Tiếp theo, chúng ta sẽ xem xét các hệ quả của tính **an toàn ngữ nghĩa** trong bối cảnh một ví dụ cụ thể, đó là trò chơi cá cược điện tử. Các chi tiết cụ thể của ví dụ không quá quan trọng, nhưng ví dụ này minh họa cách mà giả định về tính an toàn ngữ nghĩa thường được sử dụng trong các ứng dụng thực tế.

Xét một phiên bản **cực kỳ đơn giản hóa** của trò chơi roulette, là trò chơi giữa nhà cái và người chơi. Người chơi đưa cho nhà cái $1$ đô la. Anh ta có thể đặt một trong hai loại cược:

* “cao hoặc thấp”, hoặc
* “chẵn hoặc lẻ”.

Sau khi đặt cược, nhà cái chọn một số ngẫu nhiên $r \in \{0, 1, \ldots, 36\}$. Người chơi thắng nếu $r \ne 0$, và nếu:

* anh ta cược “cao” và $r > 18$,
* anh ta cược “thấp” và $r \le 18$,
* anh ta cược “chẵn” và $r$ là số chẵn,
* anh ta cược “lẻ” và $r$ là số lẻ.

Nếu người chơi thắng, nhà cái trả cho anh ta 2 đô (tức là lời 1 đô), còn nếu thua thì nhà cái không trả gì cả (lỗ 1 đô). Rõ ràng, nhà cái có một lợi thế nhỏ nhưng không hề không đáng kể trong trò chơi này: xác suất để người chơi thắng là $\frac{18}{37} \approx 48.65\%$.

---

Giả sử giờ đây trò chơi này được chơi qua Internet. Và giả sử vì các lý do kỹ thuật, nhà cái **công bố bản mã hóa của $r$ trước khi người chơi đặt cược** (có thể là để cơ quan quản lý có thể giải mã được, vì họ chia sẻ khóa với nhà cái). Người chơi được tự do phân tích bản mã hóa này trước khi đặt cược — và dĩ nhiên, bằng việc làm như vậy, có thể người chơi sẽ tăng xác suất chiến thắng của mình.

Tuy nhiên, nếu hệ mã hóa được sử dụng đủ tốt, khả năng chiến thắng của người chơi **không nên tăng lên một cách đáng kể**. Hãy cùng chứng minh điều đó, với giả định rằng $r$ được mã hóa bằng một hệ mã **an toàn ngữ nghĩa** $\mathcal{E} = (E, D)$, được định nghĩa trên $(\mathcal{K}, \mathcal{M}, \mathcal{C})$, trong đó $\mathcal{M} = \{0, 1, \ldots, 36\}$ (chúng ta sẽ giả định rằng tất cả các thông điệp trong $\mathcal{M}$ có cùng độ dài). Từ đây, ta sẽ gọi người chơi là $\mathcal{A}$, để nhấn mạnh tính chất "đối thủ" của người chơi, và giả định rằng chiến lược của $\mathcal{A}$ được mô hình hóa bằng một thuật toán hiệu quả.

---

Trò chơi được minh họa trong **Hình 1** dưới đây. Ở đây, $bet$ biểu thị một trong các lựa chọn “cao”, “thấp”, “chẵn”, hoặc “lẻ”. Người chơi $\mathcal{A}$ gửi $bet$ đến nhà cái, nhà cái sẽ đánh giá hàm $W(r, bet)$, trả về $1$ nếu cược thắng với $r$, và $0$ nếu không.

Định nghĩa:

$$
\mathtt{IR}\text{adv}[\mathcal{A}] := \left| \Pr[W(r, bet) = 1] - \frac{18}{37} \right|.
$$

*Hình 1. Internet roulette*

Mục tiêu của chúng ta là chứng minh định lý sau:

**Định lý 2.** Nếu $\mathcal{E}$ là hệ mã an toàn ngữ nghĩa, thì với mọi đối thủ hiệu quả $\mathcal{A}$, giá trị $\mathtt{IR}\text{adv}[\mathcal{A}]$ là **không đáng kể** (negligible).

---

Tương tự như trong các chứng minh trước, chúng ta sẽ **chứng minh bằng cách reduction**. Cụ thể hơn, chúng ta sẽ chỉ ra rằng với mỗi người chơi $\mathcal{A}$, tồn tại một đối thủ $\mathtt{SS}$ là $\mathcal{B}$, trong đó $\mathcal{B}$ là một “vỏ bọc đơn giản” quanh $\mathcal{A}$, sao cho:

$$
\mathtt{IR}\text{adv}[\mathcal{A}] = \mathtt{SS}\text{adv}[\mathcal{B}, \mathcal{E}]. \tag{1}
$$

Do đó, nếu tồn tại một người chơi hiệu quả $\mathcal{A}$ có lợi thế đáng kể, thì ta sẽ có một đối thủ $\mathtt{SS}$ hiệu quả $\mathcal{B}$ phá được tính an toàn ngữ nghĩa của $\mathcal{E}$ — điều mà ta đang giả định là không thể. Dẫn đến không thể tồn tại $\mathcal{A}$ như vậy.

---

Để xây dựng và phân tích đối thủ $\mathcal{B}$, ta xét một phiên bản **lý tưởng hóa** của trò chơi roulette qua Internet, trong đó thay vì công bố mã hóa của giá trị thực $r$, nhà cái công bố bản mã của một **giá trị giả**, ví dụ như $0$. Logic của trò chơi lý tưởng hóa này được minh họa trong **Hình 2**. Tuy nhiên, lưu ý rằng trong trò chơi lý tưởng, nhà cái vẫn dùng giá trị thực $r$ để xác định kết quả của trò chơi.

*Hình 2. ideal Internet roulette*

Gọi $p_0$ là xác suất người chơi $\mathcal{A}$ thắng trong roulette Internet thật, và $p_1$ là xác suất $\mathcal{A}$ thắng trong phiên bản roulette lý tưởng.

---

Đối thủ $\mathcal{B}$ được thiết kế để tham gia vào **Trò chơi tấn công an toàn ngữ nghĩa**, sao cho nếu $\hat{b}$ là đầu ra của $\mathcal{B}$ trong trò chơi đó, thì ta có:

* Nếu $\mathcal{B}$ tham gia **Thí nghiệm 0**, thì $\Pr[\hat{b} = 1] = p_0$.
* Nếu $\mathcal{B}$ tham gia **Thí nghiệm 1**, thì $\Pr[\hat{b} = 1] = p_1$.

Logic của đối thủ $\mathcal{B}$ được minh họa trong **Hình 3**. Rõ ràng theo cách xây dựng, $\mathcal{B}$ thỏa mãn các tính chất trên, do đó:

$$
\mathtt{SS}\text{adv}[\mathcal{B}, \mathcal{E}] = |p_1 - p_0|. \tag{2}
$$

*Hình 3. The SS adversary B in Attack Game in semantic security*

---

Giờ hãy xét xác suất $p_1$ mà $\mathcal{A}$ thắng trong phiên bản roulette lý tưởng. Dù $\mathcal{A}$ có chiến lược thông minh đến đâu, xác suất thắng vẫn là $\frac{18}{37}$, bởi vì trong phiên bản lý tưởng, giá trị $bet$ được tính toán từ bản mã $c$ — mà $c$ lại là bản mã của số $0$, hoàn toàn **độc lập thống kê** với giá trị $r$. Điều này có nghĩa là roulette lý tưởng tương đương với roulette thật ngoài đời.

Do đó:

$$
\mathtt{IR}\text{adv}[\mathcal{A}] = \left|p_1 - \frac{18}{37} \right|= |p_1 - p_0|. \tag{3}
$$

Kết hợp $(2)$ và $(3)$, ta suy ra $(1)$. □

---

### **Kết luận**

Phương pháp mà chúng ta dùng để phân tích trò chơi roulette Internet là cách tiếp cận mà ta sẽ gặp đi gặp lại nhiều lần trong các phân tích bảo mật. Ý tưởng cốt lõi là **thay thế một thành phần trong hệ thống bằng phiên bản lý tưởng hóa** của thành phần đó, rồi phân tích hành vi của hệ thống lý tưởng mới.

Một bài học khác từ ví dụ trên là: khi suy luận về bảo mật của hệ thống, cái mà chúng ta xem là “đối thủ” **phụ thuộc vào mục tiêu phân tích**. Trong phân tích trên, chúng ta đã ráp nối một đối thủ mới $\mathcal{B}$ từ nhiều thành phần: một phần là đối thủ gốc $\mathcal{A}$, phần còn lại được trích xuất từ các thành phần khác của hệ thống (ví dụ, thuật toán của nhà cái). Điều này là **rất điển hình** trong các phân tích bảo mật.

Một cách trực quan, nếu ta tưởng tượng một sơ đồ hệ thống, thì tại các điểm khác nhau trong quá trình phân tích, ta sẽ vẽ “vòng tròn” bao quanh các thành phần khác nhau để xác định “ai là đối thủ” tại thời điểm đó.

---

## **Đoán bit: một cách diễn giải khác của tính an toàn ngữ nghĩa**

Ví dụ trên là một ví dụ điển hình cho cách người ta có thể sử dụng định nghĩa về **tính an toàn ngữ nghĩa** để phân tích các đặc tính bảo mật của một hệ thống lớn hơn có sử dụng một hệ mã an toàn ngữ nghĩa.

Tuy nhiên, có một cách diễn giải khác của tính an toàn ngữ nghĩa, thường **tiện lợi hơn** khi ta muốn chứng minh rằng một hệ mã cụ thể nào đó thỏa mãn định nghĩa này. Trong cách diễn giải thay thế này, chúng ta định nghĩa một **trò chơi tấn công mới**. Vai trò của đối thủ vẫn giống như trước, tuy nhiên thay vì có hai thí nghiệm khác nhau, giờ chỉ có **một thí nghiệm duy nhất**.

Trong phiên bản **đoán bit** của trò chơi tấn công, người thách đấu chọn ngẫu nhiên $b \in \{0, 1\}$ và thực thi Thí nghiệm $b$ của **Trò chơi tấn công An toàn ngữ nghĩa**. Mục tiêu của đối thủ là **đoán đúng bit $b$ với xác suất tốt hơn đáng kể so với 1/2**.

---

### **Trò chơi tấn công an toàn ngữ nghĩa (phiên bản đoán bit)**

Với một hệ mã $\mathcal{E} = (E, D)$ được định nghĩa trên $(\mathcal{K}, \mathcal{M}, \mathcal{C})$, và một đối thủ $\mathcal{A}$ được cho trước, trò chơi diễn ra như sau:

* Đối thủ chọn và gửi hai thông điệp $m_0, m_1 \in \mathcal{M}$ có cùng độ dài đến người thách đấu.
* Người thách đấu chọn ngẫu nhiên $b \xleftarrow{R} \{0, 1\}$, $k \xleftarrow{R} \mathcal{K}$, và tính $c \xleftarrow{R} E(k, m_b)$, rồi gửi $c$ cho đối thủ.
* Đối thủ xuất ra một bit $\hat{b} \in \{0, 1\}$.

Ta nói rằng đối thủ **thắng trò chơi** nếu $\hat{b} = b$. □

---

**Hình 4** minh họa Trò chơi tấn công trên. Lưu ý rằng trong trò chơi này, sự kiện “đối thủ thắng” được xác định với không gian xác suất do việc lựa chọn ngẫu nhiên $b$ và $k$, cũng như bất kỳ lựa chọn ngẫu nhiên nào của thuật toán mã hóa và của đối thủ.

*Hình 4. Trò chơi tấn công an toàn ngữ nghĩa (phiên bản đoán bit)*

---

Dĩ nhiên, bất kỳ đối thủ nào cũng có thể thắng trò chơi với xác suất $1/2$ bằng cách **bỏ qua $c$ hoàn toàn và đoán ngẫu nhiên** (ví dụ, luôn đoán $\hat{b} = 0$ hoặc luôn đoán $\hat{b} = 1$). Điều chúng ta quan tâm là đối thủ **có thể làm tốt hơn đoán ngẫu nhiên bao nhiêu**.

Nếu $W$ là sự kiện đối thủ thắng trò chơi đoán bit, thì lượng ta quan tâm là $|\Pr[W] - 1/2|$, ký hiệu là $\mathtt{SS}\text{adv}^*[\mathcal{A}, \mathcal{E}]$. Khi đó ta có:

**Định lý 3.** Với mọi hệ mã $\mathcal{E}$ và mọi đối thủ $\mathcal{A}$, ta có:

$$
\mathtt{SS}\text{adv}[\mathcal{A}, \mathcal{E}] = 2 \cdot \mathtt{SS}\text{adv}^*[\mathcal{A}, \mathcal{E}]. \tag{4}
$$

**Chứng minh.** Đây là một phép tính đơn giản. Gọi $p_0$ là xác suất đối thủ xuất ra $1$ trong **Thí nghiệm 0** của Trò chơi tấn công an toàn ngữ nghĩa gốc, và $p_1$ là xác suất đối thủ xuất ra $1$ trong **Thí nghiệm 1**.

Giờ xét Trò chơi tấn công an toàn ngữ nghĩa phiên bản đoán bit. Từ đây trở đi, tất cả các sự kiện và xác suất đều xét trong trò chơi này.

Nếu ta **điều kiện hóa** theo sự kiện $b = 0$, thì trong không gian xác suất điều kiện này, tất cả các lựa chọn ngẫu nhiên khác (của người thách đấu và đối thủ) được phân phối **giống hệt** như trong Thí nghiệm 0. Do đó, nếu $\hat{b}$ là đầu ra của đối thủ trong Trò chơi phiên bản đoán bit, ta có:

$$
\Pr[\hat{b} = 1 \mid b = 0] = p_0.
$$

Tương tự:

$$
\Pr[\hat{b} = 1 \mid b = 1] = p_1.
$$

Vậy:

$$
\begin{aligned}
\Pr[\hat{b} = b] &= \Pr[\hat{b} = b \land b = 0] + \Pr[\hat{b} = b \land b = 1] \\
&= \Pr[\hat{b} = b \mid b = 0] \cdot \Pr[b = 0] + \Pr[\hat{b} = b \mid b = 1] \cdot \Pr[b = 1] \\
&= \Pr[\hat{b} = 0 \mid b = 0] \cdot \frac{1}{2} + \Pr[\hat{b} = 1 \mid b = 1] \cdot \frac{1}{2} \\
&= \frac{1}{2} \left( 1 - \Pr[\hat{b} = 1 \mid b = 0] + \Pr[\hat{b} = 1 \mid b = 1] \right) \\
&= \frac{1}{2} (1 - p_0 + p_1).
\end{aligned}
$$

Do đó:

$$
\mathtt{SS}\text{adv}^*[\mathcal{A}, \mathcal{E}] = \left| \Pr[\hat{b} = b] - \frac{1}{2} \right| = \frac{1}{2} |p_1 - p_0| = \frac{1}{2} \cdot \mathtt{SS}\text{adv}[\mathcal{A}, \mathcal{E}].
$$

Điều này chứng minh định lý. □

---

Cũng như ta gọi $\mathtt{SS}\text{adv}[\mathcal{A}, \mathcal{E}]$ là “**lợi thế an toàn ngữ nghĩa**” của $\mathcal{A}$, ta sẽ gọi $\mathtt{SS}\text{adv}^*[\mathcal{A}, \mathcal{E}]$ là “**lợi thế đoán bit an toàn ngữ nghĩa**” của $\mathcal{A}$.

---

### **Một khái quát hóa**

Thật ra, tình huống trên là **rất tổng quát**. Dù chúng ta chưa cần đến trong lúc này, nhưng để tham khảo cho tương lai, ta sẽ mô tả cách khái quát tình huống trên.

Sẽ có nhiều tình huống mà một thuộc tính bảo mật nào đó — gọi là “$\mathtt{X}$” — đối với một hệ mật mã nào đó — gọi là “$\mathcal{S}$” — có thể được định nghĩa thông qua một trò chơi tấn công gồm **hai thí nghiệm**, Thí nghiệm 0 và Thí nghiệm 1. Trong đó **giao thức của đối thủ $\mathcal{A}$ là giống nhau** ở cả hai thí nghiệm, nhưng giao thức của người thách đấu thì khác nhau.

Với $b = 0, 1$, ta định nghĩa $W_b$ là sự kiện đối thủ xuất ra 1 trong Thí nghiệm $b$, và định nghĩa:

$$
\mathtt{X}\text{adv}[\mathcal{A}, \mathcal{S}] := \left| \Pr[W_0] - \Pr[W_1] \right|
$$

là **lợi thế X** của đối thủ $A$ đối với hệ thống $S$.

Tương tự như trên, ta có thể định nghĩa một phiên bản “**đoán bit**” của trò chơi tấn công, trong đó người thách đấu chọn ngẫu nhiên $b \in {0, 1}$ và thực hiện Thí nghiệm $b$. Nếu $W$ là sự kiện đầu ra của đối thủ bằng với $b$, thì ta định nghĩa:

$$
\mathtt{X}\text{adv}^*[\mathcal{A}, \mathcal{S}] := \left| \Pr[W] - \frac{1}{2} \right|
$$

là **lợi thế đoán bit X** của $\mathcal{A}$.

Và với phép tính giống hệt trong chứng minh Định lý 3, ta thu được:

$$
\mathtt{X}\text{adv}[\mathcal{A}, \mathcal{S}] = 2 \cdot \mathtt{X}\text{adv}^*[\mathcal{A}, \mathcal{S}]. \tag{5}
$$