Mật mã dưới góc nhìn độ phức tạp tính toán

Phan Dương Hiệu | 20/09/2009 |

Bài này thảo luận mối liên hệ mất thiết giữa lý thuyết mật mã và lý thuyết độ phức tạp tính toán.

I. Khởi động: Bài toán quyết định và bài toán tìm kiếm (Decision versus Search)

Trong thực tế, khi có một bài toán, ta thường quan tâm tới việc tìm ra lời giải cho bài toán đó hơn là xem xét liệu bài toán đó có tồn tại lời giải hay không. Tuy nhiên, trong lý thuyết độ phức tạp tính toán, ta lại toàn bắt gặp các bài toán quyết định (chẳng hạn như với $\mathsf{SAT}$ là xem 1 công thức có thỏa được hay không) mà ít chú ý đến việc tìm kiếm lời giải (tìm một phép gán giá trị cho các biến để công thức là thỏa được). Các lớp phổ biến $\mathbf{P, NP, EXP}$ ,… đều là các lớp các bài toán quyết định. Điều đó hẳn làm chúng ta băn khoăn tự hỏi, lý do nào mà ta thường ít nói tới các bài toán tìm kiếm? Một số lý do cơ bản (tất nhiên có thể có nhiều lý do khác) là như sau :
- Nếu lý thuyết thuật toán là đưa ra cận trên (upper bound) của sự phức tạp để giải quyết một bài toán (thực vậy, khi ta có thiết kế một thuật toán để giải một bài toán, thì đồng thời độ phức tạp của thuật toán đó cho ta một cận trên để giải bài toán) thì lý thuyết độ phức tạp nghiên cứu chủ yếu cận dưới (lower bound) hay độ khó tối thiểu để giải một bài toán. Bài toán quyết định hiển nhiên không thể khó hơn bài toán tìm kiếm nên nếu ta chứng minh được bài toán quyết định là khó thì nghiễm nhiên bài toán tìm kiếm cũng khó theo. Do vậy, dù gì cũng nên nghiên cứu độ khó của bài toán quyết định trước.
- Trong nhiều bài toán ta có sự “tương đương” giữa bài toán quyết định và bài toán tìm kiếm nên chỉ cần nghiên cứu bài toán quyết định. Thực tế, tất cả các bài toán trong lớp NP-đầy đủ đều có tính chất này. Kỹ thuật qui dẫn một bài toán tìm kiếm về bài toán quyết định thường là dùng cách phương pháp tìm kiếm nhị phân. Chẳng hạn đối với $\mathsf{SAT}$ , giả sử ta giải được bài toán quyết định xác định một công thức thỏa được hay không, khi đó ta cũng có thể tìm một phép gán giá trị các biến để công thức thỏa được như sau: cho biến đầu tiên giá trị đúng ; nếu công thức giản lược là thỏa được thì ta tiếp tục tìm phép gán cho biến thứ hai, nếu không ta cho biến đầu giá trị sai và tiếp tục với công thức giản lược cho trường hợp này; chỉ sau n bước như vậy (n = số biến) là ta có được phép gán giá trị cho tất cả các biến.
- Ta tạm gọi (sẽ định nghĩa chính xác dưới đây) lớp bài toán tìm kiếm tương ứng với các lớp bài toán quyết định $\mathbf{P, NP}$ là $\mathbf{FP, FNP}$ (Function $\mathbf{P}$ , Function $\mathbf{NP}$ ). Khi đó ta có thể chứng minh được $\mathbf{P}=\mathbf{NP}$ khi và chỉ khi $\mathbf{FP}=\mathbf{FNP}$ . Như vậy tình trạng đối với các bài toán tìm kiếm cũng tương tự như các bài toán quyết định: tìm kiếm lời giải cho một bài toán $\mathbf{NP}$ thực hiện được trong thời gia đa thức khi và chỉ khi bài toán quyết định cũng thực hiện được trong thời gian đa thức. Do vậy nghiên cứu vấn đề nổi cộm “ $\mathbf{P}$ vs. $\mathbf{NP}$ ” là bao quát được vấn đề chung.

Tuy vậy, những lý do trên chưa đủ thuyết phục để ta hoàn toàn quên đi các bài toán tìm kiếm. Vẫn có nhiều bài toán tìm kiếm có vẻ thực sự khó hơn là quyết định (chẳng hạn Bellare và Goldwasser chứng minh rằng, dưới giả thiết khá hợp lý ( $\mathbf{EE} \neq \mathbf{NEE}$ ), có những ngôn ngữ $\mathbf{NP}$ mà ở đó bài toán tìm kiếm không thể qui dẫn về bài toán quyết định). Một số ví dụ khác liên quan đến mật mã nơi chủ yếu dựa trên các bài toán không phải NP-đầy đủ (phân tích thành thừa số nguyên tố chẳng hạn) và do vậy, bài toán tìm kiếm có thể rất khác bài toán quyết định.

