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

Với bộ rắc rối hóa chương trình O, ta có thể biến một hệ thống mật mã khóa riêng thành hệ thống mật mã khóa công cộng. Hệ thống mật mã khóa riêng có thể được mô tả như sau: bên gửi và bên nhận dùng chung một khóa bí mật K cùng với một giải thuật mã hóa E và giải mã D. Gọi E _K là chương trình mã hóa dùng E với khóa K, và D_K là chương trình giải mã dùng D với khóa K. Để mã hóa một thông điệp M thì bên gửi sẽ gửi E _K(M), và bên nhận giải mã với D_K(E _K(M)) = M.

Như ta đã nói trong các bài trước, việc làm thế nào để phân phối và đồng ý với khóa K là vấn đề khó giải quyết của hệ thống mật mã khóa riêng. Với bộ rắc rối hóa O, bên nhận có thể cho mọi người biết O(E _K). Ai muốn gửi thông điệp M thì chỉ cần gửi O(E_K)(M) là xong. Nhờ có O, không thể đoán được K từ O(E _K).

Cho đến đây, ta vẫn chưa định nghĩa rõ ràng thế nào là một bộ rắc rối hóa chương trình bằng toán học. Bộ rắc rối hóa phải thỏa mãn những tính chất gì thì các ứng dụng nêu trên mới có thể thành hiện thực được? Tệ hơn nữa, nhỡ khi không tồn tại một bộ rắc rối hóa như ta mong muốn thì sao? Làm sao chứng minh được điều này?