Rắc rối hóa chương trình (hết)

Về mặt trực quan, một chương trình P sau khi được rắc rối hóa thành O(P) thì ta không thể hiểu được logic của O(P) nữa. Làm thế nào để mô tả điều này về mặt toán học?

Một bài báo của Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, và Yang nghiên cứu định nghĩa như sau. Tôi chỉ mô tả lại đây ý tưởng chính đằng sau định nghĩa của họ. Định nghĩa cụ thể bằng toán học bạn có thể đọc trực tiếp.

Nếu O(P) cực kỳ khó hiểu, thì có O(P) cũng không khác gì có P như một hộp đen (blackbox). Hộp đen ở đây được hiểu là ta không biết P hoạt động thế nào, chỉ biết rằng cho bất kỳ input x nào thì ta biết output P(x) tương ứng của chương trình P, nhưng không có thông tin gì khác về việc làm thế nào mà P tính được P(x). Ví dụ, người ta có thể bán cho bạn một cái máy mà ta gõ vào tiếng Việt thì máy dịch sang tiếng Anh. Giả sử bạn không bao giờ mở máy ra xem thì bạn có truy cập theo kiểu hộp đen đến cái giải thuật dịch đấy. Nếu P là giải thuật dịch, việc bạn có O(P) cũng chẳng hơn gì có cái máy dịch không được tháo ra, dù O(P) vẫn là mã nguồn của P (chỉ bị rắc rối hóa đi thôi).

Cụ thể hơn về mặt toán học, thì O là bộ rắc rối hóa tốt nếu những gì ta tính toán được hay suy ra được từ O(P) cũng y như những gì ta tính toán được hay suy ra được từ truy cập kiểu hộp đen đến P.

Nếu ta chấp nhận định nghĩa này của bộ rắc rối hóa (định nghĩa có thể hơi mạnh quá), thì các tác giả bài báo trên chứng minh được rằng tồn tại một họ F các hàm số không thể rắc rối hóa được theo nghĩa như sau. Tồn tại một thuộc tính p : F --> {0,1} của các hàm số này thỏa mãn tính chất sau đây:
 

1. Nếu có bất kỳ chương trình Q nào tính một hàm f thuộc F, thì thuộc tính p(f) có thể tính được một cách hiệu quả,
2. Trong khi đó nếu ta chỉ có truy cập kiểu hộp đen đến một hàm f chọn ngẫu nhiên từ họ F, thì không có giải thuật hiệu quả nào để tính p(f) tốt hơn cách đoán bừa (random guessing).

Có lẽ cần giải thích chi tiết hơn một chút. Giả sử tồn tại một bộ rắc rối hóa O . Nếu O là bộ rắc rối hóa tốt thì, theo định nghĩa, nếu ta chọn một hàm f bất kỳ từ họ F thì việc có O(f) cũng không hơn gì việc có truy cập kiểu hộp đen đến f. Gọi Q = O(f). Theo tính chất (1) thì ta có thể tính p(f) một cách hiệu quả. Theo tính chất (2) thì ta không tính được p(f) một cách hiệu quả nếu chỉ có truy cập kiểu hộp đen đến f. Như vậy rõ ràng là O(f) chứa nhiều "thông tin" (trong trường hợp này là thuộc tính p của f) hơn là cái hộp đen tính f. Nói cách khác, O đã không hoàn toàn rắc rối hóa f.

Vài hướng nghiên cứu tiếp:

• Tìm một định nghĩa có ý nghĩa về mặt thực tiễn (cho software protection, watermarking, vân vân) cho bộ rắc rối hóa sao cho việc rắc rối hóa này vẫn có thể làm được về mặt lý thuyết.
• Giả sử ta vẫn dùng định nghĩa trên, có một lớp các hàm số nào hữu dụng mà lại có thể rắc rối hóa được hay không? (Bộ hàm số F như trên chỉ là một phản ví dụ không bao gồm hết các hàm hữu dụng trong thực tế.)