Trong bài này, chúng ta sẽ xem xét lớp các bài toán tìm kiếm $\mathbf{FP, FNP}$ và sự liên quan tới mật mã. Sự liên hệ giữa các lớp bài toán $\mathbf{FP, FNP}$ và $\mathbf{P, NP}$ cuối cùng giúp chúng ta có một liên hệ giữa sự tồn tại của mật mã với câu hỏi trọng tâm của lý thuyết độ phức tạp – “ $\mathbf{P} vs. \mathbf{NP}$ “.

I.1 Lớp bài toán $\mathbf{FNP, FP}$

Một cách nôm na, cho một ngôn ngữ $L$ ( $\mathsf{SAT}$ chẳng hạn) và một đầu vào $x$ (một công thức lô gíc chẳng hạn), bài toán quyết định là xác định xem liệu $x$ có thuộc $L$ (công thức lô gíc đầu vào liệu có thỏa được) còn bài toán tìm kiếm là bài toán chỉ ra, khi $x$ thuộc $L$ (công thức đã cho là thỏa được), một lời giải chứng tỏ $x$ thuộc $L$ (một phép gán giá trị cho các biến để công thức đã cho là thỏa được).

Mọi việc tưởng chừng đơn giản trừ việc ta chưa nói cho chính xác thế nào là một lời giải để chứng tỏ $x$ thuộc $L$ . Một bài toán có thể có nhiều cách chứng minh chứ không phải chỉ có một. Và như vậy, để định nghĩa chính xác bài toán tìm kiếm, ta cần đưa ra quan hệ giữa đầu vào và lời giải cho nó một cách thích hợp.

Ta hãy xem xét một cách viết lại định nghĩa của ngôn ngữ $\mathbf{NP}$ dựa trên các quan hệ hai ngôi.

Quan hệ NP-relation
Một quan hệ hai ngôi $R \in \Sigma^* \times \Sigma^*$ (với $\Sigma^*$ là bảng ký hiệu dùng trong một ngôn ngữ) được gọi là NP-relation nếu nó thỏa mãn các điều kiện sau:
- $R$ có thể xác định được trong thời gian đa thức. Tức là, với các đầu vào $x, y \in \Sigma^*$ , ta có thể xác định liệu $x$ có quan hệ $R$ với $y$ (ký hiệu $R(x,y)$ ) hay không trong thời gian đa thức tính trên $|x|,|y|$ (độ dài của $x,y$ ).
- $R$ có tính chất cân bằng đa thức (polynomially balanced), tức là tồn tại một đa thức $p(.)$ để, nếu $R(x,y)$ thì $|y| \leq p(|x|$ ). Đó là một yêu cầu tự nhiên : lời giải không thể quá dài so với đầu vào (nếu không thì riêng việc viết ra lời giải đã không thể thực hiện trong thời gian đa thức).

(Ta hãy cứ hình dung, cho $x$ là một bài toán, $R$ là định nghĩa của “lời giải”, thì $y$ là lời giải của $x$ nếu $R(x,y)$ ).

Nhìn lại (và chép lại) định nghĩa về lớp $\mathbf{NP}$ trong bài PCP số 1 của anh Hưng: một ngôn ngữ $L$ thuộc $\mathbf{NP}$ nếu tồn tại một poly-time algorithm verifier $V$ :

Verifier nhận inputs $x, \pi$ , và trả lời YES/NO. Nhiệm vụ là xác định xem $x$ là YES-instance hay NO-instance của $L$ .
Nếu $x$ là YES-instance thì tồn tại “chứng minh” $\pi$ sao cho $V(x, \pi) =$ YES.
Nếu $x$ là NO-instance thì với bất kỳ “chứng minh” $\pi$ nào ta cũng có $V(x,\pi) =$ NO.

Một verifier $V$ như vậy thực chất chính là một NP-relation và ngôn ngữ $L = \{x \in \Sigma^*: \exists y \in \Sigma^* V(x,y)\}$ .
Ngược lại, với mỗi NP-relation $R$ , ta cũng có thể định nghĩa một ngôn ngữ $L_R = \{x \in \Sigma^*: \exists y \in \Sigma^* R(x,y)\}$ và ngôn ngữ $L_R$ hiển nhiên là thuộc $\mathbf{NP}$ (bằng cách đặt $V$ chính là $R$ ).

Như vậy thực chất $\mathbf{NP}$ là tập hợp tất cả các ngôn ngữ $L_R = \{x \in \Sigma^*: \exists y \in \Sigma^* R(x,y)\}$ với $R$ là NP-relation.

Điểm hay là quan hệ $R$ giúp ta có thể định nghĩa được bài toán tìm kiếm một cách tường minh.

Định nghĩa bài toán tìm kiếm

Với quan hệ $R$ , ta có thể định nghĩa một bài toán tìm kiếm $\Pi_R$ như sau:
- Đầu vào: Cho một $x \in \Sigma^*$
- Trả lời: Tìm một $y \in \Sigma^*$ sao cho $R(x,y)$ nếu tồn tại một $y$ như vậy, hoặc trả lời “KHONG” nếu không tồn tại $y$ .

