Năm 1868, nhà toán học Charles Dodgson tuyên bố rằng một sơ đồ mã hóa được gọi là mật mã Vigenère là “không thể phá vỡ”. Ông không chứng minh, nhưng ông có những lý do thuyết phục cho niềm tin của mình, vì các nhà toán học đã cố gắng phá mật mã đó trong hơn ba thế kỷ nhưng không thành công. Thế nhưng, trên thực tế thì ngược lại, một sĩ quan bộ binh Đức tên là Friedrich Kasiski đã phá vỡ nó 5 năm trước đó và được ghi lại trong một cuốn sách ít được chú ý vào thời điểm đó.

Năm thập kỷ trước, các nhà mật mã học đã tiến một bước dài theo hướng này. Họ cho thấy rằng có thể tạo ra mật mã an toàn chứng minh được nếu có quyền truy cập vào một thành phần được gọi là “hàm một chiều”, đó là một thứ dễ thực hiện nhưng khó đảo ngược. Kể từ đó, các nhà nghiên cứu đã phát minh ra một loạt các hàm một chiều, mà đơn giản nhất có thể thấy là phép nhân.

Giờ đây, thay vì phải lo lắng về độ an toàn từ mọi khía cạnh của một lược đồ mật mã, các nhà mật mã chỉ cần quan tâm đến hàm cốt lõi của nó. Nhưng không có hàm nào hiện đang được sử dụng đã từng được chứng minh một cách dứt khoát đó là hàm một chiều - chúng ta thậm chí không biết chắc rằng có tồn tại các hàm một chiều thực sự hay không. Trong trường hợp không có chứng minh, các nhà mật mã chỉ đơn giản hy vọng rằng các hàm đã tồn tại sau các cuộc tấn công thực ra là an toàn. Các nhà nghiên cứu không có cách tiếp cận thống nhất để nghiên cứu độ an toàn của các hàm này vì mỗi hàm “đến từ một lĩnh vực khác nhau, từ một nhóm chuyên gia khác nhau”.

Rafael Pass, một nhà mật mã học tại Đại học Cornell (Mỹ) đã đặt ra câu hỏi: “Liệu có tồn tại một vấn đề nào đó, chỉ một vấn đề chính, cho chúng ta biết liệu mật mã (an toàn) có khả thi không?”. Năm 2021, Pass - nhà mật mã học tại Cornell Tech and Cornell University và Yanyi Liu - một nghiên cứu sinh tại Đại học Cornell, đã chứng minh rằng câu trả lời là có. Họ đã chứng minh rằng sự tồn tại của các hàm một chiều thực sự phụ thuộc vào một trong những vấn đề lâu đời nhất và trọng tâm nhất trong một lĩnh vực khác của khoa học máy tính, được gọi là lý thuyết độ phức tạp tính toán. Đó là độ phức tạp Kolmogorov, liên quan đến việc khó phân biệt giữa các chuỗi số ngẫu nhiên và các chuỗi số chứa thông tin nào đó.

Rafael Pass, một nhà mật mã học tại Cornell Tech and Cornell University

Yanyi Liu nghiên cứu sinh tại Đại học Cornell

Liu và Pass đã chứng minh rằng nếu một phiên bản cụ thể nào đó của độ phức tạp Kolmogorov là khó tính toán, thì các hàm một chiều thực sự tồn tại và có một cách rõ ràng để xây dựng nó. Ngược lại, nếu phiên bản này của độ phức tạp Kolmogorov là dễ tính toán, thì các hàm một chiều không thể tồn tại. Pass chia sẻ rằng: “Vấn đề này, đã xuất hiện trước khi người ta đưa ra các hàm một chiều, thì ra lại mô tả đầy đủ đặc trưng của hàm một chiều”.

