Mật mã dưới góc nhìn độ phức tạp tính toán
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
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 một 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 \(\mathsf{P}\), \(\mathsf{NP}\), \(\mathsf{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 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 \(\mathsf{NP}\)-đầy đủ đều có tính chất này. Kỹ thuật quy 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 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 \(\mathsf{P}\) và \(\mathsf{NP}\) là \(\mathsf{FP}\) và \(\mathsf{FNP}\) (viết tắt của Function \(\mathsf{P}\), Function \(\mathsf{NP}\)). Khi đó ta có thể chứng minh được \(\mathsf{P} = \mathsf{NP}\) khi và chỉ khi \(\mathsf{FP} = \mathsf{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 \(\mathsf{FNP}\) thực hiện được trong thời gian đ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 "\(\mathsf{P}\) vs. \(\mathsf{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ý (\(\mathsf{EE} \neq \mathsf{NEE}\)), có những ngôn ngữ \(L \in \mathsf{NP}\) mà ở đó bài toán tìm kiếm không thể quy 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 \(\mathsf{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 \(\mathsf{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 \(\mathsf{P}\) và \(\mathsf{FP}\) 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 - "\(\mathsf{P} \neq \mathsf{NP}\)".
I.1 Lớp bài toán \(\mathsf{FNP}\) và \(\mathsf{FP}\)
Một cách nôm na, cho một ngôn ngữ (lớp \(\mathsf{SAT}\) chẳng hạn) và một đầu vào (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 đầu vào có thuộc ngôn ngữ (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 đầu vào thuộc ngôn ngữ (công thức đã cho là thỏa được), một lời giải chứng tỏ điều đó (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ỏ đầu vào thuộc ngôn ngữ. 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ữ dựa trên các quan hệ hai ngôi.
Một quan hệ hai ngôi \(R \subseteq \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:
- Kiểm tra được trong thời gian đa thức: Với các đầu vào \((x, y)\), ta có thể xác định liệu \(x\) có quan hệ với \(y\) (ký hiệu \(R(x,y)\)) hay không trong thời gian đa thức tính trên \(|x|\) (độ dài của \(x\)).
- Cân bằng đa thức (polynomially balanced): 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 định nghĩa về lớp \(\mathsf{NP}\): một ngôn ngữ \(L\) thuộc \(\mathsf{NP}\) nếu tồn tại một poly-time verifier \(V\):
- Verifier nhận inputs \((x, w)\), và trả lời CÓ/KHÔNG. 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" \(w\) sao cho \(V(x,w) = \text{CÓ}\).
- Nếu \(x\) là NO-instance thì với bất kỳ "chứng minh" \(w\) nào ta cũng có \(V(x,w) = \text{KHÔNG}\).
Một verifier \(V\) như vậy thực chất chính là một NP-relation \(R_V\) và ngôn ngữ \(L_{R_V} = L\). 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 \mid \exists\, y : R(x,y)\}\) và ngôn ngữ \(L_R\) hiển nhiên là thuộc \(\mathsf{NP}\) (bằng cách đặt verifier \(V\) chính là \(R\)).
Như vậy thực chất \(\mathsf{NP}\) là tập hợp tất cả các ngôn ngữ \(L_R\) 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.
Với quan hệ \(R\), ta định nghĩa bài toán tìm kiếm \(S_R\) như sau:
- Đầu vào: Cho một \(x\).
- Trả lời: Tìm một \(y\) sao cho \(R(x,y)\), nếu tồn tại một \(y\) như vậy; hoặc trả lời "KHÔNG" 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 \(S_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à KHÔNG, 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)\)).
- \(\mathsf{FNP}\) là tập hợp tất cả các bài toán \(S_R\) với \(R\) là NP-relation.
- \(\mathsf{FP}\) là tập con của \(\mathsf{FNP}\) bao gồm các bài toán \(S_R\) ở đó câu "Trả lời" được thực hiện trong thời gian đa thức.
Để ý rằng, cho trước một ngôn ngữ \(L\), 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 \(S_R\).
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\) và \(R'\) sao cho \(L_R = L_{R'}\) thì tương ứng với \(L\) có hai bài toán tìm kiếm \(S_R\) và \(S_{R'}\). Đ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ộ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:
\(\mathsf{P} = \mathsf{NP}\) khi và chỉ khi \(\mathsf{FP} = \mathsf{FNP}\).
Chứng minh. □
– Chiều thuận: nếu \(\mathsf{FP} = \mathsf{FNP}\) thì \(\mathsf{P} = \mathsf{NP}\). Điều này hiển nhiên: tìm được lời giải nhanh (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.
– Chiều ngược: nếu \(\mathsf{P} = \mathsf{NP}\) thì \(\mathsf{FP} = \mathsf{FNP}\). Ý tưởng là sử dụng tìm kiếm nhị phân. Cho một NP-relation bất kỳ \(R\), ta cần chứng minh \(S_R \in \mathsf{FP}\), tức là với mọi \(x\), cần tìm trong thời gian đa thức \(y\) để \(R(x,y)\) (nếu có), hoặc trả lời KHÔNG nếu không có \(y\) nào thỏa mãn.
Do \(\mathsf{P} = \mathsf{NP}\), 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 KHÔNG là xong. Trường hợp tồn tại \(y\), ta tìm như sau:
Với mỗi \(x\) và \(z \in \Sigma^*\), định nghĩa quan hệ \(R_z(x,y) \iff R(x,y)\) và \(y \geq z\) (theo thứ tự từ điển trên \(\Sigma^*\)). Do \(R\) là NP-relation, \(R_z\) cũng là NP-relation, nên bài toán quyết định \(L_{R_z}\) thực hiện được trong thời gian đa thức. Lấy \(z\) là điểm giữa trong không gian tìm kiếm: nếu \(x \in L_{R_z}\) thì tồn tại lời giải phía sau \(z\), ngược lại tồn tại lời giải phía trước \(z\). Như vậy ta giới hạn miền tìm kiếm xuống còn một nửa. Tiếp tục tương tự ta 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 giả thiết khá hợp lý (\(\mathsf{EE} \neq \mathsf{NEE}\)), có những ngôn ngữ \(L \in \mathsf{NP}\) mà ở đó bài toán tìm kiếm không thể quy dẫn về 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, e_1), \ldots, (p_k, e_k)\}\) với \(p_i\) là các số nguyên tố và \(e_i\) là các số tự nhiên. Ta định nghĩa:
Với quan hệ định nghĩa như vậy, ngôn ngữ \(L_{R_{\mathrm{FACTOR}}}\) chính là toàn bộ các số tự nhiên, vì mọi số tự nhiên đều có 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_{\mathrm{FACTOR}}}\) do đó là tầm thường.
Trong khi đó, bài toán tìm kiếm \(S_{R_{\mathrm{FACTOR}}}\) 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
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 và một chứng minh (một số tự nhiên) như sau:
Đây là cách định nghĩa tự nhiên nhất để chứng minh một số 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 \(S_{R_1}\) 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 số \(a\) như sau:
với \(\left(\frac{a}{n}\right)\) 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\) nguyên tố cùng nhau với \(n\), theo tiêu chuẩn Euler ta đều có \(a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod{n}\), tức là \((n, a) \notin R_2\).
- Ngược lại, nếu \(n\) là hợp số thì, ít nhất một nửa các số nguyên tố cùng nhau với \(n\) thỏa mãn \(a^{(n-1)/2} \not\equiv \left(\frac{a}{n}\right) \pmod{n}\). (Chứng minh điều này không khó, bởi tập các \(a\) để \(a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod{n}\) tạo thành một 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\) vi phạm điều đó. Điều đó dẫn đến tập các \(a\) thỏa mãn đẳng thức 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_2}\) chính là COMPOSITE. Tuy vậy, bài toán tìm kiếm \(S_{R_2}\) ở đâ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 số \(a\) nguyên tố cùng nhau với \(n\) là đã có khả năng chí ít là 50% để có \(R_2(n,a)\).
Vấn đề còn lại là tính \(a^{(n-1)/2} \bmod n\) có dễ không? Tính \(a^{(n-1)/2} \bmod n\) là dễ (bằng bình phương nhanh), nhưng còn ký hiệu Jacobi \(\left(\frac{a}{n}\right)\)? Định nghĩa của \(\left(\frac{a}{n}\right)\) 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 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 \(\left(\frac{a}{n}\right)\) 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\).
Luật tương hỗ toàn phương nguyên thủy dành cho số nguyên tố thật đẹp. Chỉ muốn nói thêm là trong suốt một thời gian dài, người ta đã tưởng các số nguyên tố là rất kỳ bí và có tính độc lập nhau - hai 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ế. Nó giúp ta có một thuật toán kiểm tra xem một số bất kỳ có là nguyên tố hay không: lấy bất kỳ số \(a\) nguyên tố cùng nhau với \(n\), nếu \(a^{(n-1)/2} \not\equiv \left(\frac{a}{n}\right) \pmod{n}\) thì chắc chắn \(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 thì có nghĩa là \(n\) nguyên tố với sai số chỉ là \(2^{-100}\)! Gần đây (2002) đã 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 (thuật toán AKS, thú vị là chứng minh khá sơ cấp), nhưng trong thực tế người ta vẫn dùng các thuật toán xác suất vì 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
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ó khóa) thì không thể giải được mã. Tạm gác chuyện chiếc chìa khóa thần kỳ trong mã hóa 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ã hóa 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 \(x\) (có thể coi là bản rõ - plaintext), thì tính \(y = f(x)\) (có thể coi là bản mã - ciphertext) là dễ, nhưng cho \(y\) thì việc tính ngược một \(x\) (có thể có nhiều \(x\)) để \(f(x) = y\) 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 "\(\mathsf{P}\) vs. \(\mathsf{NP}\)" của lý thuyết độ phức tạp?
Ta giả thiết rằng tồn tại một hàm xuôi dễ ngược khó \(f\). 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_f\) như sau:
Dễ thấy \(R_f\) là một NP-relation (kiểm tra \(f(x) = y\) trong thời gian đa thức; nếu \(f\) tính được trong thời gian đa thức trên \(|x|\) và \(|x| \leq p(|y|)\) thì \(R_f\) cân bằng đa thức). Như vậy, bài toán tìm kiếm \(S_{R_f}\) thuộc lớp \(\mathsf{FNP}\). Mà bài toán \(S_{R_f}\) 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ó \(S_{R_f} \notin \mathsf{FP}\), và suy ra \(\mathsf{FP} \neq \mathsf{FNP}\). Theo định lý phía trên, điều đó kéo theo \(\mathsf{P} \neq \mathsf{NP}\).
Kết luậ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à "\(\mathsf{P} \neq \mathsf{NP}\)". Nói cách khác, nếu ta chứng minh được "\(\mathsf{P} = \mathsf{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ư \(\mathsf{EXP}\) để phòng trường hợp \(\mathsf{P} = \mathsf{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 \(\mathsf{P} \neq \mathsf{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 đa 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 \(\mathsf{P} \neq \mathsf{NP}\). Câu hỏi ngược lại là liệu nếu \(\mathsf{P} \neq \mathsf{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 \(y\) mà ta không tính ngược được \(f^{-1}(y)\). Đ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ã hóa, 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ã hóa, 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 \(f\) thỏa mãn:
Một hàm \(f : \{0,1\}^* \to \{0,1\}^*\) được gọi là hàm một chiều nếu:
- Dễ tính: \(f\) tính được trong thời gian đa thức.
- Khó đảo: Cho \(y = f(x)\) với \(x\) được lấy ngẫu nhiên đều, xác suất để bất kỳ thuật toán đa thức nào tính được \(x'\) sao cho \(f(x') = y\) là rất nhỏ (nhỏ hơn bất kỳ đa thức nghịch đảo nào theo độ dài đầu vào).
Câu hỏi trọng tâm của mã hóa 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ã hóa?
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 (pseudorandom generators) rồi từ đó xây dựng được các sơ đồ mã hóa khóa bí mật (symmetric encryption). Đối với các sơ đồ mã hóa khóa công khai (public-key encryption), 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" (trapdoor), bình thường tính ngược khó nhưng nếu có cửa lật sẽ giúp ta tính hàm ngược dễ dàng.
Kết luận:
- 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.
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 dẫn đến chuỗi kéo theo:
Chiều ngược lại vẫn còn là câu hỏi mở. Do đó dù \(\mathsf{P} \neq \mathsf{NP}\) vẫn chưa chắc đã tồn tại các bài toán \(\mathsf{NP}\) khó tính theo độ phức tạp trung bình (average-case complexity); và dù tồn tại các bài toán \(\mathsf{NP}\) khó theo 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ú!