Như vậy, ta đã định nghĩa được bài toán tìm kiếm $\Pi_R$ tương ứng cho bài toán quyết định $L_R$ : nếu $x \notin L_R$ thì câu trả lời là KHONG, còn nếu $x \in L_R$ thì phải chỉ ra lời giải $y$ chứng tỏ điều đó ( $y$ thỏa mãn $R(x,y)$ ).

Định nghĩa các lớp $\mathbf{FNP, FP}$
- $\mathbf{FNP}$ là tập hợp tất cả các bài toán $\Pi_R$ với $R$ là NP-relation.
- $\mathbf{FP}$ là tập con của $\mathbf{FNP}$ bao gồm các bài toán $\Pi_R$ ở đó câu “Trả lời” (trong định nghĩa bài toán tìm kiếm trên) được thực hiện trong thời gian đa thức.

Để ý rằng, cho trước một ngôn ngữ $L \in \mathbf{NP}$ , ta chưa có ngay bài toán tìm kiếm tương ứng với nó. Ta phải định nghĩa thế nào là một lời giải chứng tỏ $x \in L$ , đó chính là việc định nghĩa quan hệ $R$ thỏa mãn $L_R = L$ . Chỉ khi đã định nghĩa được $R$ thì tương ứng với nó ta mới định nghĩa được bài toán tìm kiếm $\Pi_R$ . $\Pi_R$ chính là một bài toán tìm kiếm tương ứng với bài toán quyết định $L_R=L$ .

Do vậy, với một bài toán quyết định, có thể cho tương ứng nhiều bài toán tìm kiếm. Chẳng hạn, nếu ta tìm được hai quan hệ $R_1$ và $R_2$ sao cho $L_{R_1} = L_{R_2} = L$ thì tương ứng với $L$ có hai bài toán tìm kiếm $\Pi_{R_1} = \Pi_{R_2}$ . Điều này phù hợp với thực tế, một phát biểu có thể đúng hoặc sai, nhưng chứng minh nó là đúng hay sai thì có thể có nhiều cách khác nhau.

Có những bài toán mà tương ứng với nó có hai bài toán tìm kiếm mà một thì có thể dễ, mà một thì lại có vẻ khó. Ta sẽ xem xét một ví dụ thú vị liên quan đến bài toán phân tích thành thừa số nguyên tố. Nhưng trước hết ta hãy chứng minh định lý quan trọng sau đây:

Định lý về sự liên quan giữa lớp các bài toán quyết định và lớp các bài toán tìm kiếm

$\mathbf{P}=\mathbf{NP}$ khi và chỉ khi $\mathbf{FP}=\mathbf{FNP}$

Chứng minh rất đơn giản:
- Đầu tiên, nếu $\mathbf{FP}=\mathbf{FNP}$ thì $\mathbf{P}=\mathbf{NP}$ . Điều này hiển nhiên, tìm được lời giải nhanh nếu có (trong thời gian đa thức) thì cũng sẽ quyết định được nhanh là có lời giải hay không.
- Ngược lại, nếu $\mathbf{P}=\mathbf{NP}$ thì $\mathbf{FP}=\mathbf{FNP}$ . Ý tưởng là sử dụng tìm kiếm nhị phân.
Cho một quan hệ NP-relation bất kỳ $R$ , ta cần chứng minh $\Pi_R \in \mathbf{FP}$ . Điều đó có nghĩa là với mọi $x$ , cần tìm trong thời gian đa thức $y$ để $R(x,y)$ (nếu có $y$ như vậy), hoặc trả lời KHONG nếu không có $y$ nào thỏa mãn $R(x,y)$ .
Do $L_R \in \mathbf{NP}=\mathbf{P}$ , nên việc quyết định có tồn tại $y$ hay không được thực hiện trong thời gian đa thức. Nếu không có $y$ thì trả lời KHONG là xong.
Trường hợp tồn tại $y$ , ta làm sao tìm được $y$ đây?
Với mỗi $z\in \Sigma^*$ , định nghĩa một quan hệ $R_z(x,y) := (R(x,y) \land (y\leq z))$ . (quan hệ thứ tự tính theo quan hệ thứ tự từ trên bảng chữ cái $\Sigma$ )
Do $R$ là NP-relation, $R_z$ cũng là NP-relation. Do vậy $L_{R_z} \in \mathbf{NP}$ và do đó việc bài toán quyết định $L_{R_z}$ thực hiện được trong thời gian đa thức.

Nếu lấy $z$ là điểm giữa $\emptyset$ và $U$ – xâu lớn nhất có độ dài $p(|x|)$ (với $p()$ là đa thức chặn trên độ dài của $y$ theo độ dài của $x$ . Hiển nhiên ta có $y \leq U$ ). Nếu $x \in L_{R_z}$ thì tồn tại lời giải $y$ giữa $\emptyset$ và $z$ , ngược lại, nếu $x \notin L_{R_z}$ thì tồn tại lời giải $y$ giữa $z$ và $U$ .
Như vậy ta giới hạn miền tìm kiếm $y$ xuống còn một nửa. Tiếp tục một cách tương tự ta sẽ tìm được chính xác $y$ trong thời gian đa thức.