Phát hiện cho thấy rằng thay vì phải nhìn xa và rộng cho tất cả các hàm một chiều ứng viên, các nhà mật mã học có thể chỉ tập trung nỗ lực vào việc tìm hiểu độ phức tạp Kolmogorov. Có thể nói rằng chứng minh của Pass và Liu là một “công trình đột phá về nền tảng của mật mã”.

ĐỘ PHỨC TẠP TÍNH TOÁN

Thông thường, khi gặp một bài toán khó thì đó là một trở ngại cho công việc. Nhưng trong mật mã, đó là một lợi ích. Năm 1976, hai nhà mật mã học người Mỹ - Martin Hellman và Whitfield Diffie đã viết một bài báo đột phá, trong đó họ lập luận rằng độ khó đặc biệt của các hàm một chiều chính xác là thứ mà các nhà mật mã học cần để đáp ứng nhu cầu của thời đại máy tính đang phát triển.

Trong những thập kỷ sau đó, các nhà nghiên cứu đã tìm ra cách xây dựng nhiều công cụ mật mã từ các hàm một chiều, bao gồm mã hóa khóa bí mật, chữ ký số, các bộ tạo số ngẫu nhiên và chứng minh không lộ tri thức (trong đó một người có thể thuyết phục người khác rằng một tuyên bố là đúng mà không tiết lộ bằng chứng).

Để biết cách hoạt động của hàm một chiều, hãy tưởng tượng ai đó yêu cầu bạn nhân hai số nguyên tố lớn, giả sử 6.547 và 7.079. Đi đến câu trả lời bằng 46.346.213 ta phải làm phép nhân, nhưng đây là một việc dễ làm. Tuy nhiên, nếu ai đó đưa cho bạn số 46.346.213 và hỏi về các thừa số nguyên tố của nó, bạn có thể không trả lời được. Trên thực tế, đối với các số có các thừa số nguyên tố đều lớn, không có cách nào hiệu quả (mà chúng ta đã biết) để tìm ra các thừa số đó. Điều này làm cho phép nhân trở thành một ứng cử viên đầy hứa hẹn cho hàm một chiều. Nhưng chúng ta không biết chắc chắn rằng sẽ là như vậy. Trong tương lai, một ai đó có thể tìm ra một cách phân tích số nhanh hiệu quả.

Các nhà mật mã học đã thu thập được một loạt các hàm một chiều tiềm năng từ các lĩnh vực toán học khác nhau, nhưng không một hàm nào có yêu cầu cao hơn một hàm khác. Giả sử, nếu một ngày phép nhân bị lật đổ như là hàm một chiều, thì điều đó sẽ không nói lên điều gì về tính hợp lệ của các hàm một chiều ứng cử viên khác. Các nhà mật mã học từ lâu đã đặt câu hỏi liệu có một hàm một chiều tinh túy nào đó (gọi là “phổ quát”) - một hàm mà nếu bị phá, sẽ kéo theo tất cả các ứng cử viên khác.

Martin Hellman (giữa) và Whitfield Diffie (phải)

Andrey Kolmogorov

Năm 1985, Leonid Levin, một nhà khoa học máy tính tại Đại học Boston, đã chứng minh rằng một hàm một chiều “phổ quát” như vậy là có nếu như có hàm một chiều.

Pass bắt đầu say mê với mối liên hệ đó khi còn là một sinh viên tốt nghiệp vào năm 2004. Trong nhiều năm, ông đã xoay xở với bài toán này nhưng không mấy thành công. Nhưng Pass cảm thấy chắc chắn có điều gì ở đó và sự bùng nổ các nghiên cứu về độ phức tạp Kolmogorov trong 5 năm qua đã làm tăng thêm sự quan tâm của ông và ông đã cố gắng thuyết phục một số sinh viên tốt nghiệp khám phá câu hỏi cùng với mình. Cuối cùng ông gặp được Yanyi Liu, một sinh viên cao học tại Cornell.

TÍNH NGẪU NHIÊN

Khái niệm về tính ngẫu nhiên về bản chất rất khó để xác định. Nếu ai đó hiển thị cho chúng ta hai chuỗi số 99999999999999999999 và 03729563829603547134 đồng thời nói rằng chúng được chọn ngẫu nhiên, thì khi đó cũng không thể bác bỏ một cách thuyết phục khẳng định đó. Vì cả hai chuỗi đều có cùng xác suất được tạo ra khi chọn các chữ số một cách ngẫu nhiên (chúng có cùng độ dài). Tuy nhiên, chuỗi thứ hai chắc chắn được cảm thấy là ngẫu nhiên hơn.

Để có được khái niệm về một chuỗi số ngẫu nhiên, vào những năm 1960, Andrey Kolmogorov đã quyết định không tập trung vào quá trình tạo ra chuỗi mà dựa vào sự dễ dàng mà nó có thể được mô tả. Chuỗi 99999999999999999999 có thể được mô tả ngắn gọn là “20 9s”, nhưng chuỗi 03729563829603547134 lại không có bất kỳ mô tả nào ngắn hơn chính chuỗi đó.

Kolmogorov đã định nghĩa độ phức tạp của một chuỗi là độ dài của chương trình ngắn nhất có thể mà tạo ra chuỗi đó dưới dạng đầu ra. Nếu chúng ta đang xử lý các chuỗi có 1 nghìn chữ số, thì một số chuỗi có các chương trình rất ngắn, chẳng hạn như “in một nghìn số 9” hoặc “in số 23319” hoặc “in một nghìn chữ số đầu tiên của π bằng công thức sau,... ” Các chuỗi khác không thể mô tả ngắn gọn và không có chương trình nào ngắn hơn chương trình viết ra toàn bộ chuỗi và chỉ yêu cầu máy tính in ra.

Độ phức tạp Kolmogorov nhanh chóng trở thành một trong những khái niệm cốt lõi của khoa học máy tính. Khái niệm này cơ bản đến mức nó đã được phát hiện một cách độc lập nhiều lần vào những năm 1960.

ĐỘ PHỨC TẠP KOLMOGOROV

Một cách đo lường tính ngẫu nhiên dựa trên mức độ dễ dàng để mô tả một chuỗi số. Chương trình có thể xuất ra chuỗi càng đơn giản thì độ phức tạp Kolmogorov của chuỗi càng thấp.

Chỉ có một nhược điểm đối với độ phức tạp của Kolmogorov là không tính toán được, nghĩa là không có chương trình nào có thể tính ra độ phức tạp của mọi chuỗi có thể có. Chúng ta biết điều này bởi vì nếu có một chương trình như vậy, chúng ta sẽ dẫn đến một sự mâu thuẫn.

Để thấy điều này, hãy tưởng tượng chúng ta có một chương trình mà có thể tính độ phức tạp Kolmogorov cho bất kỳ chuỗi nào. Gọi chương trình đó là K. Bây giờ, tìm kiếm chuỗi số nhỏ nhất gọi là S - có độ phức tạp Kolmogorov gấp đôi độ dài của K. Nói một cách cụ thể, chúng ta có thể tưởng tượng rằng K có 1 triệu ký tự, vì vậy chúng ta đang đi tìm một chuỗi S có độ phức tạp Kolmogorov là 2 triệu (nghĩa là chương trình ngắn nhất xuất ra S có 2 triệu ký tự).

Với chương trình K trong hộp công cụ, việc tính toán S rất dễ dàng (mặc dù không nhất thiết phải nhanh chóng). Viết một chương trình mới và gọi là P. Chương trình P về cơ bản sẽ “Duyệt qua tất cả các chuỗi theo thứ tự, sử dụng chương trình K để tính độ phức tạp Kolmogorov của chúng, cho đến khi tìm thấy cái đầu tiên có độ phức tạp Kolmogorov là 2 triệu”. Khi đó sẽ cần sử dụng chương trình K khi xây dựng P, vì vậy tổng thể P sẽ có hơn 1 triệu ký tự một chút. Nhưng chương trình này xuất ra S và sẽ định nghĩa S là một chuỗi mà chương trình ngắn nhất có 2 triệu ký tự. Có thế thấy sự mâu thuẫn nhưng mâu thuẫn này sẽ được giải thích, nếu thay vì tìm kiếm chương trình ngắn nhất tạo ra một chuỗi thì ta tìm kiếm chương trình ngắn nhất có hiệu quả “hợp lý” xuất ra chuỗi.