I.2 Có những bài toán quyết định dễ, còn tìm kiếm lại khó
Phía trên ta nhắc đến kêt quả của Bellare và Goldwasser chứng minh rằng, dưới một giả thiết khá hợp lý ( $\mathbf{EE} \neq \mathbf{NEE}$ ), có những ngôn ngữ $\mathbf{NP}$ mà ở đó bài toán tìm kiếm không thể qui dẫn bài toán quyết định. Ở đây ta xét một ví dụ đơn giản hơn và kết quả tuy không mạnh bằng nhưng khá lý thú.
Ta xét một số $n$ và một dãy cặp $(p_1,\alpha_1), (p_2,\alpha_2), \cdots, (p_k,\alpha_k)$ với $p_i$ là các số nguyên tố và $\alpha_i$ là các số tự nhiên.
Ta định nghĩa một quan hệ $R(n, ((p_1,\alpha_1), (p_2,\alpha_2), \cdots, (p_k,\alpha_k))) := (n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k})$ .
Điều đó có nghĩa là $n$ và $(p_1,\alpha_1), (p_2,\alpha_2), \cdots, (p_k,\alpha_k)$ có quan hệ $R$ nếu phân tích thành thừa số nguyên tố của $n$ chính là $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ .

Với quan hệ $R$ định nghĩa như vậy, ngôn ngữ $L_R$ chính là toàn bộ các số tự nhiên vì mọi số tự nhiên đều có tương ứng một cách phân tích thành thừa số nguyên tố. Bài toán quyết định $L_R$ do đó là tầm thường.
Trong khi đó, bài toán tìm kiếm $\Pi_R$ chính là việc cho số $n$ , phân tích $n$ ra thừa số nguyên tố. Bài toán này được tin là khó.

I.3 Sự khéo léo trong việc định nghĩa bài toán tìm kiếm cho các bài toán quyết định

Bây giờ ta hãy xem một ví dụ cho thấy, cùng một bài toán quyết định, có thể có hai bài toán tìm kiếm khá xa nhau. Hơn nhau là việc định nghĩa bài toán tìm kiếm sao cho hợp lý để có thể giải nó một cách hiệu quả nhất.

Xét ngôn ngữ COMPOSITE gồm các số tự nhiên $n$ là hợp số.

Bài toán tìm kiếm 1 tương ứng với COMPOSITE:
Ta định nghĩa một quan hệ giữa một số tự nhiên $n$ và một chứng minh $a$ (một số tự nhiên) như sau: $R(n,a) := ( (1<a<n) \land (a|n))$ .
Đây là cách định nghĩa tự nhiên nhất để chứng minh một số $n$ là hợp số: đưa ra một ước số không tầm thường của nó.
Bài toán tìm kiếm $\Pi_R$ tương ứng là cho $n$ , nếu $n$ là hợp số thì tìm một ước số không tầm thường của nó.
Rõ ràng bài toán tìm kiếm này tương đương bài toán phân tích một số thành thừa số nguyên tố, do vậy nó được tin là khó.

Bài toán tìm kiếm 2 tương ứng với COMPOSITE:
Ta định nghĩa một quan hệ giữa một số tự nhiên $n$ và một chứng minh $a$ (một số tự nhiên) như sau: $R(n,a):= ((\frac{a}{n}) \neq a^ {\frac{n-1}{2}})$

với $(\frac{a}{n})$ là ký hiệu Jacobi (một mở rộng tự nhiên của ký hiệu Legendre cho trường hợp các số tự nhiên thay vì chỉ cho các số nguyên tố).

Ta đã biết:

Nếu $n$ là số nguyên tố thì, với mọi $a$ ta đều có $(\frac{a}{n}) = a^ {\frac{n-1}{2}}$ , tức là $\lnot R(n,a)$ .
Ngược lại, nếu $n$ là hợp số thì, ít nhất một nửa các số $a$ nguyên tố cùng nhau với $n$ thỏa mãn $R(n,a)$ . (Chứng minh điều này không khó, bởi tập các $a$ để $\lnot R(n,a)$ tạo thành 1 nhóm, và ta có thể chứng minh khi $n$ là hợp số thì tồn tại ít nhất một phần tử $a$ để $R(n,a)$ . Điều đó dẫn đến tập các $a$ để $\lnot R(n,a)$ tạo thành một nhóm con thực sự của $(\mathbb{Z}/n\mathbb{Z})^*$ , và do đó số phần tử của nó nhiều nhất bằng nửa số phần tử của $(\mathbb{Z}/n\mathbb{Z})^*)$ .

Từ đó ta thấy ngôn ngữ $L_R = \{n : \exists a, R(n,a) \}$ chính là COMPOSITE.
Tuy vậy, bài toán tìm kiếm $\Pi_R$ ở đây khá là dễ dàng.
Thực vậy, nếu $n$ là hợp số, ta chỉ cần lấy ngẫu nhiên một $a$ nguyên tố cùng nhau với $n$ là đã có khả năng chí ít là 50% để có $R(n,a)$ .

Vấn đề còn lại là tính $R(n,a)$ có dễ không? Tính $a^ {\frac{n-1}{2}}$ là dễ nhưng còn ký hiệu Jacobi $(\frac{a}{n})$ ? Định nghĩa của $(\frac{a}{n})$ dựa trên việc phân tích thành thừa số nguyên tố của $n$ . Nhưng nếu mà ta biết phân tích thành thừa số nguyên tố của $n$ thì đã xác định được $n$ là hợp số hay không rồi! Rất may, ta có thể tính $(\frac{a}{n})$ dựa trên luật tương hỗ toàn phương một cách rất nhanh chóng mà không cần thông qua phân tích thành thừa số nguyên tố của $n$ .

Các bạn có thể đọc thêm về luật tương hỗ toàn phương (bài 1, bài 2) trên blog của hòa thượng Thích Học Toán. Luật “tương hỗ toàn phương” như hòa thượng giải thích dành cho số nguyên tố, ở đây ta phải dùng một luật tương tự cho các số tự nhiên tổng quat. Bình loạn một chút về hai luật tương hỗ:

Luật “tương hỗ toàn phương” nguyên thủy dành cho số nguyên tố thật đẹp, nó có ý nghĩa thế nào hòa thượng đã giải thích. Chỉ muốn nói thêm là trong suốt một thời gian dài, người ta đã tưởng thể loại số nguyên tố là rất kỳ bí và có tính độc lập nhau, tức là 2 kẻ khác nhau trong bọn chúng là chả có quan hệ dây mơ rễ má chi cả. Nhưng luật tương hỗ cho thấy không hẳn là thế, nó cho ta quan hệ họ hàng giữa hai số nguyên tố bất kỳ: nếu anh là thặng dư bậc hai của tôi thì tôi cũng xác định được ngay mình có phải là thặng dư bậc hai trong thế giới của anh hay không!
Luật “tương hỗ toàn phương” áp dụng cho số không nguyên tố dĩ nhiên làm mất cái vẻ đẹp nguyên tố trên. Ấy vậy mà nó lại đem đến một ứng dụng bất ngờ trong việc tìm ra các … số nguyên tố lớn phục vụ các ứng dụng mật mã trong thực tế nhốn nháo ngày nay. Nó giúp ta có một thuật toán kiểm tra xem một số $n$ bất kỳ có là nguyên tố hay không. Thuật toán này thực chất ý tưởng đã được mô tả phía trên : lấy $a$ bất kỳ nguyên tố cùng nhau với $n$ , nếu $R(n,a)$ thì $n$ chắc chắn là hợp số, nếu không thì ít nhất 50% khả năng $n$ là số nguyên tố. Thực hiện thao tác này 100 lần mà đều không có $a$ nào thỏa mãn $R(n,a)$ thì có nghĩa $n$ là số nguyên tố với sai số chỉ là $\frac{1}{2^{100}}$ ! Gần đây đã có một kết quả lý thuyết đẹp đưa ra thuật toán đơn định để kiểm tra tính nguyên tố trong thời gian đa thức (thú vị là chứng minh khá sơ cấp) nhưng trong thực tế thì người ta vẫn dùng các thuật toán xác suất vì nó hiệu quả hơn rất nhiều.

II. Điều kiện cần cho sự tồn tại của mã hóa, dưới cách nhìn của lý thuyết độ phức tạp tính toán

Ta sẽ nhìn mật mã bằng con mắt của lý thuyết độ phức tạp tính toán và giới hạn việc bàn luận cho mã hóa (Encryption) – mục tiêu trọng tâm của mật mã.

Mục đích của mã hóa là gì nhỉ? Thật đơn giản, tôi có thể mã hóa một bản rõ dễ dàng để: nếu anh có khóa thích hợp thì anh có thể mở được nó và kẻ địch (không có khoá) thì không thể giải được mã.

Tạm gác chuyện chiếc chìa khoá thần kỳ trong mã hóa (ừ, thế đấy, mã hóa phải có khóa, nhưng ta cứ tạm bỏ qua nó đã) và bỏ qua luôn việc anh có giải được mã hay không, ta có thể rút gọn câu trên: tôi có thể mã hóa một bản rõ dễ dàng để kẻ địch (tay không – không có ngoại lực trợ giúp) không thể giải được mã.

Ta giản lược yêu cầu như trên nhằm đưa ra một điều kiện cần để mã hoá tồn tại. Đó là phải có các “hàm xuôi dễ ngược khó”, tức là các hàm $f$ để, với một đầu vào $m$ (có thể coi là bản mã – message), thì tính $c=f(m)$ (có thể coi là bản mã – ciphertext) là dễ, nhưng cho $c$ thì việc tính ngược một $m$ (có thể có nhiều $m$ ) để $f(m) = c$ thì là khó.

Vậy câu hỏi đặt ra là: Các hàm xuôi dễ ngược khó có liên quan gì tới bài toán trọng tâm “P vs. NP” của lý thuyết độ phức tạp?