Vậy chương trình P mất rất nhiều thời gian để chạy, vì nó phải kiểm tra rất nhiều chuỗi. Nếu cấm các chương trình chậm như vậy sẽ có một khái niệm gọi là độ phức tạp Kolmogorov “giới hạn thời gian”. Phiên bản này của độ phức tạp Kolmogorov có thể tính toán được và có thể tính độ phức tạp Kolmogorov có giới hạn thời gian cho mọi chuỗi có thể, ít nhất là về nguyên tắc. Và theo một nghĩa nào đó, nó là một khái niệm tự nhiên như độ phức tạp Kolmogorov ban đầu. Vì độ phức tạp Kolmogorov có giới hạn thời gian là có thể tính toán được, một câu hỏi tự nhiên tiếp theo là việc tính toán sẽ phức tạp như thế nào. Vấn đề này đã được Liu và Pass chứng minh, là chìa khóa cho việc liệu các hàm một chiều có tồn tại hay không.

Cụ thể hơn, giả sử đặt tầm nhìn vào một mục tiêu thấp hơn là tính độ phức tạp Kolmogorov có giới hạn thời gian chính xác của mọi chuỗi có thể có (giả sử hài lòng để tính nó một cách gần đúng và chỉ cho hầu hết các chuỗi). Nếu có một cách hiệu quả để làm điều này như Liu và Pass đã chỉ ra thì các hàm một chiều thực sự không thể tồn tại. Trong trường hợp đó, tất cả các hàm một chiều ứng viên sẽ bị phá vỡ ngay lập tức, không chỉ trên lý thuyết mà còn trong thực tế.

Ngược lại, nếu việc tính toán độ phức tạp Kolmogorov giới hạn thời gian gần đúng là quá khó để giải hiệu quả cho nhiều chuỗi, thì Liu và Pass đã chỉ ra rằng phải tồn tại các hàm một chiều thực sự. Nếu đúng như vậy, bài báo của họ thậm chí còn cung cấp một cách cụ thể để làm việc này. Hàm một chiều mà Liu và Pass mô tả trong bài báo quá phức tạp để sử dụng trong các ứng dụng thế giới thực, nhưng trong mật mã, các cấu trúc thực hành thường nhanh chóng đi theo một bước đột phá về mặt lý thuyết. Tính không thực tế của hàm một chiều của Liu và Pass không phải là một hạn chế cơ bản.

KẾT LUẬN

Bài báo đã mở ra một loạt các nghiên cứu mới về giao diện của lý thuyết mật mã và độ phức tạp. Mật mã học năng động, thực dụng và lạc quan, trong khi lý thuyết độ phức tạp thay đổi chậm và bảo thủ. Giờ đây, mật mã và độ phức tạp có một mục tiêu chung và mỗi lĩnh vực cung cấp cho lĩnh vực kia một góc nhìn mới.

Các nhà mật mã học hiện đang phải đối mặt với nhiệm vụ cố gắng làm cho hàm một chiều của Liu và Pass trở nên thiết thực hơn. Họ cũng đang bắt đầu khám phá xem liệu có bất kỳ “vấn đề chính” nào khác ngoài độ phức tạp Kolmogorov mà cũng có thể chi phối sự tồn tại của các hàm một chiều hoặc các công cụ mật mã phức tạp hơn. Trong khi đó, các nhà lý thuyết về độ phức tạp đang bắt đầu đào sâu hơn để tìm hiểu độ khó của độ phức tạp Kolmogorov.