Ta hãy giả thiết rằng là tồn tại các hàm $f$ xuôi dễ ngược khó.
Theo định nghĩa “dễ, khó” trong độ phức tạp thì $f$ tính được trong thời gian đa thức và việc tính $f^{-1}$ là không thực hiện được trong thời gian đa thức.

Khi đó ta định nghĩa một quan hệ $R(c,m)$ như sau: $R(c,m) := (c=f(m))$ .
Dễ thấy $R(c,m)$ là một NP-relation.
Như vậy, bài toán tìm kiếm $\Pi_R$ thuộc lớp $\mathbf{FNP}$ . Mà bài toán $\Pi_R$ chính là việc tính ngược hàm $f$ .

Theo giả thiết, việc tính $f^{-1}$ là không thực hiện được trong thời gian đa thức. Từ đó ta có $\Pi_R$ không thể thuộc $\mathbf{FP}$ , và suy ra $\mathbf{FP} \neq \mathbf{FNP}$ . Theo định lý phía trên, nó tương đương $\mathbf{P} \neq \mathbf{NP}$ .

Như vậy ta có kết luận đầu tiên:

Yêu cầu tối thiểu không thể ít hơn để ngành lý thuyết mã hóa tồn tại, đó là “ $\mathbf{P} \neq \mathbf{NP}$ “. Nói cách khác, nếu ta chứng minh được “ $\mathbf{P} = \mathbf{NP}$ ” thì ngành lý thuyết mã hóa sụp đổ!

Kết luận này có nghĩa ta không thể hy vọng vào việc xây dựng mã hóa dựa trên các lớp có độ phức tạp cao hơn như $\mathbf{EXP, NEXP}$ để phòng trường hợp $\mathbf{P} = \mathbf{NP}$ . Bản chất sự tồn tại của mã hóa bắt buộc phải dựa trên giả thiết $\mathbf{P} \neq \mathbf{NP}$ . Tất nhiên sự sụp đổ chỉ là trong lý thuyết độ phức tạp, còn trong thực tế thì dù phá mã có thể trong thời gian đã thức nhưng bậc đa thức là 100 hay 1000 thì các hệ mã vẫn còn vững lắm

III. Một cái nhìn thoáng qua về điều kiện đủ cho sự tồn tại của mã hóa

Ta đã thấy lý thuyết mã hóa (đặt trong lý thuyết độ phức tạp) chỉ có nghĩa khi $\mathbf{P} \neq \mathbf{NP}$ . Câu hỏi ngược lại là liệu nếu $\mathbf{P} \neq \mathbf{NP}$ thì ta có xây dựng được các sơ đồ mật mã hay không? Câu trả lời là … không biết (hay nói cách khác, đó là một câu hỏi mở). Điều đó tuy vậy không làm ta nhụt chí đi tìm kiểm các điều kiện đủ để xây dựng mã hóa.

Trước tiên ta thấy hàm “xuôi dễ ngược khó” chủ yếu nói về trường hợp tệ nhất (worst-case), nó chỉ yêu cầu tồn tại những $c$ để ta không tính ngược được $f^{-1}(c)$ . Điều đó có thể hiểu như, có những bản mã mà ta không giải được. Tuy nhiên điều này không phản ánh được yêu cầu của mã hoá, nơi ta cần kẻ địch không thể giải mã được một bản mã bất kỳ. Với yêu cầu tối thiểu này của mã hoá, ta có điều kiện cần là sự tồn tại của các hàm một chiều (one-way function), đó là các hàm thoả mãn: cho $c = f(m)$ với một $m$ được lấy ngẫu nhiên, khó có thể tính ngược được $f^{-1}(c)$ (tức là xác suất kẻ địch tính ngược được $c$ là rất nhỏ).

Câu hỏi trọng tâm của mã hoá là sự tồn tại của các hàm một chiều có là đủ để xây dựng các sơ đồ mã hoá?

Một cách tóm tắt, từ các hàm một chiều ta có thể xây dựng được các phép sinh dãy giả ngẫu nhiên rồi từ đó xây dựng được các sơ đồ mã hóa khóa bí mật. Đối với các sơ đồ mã hóa khóa công khai, ta sẽ phải dựa trên các hàm mạnh hơn các hàm một chiều. Đó là hoán vị cửa lật một chiều (trapdoor one-way permutation: bản chất như hàm một chiều nhưng có thêm một cửa lật, bình thường tính ngược khó nhưng có cửa lật sẽ giúp ta tính hàm ngược dễ).

Kết luận là :

các hàm một chiều là cần và đủ để xây dựng mã hóa khóa bí mật.
các hàm một chiều là cần và các hoán vị cửa lật một chiều là đủ để xây dựng mã hóa khóa công khai. Quan hệ thân thiết giữa các hàm một chiều và các hoán vị cửa lật một chiều hiện vẫn còn đang trong quá trình tìm hiểu nhau

Quan hệ giữa các hàm một chiều và lý thuyết độ phức tạp ra sao?
Sự tồn tại hàm một chiều hiển nhiên dẫn đến sự tồn tại các bài toán NP khó tính theo độ phức tạp trung bình (average-case complexity), từ đó dẫn tới sự tồn tại các bài toán NP khó (tức là tính theo độ phức tạp của trường hợp tệ nhất), có nghĩa là $\mathbf{P} \neq \mathbf{NP}$ . Chiều ngược lại vẫn còn là câu hỏi mở. Do đó dù $\mathbf{P} \neq \mathbf{NP}$ vẫn chưa chắc đã tồn tại các bài toán bài toán NP khó tính theo độ phức tạp trung bình và dù tồn tại các bài toán bài toán NP khó tính theo độ phức tạp trung bình vẫn chưa chắc đã tồn tại các hàm một chiều!

Hy vọng khi có thời gian sẽ tiềp tục được trao đổi chi tiết hơn các kết quả trên cùng các bạn.
Chúc mọi người một năm học, năm dạy mới đầy lý thú!

Chủ đề : Bảo mật và mật mã học, Lý thuyết tính toán. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

12 Comments

Thinh Nguyen

Posted 20/09/2009 at 11:35 pm | Permalink

Hay wa, e se xem sau!

Reply
Ngô Quang Hưng

Posted 21/09/2009 at 10:10 am | Permalink

Hello Hiệu, bài viết rất hay, nhiều thông tin. Tôi có vài góp ý lặt vặt

1. Thay vì nói “bài toán thực hiện được trong thời gian đa thức”, có lẽ nên nói “giải được trong thời gian đa thức”

2. Nên dùng KHONG hay NO một cách nhất quán

3. Chữ “sơ đồ mã hóa” chắc là Hiệu dịch từ “encryption scheme”? Thay “sơ đồ” bằng “phương pháp” hay “thuật toán” có lẽ dễ hiểu hơn.

Reply
RongChoi

Posted 21/09/2009 at 11:42 am | Permalink

Cảm ơn anh Hưng đã góp ý.
1. Đúng là phải nói bài toán giải được, còn khi nói tới thuật toán để giải bài toán thì mới dùng từ thực hiện được. RongChoi sẽ sửa lại các chỗ chưa chính xác.
2. Chỗ YES với NO là RongChoi copy-paste định nghĩa của anh Hưng bên bài PCP1 nên quên đổi sang CO với KHONG
3. Đúng là RongChoi lấy từ “encryption scheme”. Tuy vậy RongChoi vẫn muốn dịch là sơ đồ mã hoá bởi một sơ đồ mã hoá (encryption scheme) gồm 2 thuật toán: thuật toán mã hoá (encryption algorithm) và thuật toán giải mã (decryption algorithm).
RC

Reply
myheeu

Posted 21/09/2009 at 10:52 pm | Permalink

Theo ý kiến của em thì Encryption Scheme em thấy có thể dịch là “lược đồ mã hóa”, theo như em biết trong CNTT người ta (sách ở Việt Nam) hay dùng từ scheme/schema là “lược đồ” (nhất là trong CSDL). Ngẫm ra thấy lược đồ có vẽ “hay” hơn sơ đồ!

Reply
Thinh Nguyen

Posted 22/09/2009 at 11:19 pm | Permalink

@RC huynh: Huynh co the noi ro them ve $\mathbf{EE} \neq \mathbf{NEE}$ khong a?

Reply
RongChoi

Posted 24/09/2009 at 2:29 pm | Permalink

Bạn myheeu ngẫm nghĩ điều gì có thể nói ra không tại sao lược đồ lại hay hơn sơ đồ nhỉ?

@Thinh:

$\mathbf{EE}$ là hàm mũ mũ (chính xác hơn thì là “Double-Exponential Time With Linear Exponent”) tức là lớp có độ phức tạp thời gian là $2^{2^{O(n)}}$ . Một cách tự nhiên thì $\mathbf{NEE}$ là Non-deterministic EE.

Cũng như với lớp $\mathbf{P}$ , người ta tin rằng máy không đơn định mạnh hơn máy đơn định, nên giả thiết $\mathbf{EE} \neq \mathbf{NEE}$ có vẻ cũng hợp lý.

Với giả thiết này thì như trên ta nói, có thể xây dựng được bài toán tìm kiếm khó hơn quyết định. Chính xác thì là, xuất phát từ bất kỳ ngôn ngữ $L$ nào thuộc $\mathbf{NEE}-\mathbf{EE}$ , ta có thể xây dựng được một ngôn ngữ $L'$ thuộc $\mathbf{NP}-\mathbf{P}$ sao cho bất kỳ bài toán tìm kiếm nào tương ứng với $L'$ cũng khó hơn bào toán quyết định $L'$ .

Ngôn ngữ $L'$ được xây dựng rất đơn giản, dùng kỹ thuật “downward separation” trong chứng minh nếu $\mathbf{NEE} \neq \mathbf{EE}$ kéo theo $\mathbf{NP} \neq \mathbf{P}$ như sau. Với mọi $x \in L$ thì cho tương ứng một từ $x' \in L'$ bằng cách nhét thêm một đống bít $0$ vào cuối để độ dài tổng cộng là hàm mũ mũ của $|x|$ ( $2^{2^{|x|}}$ ). Tức là $x' = x 0^{(2^{2^{|x|}}- |x|)}$ . Khi đó hiển nhiên nếu $x \in L$ được quyết đinh bởi hàm mũ mũ theo độ dài của $x$ thì có nghĩa là $x' \in L'$ được quyết đinh bởi hàm đa thức theo độ dài của $x'$ . Do vậy $L \in \mathbf{NEE}-\mathbf{EE}$ kéo theo $L' \in \mathbf{NP}-\mathbf{P}$ .

Điểm nhấn là cách xây dựng trên cho ta một tính chất quan trọng và rất hiển nhiên về tính chất rất thưa của ngôn ngữ $L$ : số từ có độ dài $n$ thuộc ngôn ngữ $L'$ nhiều nhất chỉ là $log(n)$ .

Tính chất thưa này có ý nghĩa gì? Nó là rất quan trọng để chứng minh: nếu có một bài toán tìm kiếm tương ứng với $L'$ mà qui dẫn được về bài toán quyết định $L'$ thì kéo theo luôn $L' \in \mathbf{P}$ (trái với $L' \in \mathbf{NP}-\mathbf{P}$ thiết lập phía trên).

Ý tưởng để chứng minh điều này là gì? Giả sử ta có một thuật toán trong thời gian đa thức tìm kiếm lời giải cho $L'$ bằng cách truy cập thuật toán quyết định cho $L'$ (nói theo lối chính xác thì là: tồn tại một quan hệ NP-relation $R$ sao cho $L'_R=L'$ và bài toán tìm kiếm $\Pi_R$ qui dẫn được về $L'_R=L'$ ). Khi đó ta có thể loại toàn bộ việc truy cập thuật toán quyết định cho $L'$ bằng cách đoán tất cả câu trả lời cho các câu hỏi. Vì số từ có thể để hỏi (có dạng $x 0^{(2^{2^{|x|}}- |x|)}$ , nếu không ta có câu trả lời ngay là không thuộc $L'$ ) là rất thưa (hàm $log$ ), tập hợp tất cả các bộ trả lời có thể sẽ có số phần tử là chỉ đa thức! Như vậy ta có thuật toán trong thời gian đa thức tìm kiếm lời giải cho $L'$ bằng tay không, tức là $L' \in \mathbf{P}$ !
RC

Reply
myheeu

Posted 24/09/2009 at 6:52 pm | Permalink

@Rongchoi: Tại vì em tra từ điển thấy thế anh à, cuốn từ điển mà em dùng là cuốn của nhà giáo Nguyễn Lân và cuốn của Lê Khả Kế.

Reply
Thinh Nguyen

Posted 26/09/2009 at 3:16 am | Permalink

@RC huynh: Thks 4 detail reply. Congrats on becoming new blogger. Se tiep tuc thao lua^.n the^m trong tuong lai ga^`n.

Reply
Thinh Nguyen

Posted 16/10/2009 at 12:58 am | Permalink

@RC huynh:
Như vậy, kỹ thuật đệm tạo ra tính thưa, đến lượt mình nó cho ta phép qui dẫn từ tìm kiếm về quyết định.

“Quan hệ thân thiết giữa các hàm một chiều và các hoán vị cửa lật một chiều hiện vẫn còn đang trong quá trình tìm hiểu nhau”. Em nghĩ các primitive crypto building blocks này (OWF, PRNG, …) có rất nhiều tính chất thú vị, sao ta không tìm hiểu thêm về quan hệ của chúng, lần cuối có breakthroughs trong quan hệ này là gì (các recent results chẳng hạn).

Reply
RongChoi

Posted 16/10/2009 at 10:24 am | Permalink

Thịnh,
RC có dạy một cous về các thứ này, khi nào có thời gian sẽ trình bày dần dần. Thịnh muốn tìm hiểu có thể đọc các tài liệu sau:
1. The Foundations of Cryptography , Oded Goldreich.
http://www.wisdom.weizmann.ac.il/~oded/frag.html
2. Lecture Notes on Cryptography at the MIT, S. Goldwasser and M. Bellare.
http://cseweb.ucsd.edu/users/mihir/papers/gb.html
3. Introduction to Modern Cryptography, Mihir Bellare and Phillip Rogaway.
http://cseweb.ucsd.edu/users/mihir/cse207/classnotes.html
RC

Reply
Thinh Nguyen

Posted 16/10/2009 at 8:20 pm | Permalink

@RC huynh:
1. Paragraph cuối của comment September 24, 2009 at 2:29 pm concise wa. Nhưng có lẽ phù hợp vì ta chỉ cần trường hợp riêng ở đây
2. Đệ sẽ cố gắng đọc các tài liệu đó. Cuốn HAC có lẽ phù hợp hơn với beginner.
TN

Reply
Thinh Nguyen

Posted 21/10/2009 at 8:01 pm | Permalink

@RC huynh: Đệ đang đọc cuốn [GB]. Nhiều khái niệm mới chưa hiểu hết được. Một câu hỏi có phần “ngây ngô” là “provable security” và “proof theory” có liên quan gì đến nhau không?

Reply