Thủ thuật mật mã làm cho một vấn đề khó trở nên dễ dàng hơn một chút | Tạp chí Quanta

Cách tốt nhất để giải quyết vấn đề khó khăn là gì? Đó là câu hỏi cốt lõi của một lĩnh vực con 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à một câu hỏi khó trả lời, nhưng hãy lật nó lại và nó sẽ trở nên dễ dàng hơn. Cách tiếp cận tồi tệ nhất hầu như luôn là thử và sai, bao gồm việc đưa ra các giải pháp khả thi cho đến khi giải pháp đó hiệu quả. Nhưng đối với một số vấn đề, có vẻ như không có giải pháp thay thế nào - cách tiếp cận tệ nhất cũng là cách tốt nhất.

Các nhà nghiên cứu từ lâu đã tự hỏi liệu điều đó có thực sự xảy ra hay không, cho biết Rahul Ilango, một sinh viên tốt nghiệp đang nghiên cứu lý thuyết phức tạp tại Viện Công nghệ Massachusetts. “Bạn có thể hỏi, 'Có vấn đề nào mà việc đoán và kiểm tra là tối ưu không?'”

Các nhà lý thuyết về độ phức tạp đã nghiên cứu nhiều vấn đề tính toán, và ngay cả những vấn đề khó khăn nhất cũng thường thừa nhận một số loại thủ tục hoặc thuật toán thông minh giúp việc tìm ra giải pháp dễ dàng hơn một chút so với việc thử và sai thuần túy. Trong số ít trường hợp ngoại lệ có cái gọi là vấn đề nén, trong đó mục tiêu là tìm mô tả ngắn nhất về tập dữ liệu.

Nhưng tháng 11 năm ngoái, hai nhóm nhà nghiên cứu độc lập phát hiện một thuật toán khác cho các vấn đề về nén - một thuật toán nhanh hơn một chút so với việc kiểm tra tất cả các câu trả lời có thể có. Cách tiếp cận mới hoạt động bằng cách điều chỉnh thuật toán được các nhà mật mã học phát minh ra cách đây 25 năm để giải quyết một vấn đề khác. Chỉ có một hạn chế: Bạn cần điều chỉnh thuật toán phù hợp với kích thước tập dữ liệu của mình.

“Chúng thực sự là những kết quả đẹp đẽ và quan trọng,” nói Eric Allen, một nhà khoa học máy tính lý thuyết tại Đại học Rutgers.

Xác định độ cứng

Các kết quả mới này là kết quả mới nhất nhằm điều tra một vấn đề được nghiên cứu lần đầu tiên ở Liên Xô, rất lâu trước khi lý thuyết phức tạp ra đời. Allender nói: “Trước khi tôi học tiểu học, người dân ở Nga đã hình thành nên điều này.

Bài toán tính toán cụ thể mà các nhà nghiên cứu Liên Xô nghiên cứu, được gọi là bài toán kích thước mạch tối thiểu, giống với bài toán mà các nhà thiết kế phần cứng máy tính luôn phải đối mặt. Nếu bạn được cung cấp các thông số kỹ thuật đầy đủ về cách hoạt động của một mạch điện tử, bạn có thể tìm thấy mạch đơn giản nhất có thể thực hiện được công việc đó không? Không ai biết cách giải quyết vấn đề này nếu không có “perebor” - một từ tiếng Nga gần tương đương với “tìm kiếm toàn diện”.

Bài toán kích thước mạch tối thiểu là một ví dụ về bài toán nén. Bạn có thể mô tả hành vi của mạch bằng một chuỗi bit dài — 0 và 1 — rồi hỏi liệu có cách nào để tái tạo hành vi tương tự bằng cách sử dụng ít bit hơn không. Việc kiểm tra tất cả các cách bố trí mạch có thể sẽ mất thời gian tăng theo cấp số nhân với số bit trong chuỗi.

Kiểu tăng trưởng theo cấp số nhân này là đặc điểm xác định của một vấn đề tính toán khó. Nhưng không phải tất cả các bài toán khó đều khó như nhau — một số bài có thuật toán nhanh hơn tìm kiếm toàn diện, mặc dù thời gian chạy của chúng vẫn tăng theo cấp số nhân. Theo thuật ngữ hiện đại, câu hỏi quan trọng nhất là liệu có tồn tại thuật toán nào như vậy cho các vấn đề nén hay không.

Năm 1959, một nhà nghiên cứu nổi tiếng tên là Sergey Yablonsky tuyên bố đã chứng minh được rằng tìm kiếm toàn diện thực sự là cách duy nhất để giải quyết vấn đề kích thước mạch tối thiểu. Nhưng bằng chứng của ông vẫn để lại một số lỗ hổng. Một số nhà nghiên cứu đã nhận thấy những sai sót vào thời điểm đó, nhưng Yablonsky có đủ ảnh hưởng để ngăn cản hầu hết những người khác nghiên cứu câu hỏi về perebor.

Trong những thập kỷ sau đó, rất ít nhà nghiên cứu nghiên cứu các vấn đề nén, và câu hỏi perebor chủ yếu được biết đến như một chú thích cuối trang trong thời tiền sử của lý thuyết phức tạp. Sự chú ý rộng rãi đến câu hỏi này chỉ xuất hiện gần đây, sau khi các nhà nghiên cứu phát hiện ra mối liên hệ kỳ lạ giữa các vấn đề về nén và nền tảng của mật mã.

Giao thông một chiều

Mật mã hiện đại sử dụng các vấn đề tính toán khó để bảo vệ các thông điệp bí mật. Nhưng độ cứng tính toán chỉ hữu ích nếu nó không đối xứng - nếu việc giải mã các tin nhắn được mã hóa khó nhưng lại không khó để mã hóa các tin nhắn ngay từ đầu.

Trong mọi sơ đồ mật mã, nguồn gốc của sự bất đối xứng này là một đối tượng toán học được gọi là hàm một chiều, hàm này biến đổi chuỗi bit đầu vào thành chuỗi đầu ra có cùng độ dài. Với đầu vào của hàm một chiều, thật dễ dàng để tính toán đầu ra, nhưng với đầu ra thì rất khó để đảo ngược hàm - nghĩa là thiết kế ngược nó và khôi phục đầu vào.

Allender cho biết: “Các nhà mật mã học thực sự muốn có các hàm một chiều có thể tính toán rất hiệu quả và thực sự rất khó đảo ngược”. Nhiều hàm toán học dường như có đặc tính này, và khó khăn trong việc đảo ngược các hàm này xuất phát từ khó khăn rõ ràng trong việc giải các bài toán tính toán khác nhau.

Thật không may, các nhà mật mã không biết chắc chắn liệu có bất kỳ hàm nào trong số này thực sự khó đảo ngược hay không - thực tế, có thể các hàm một chiều thực sự không tồn tại. Sự không chắc chắn này vẫn tồn tại bởi vì các nhà lý thuyết phức tạp đã đấu tranh suốt 50 năm để chứng minh rằng những vấn đề tưởng chừng như khó lại thực sự khó. Nếu không, và nếu các nhà nghiên cứu khám phá ra các thuật toán siêu nhanh cho những vấn đề này, thì đó sẽ là thảm họa đối với mật mã - giống như việc đột ngột định tuyến những chiếc ô tô đang chạy quá tốc độ theo cả hai hướng trên đường một chiều.

Mặc dù sự hiểu biết toàn diện về độ cứng tính toán vẫn còn khó nắm bắt, nhưng các nhà mật mã học gần đây đã đạt được những tiến bộ thú vị hướng tới một lý thuyết thống nhất về hàm một chiều. Một bước tiến lớn đã được thực hiện vào năm 2020, khi nhà mật mã học của Đại học Tel Aviv Đèo Rafael và sinh viên tốt nghiệp của mình Yanyi Liu đã chứng minh rằng hàm một chiều là kết nối mật thiết đến một bài toán nén cụ thể được gọi là bài toán phức tạp Kolmogorov giới hạn thời gian.

Nếu một vấn đề đó thực sự khó giải quyết đối với hầu hết các đầu vào, thì kết quả của Pass và Liu mang lại một công thức về cách xây dựng hàm một chiều có thể chứng minh là khó - một hàm được đảm bảo an toàn ngay cả khi các vấn đề tính toán khác trở nên dễ dàng hơn nhiều hơn những gì các nhà nghiên cứu mong đợi. Nhưng nếu có một thuật toán nhanh để giải bài toán phức tạp Kolmogorov giới hạn thời gian thì mật mã sẽ thất bại và mọi hàm đều có thể dễ dàng đảo ngược. Hàm một chiều dựa trên độ cứng của vấn đề này là hàm an toàn nhất có thể - hàm một chiều để thống trị tất cả.

Xây dựng trên cấu trúc dữ liệu

Khám phá của Pass và Liu là chương mới nhất trong một chuỗi nghiên cứu dài sử dụng lý thuyết phức tạp để hiểu rõ hơn về nền tảng của mật mã. Nhưng nó cũng gợi ý một cách để đảo ngược mối quan hệ đó: Sự tương đương giữa bài toán độ phức tạp Kolmogorov giới hạn thời gian và phép nghịch đảo hàm số ngụ ý rằng những hiểu biết sâu sắc về một trong hai bài toán có thể tiết lộ nhiều hơn về bài toán kia. Các nhà mật mã học đã nghiên cứu các thuật toán đảo ngược hàm trong nhiều thập kỷ để hiểu rõ hơn về điểm yếu trong phương pháp mã hóa của họ. Các nhà nghiên cứu bắt đầu tự hỏi liệu những thuật toán đó có thể giúp trả lời những câu hỏi lâu đời về lý thuyết độ phức tạp hay không.

Giống như nhiều bài toán tính toán, nghịch đảo hàm có thể được giải bằng cách tìm kiếm toàn diện. Cho một chuỗi đầu ra, bạn chỉ cần cắm mọi đầu vào có thể có vào hàm cho đến khi bạn tìm thấy chuỗi mang lại câu trả lời đúng.

Năm 1980, nhà mật mã học Martin Hellman bắt đầu nghiên cứu liệu có thể làm tốt hơn nữa hay không - câu hỏi tương tự mà các nhà toán học Liên Xô đã đặt ra về các vấn đề nén hàng thập kỷ trước. người địa ngục phát hiện đúng vậy, điều đó là có thể — miễn là bạn sẵn sàng thực hiện trước một số công việc bổ sung, sử dụng các đối tượng toán học được gọi là cấu trúc dữ liệu.

Cấu trúc dữ liệu về cơ bản là một bảng lưu trữ thông tin về hàm cần đảo ngược và việc xây dựng một bảng yêu cầu tính toán kết quả đầu ra của hàm cho một số đầu vào được lựa chọn có tính chiến lược nhất định. Tất cả những tính toán đó “có thể mất một thời gian rất dài”, cho biết Ryan William, một nhà lý thuyết phức tạp tại MIT. “Nhưng ý tưởng là việc này được thực hiện một lần, một lần và mãi mãi.” Nếu bạn đang cố gắng đảo ngược cùng một chức năng với nhiều kết quả đầu ra khác nhau - chẳng hạn như để giải mã nhiều thông báo khác nhau được mã hóa theo cùng một cách - thì việc thực hiện trước công việc này có thể đáng giá.

Tất nhiên, việc lưu trữ thông tin bổ sung đó cần có dung lượng, vì vậy hãy thực hiện chiến lược này đến mức tối đa và bạn có thể kết thúc với một chương trình nhanh không thể phù hợp với bất kỳ máy tính nào. Hellman đã thiết kế một cấu trúc dữ liệu thông minh cho phép thuật toán của ông đảo ngược hầu hết các hàm nhanh hơn một chút so với tìm kiếm toàn diện mà không chiếm quá nhiều dung lượng. Sau đó vào năm 2000, các nhà mật mã Amos Fiat và Moni Naor gia tăng Lập luận của Hellman cho tất cả các chức năng.

Sau bước đột phá của Pass và Liu vào năm 2020, những kết quả cũ này đột nhiên trở nên phù hợp. Thuật toán Fiat-Naor có thể đảo ngược các hàm tùy ý nhanh hơn tìm kiếm toàn diện. Nó cũng có thể hoạt động cho các vấn đề nén?

Ngoài đồng phục

Các nhà nghiên cứu đầu tiên đặt ra câu hỏi này là nhà lý thuyết phức tạp Rahul Santhanam của Đại học Oxford và nghiên cứu sinh của ông Hàn Lâm Nhâm. Họ đã làm như vậy trong một giấy 2021 chứng minh rằng các vấn đề về nén và đảo ngược hàm thậm chí còn gắn bó với nhau nhiều hơn những gì các nhà nghiên cứu đã nhận ra.

Pass và Liu đã chứng minh rằng nếu bài toán độ phức tạp Kolmogorov giới hạn thời gian là khó thì việc đảo ngược hàm cũng phải khó và ngược lại. Nhưng các vấn đề có thể khó khăn và vẫn thừa nhận các giải pháp tốt hơn một chút so với việc tìm kiếm toàn diện. Santhanam và Ren đã chỉ ra rằng có một mối liên hệ chặt chẽ giữa việc có cần phải tìm kiếm toàn diện cho một vấn đề hay không và liệu nó có cần thiết cho vấn đề kia hay không.

Kết quả của họ có ý nghĩa khác nhau đối với hai loại thuật toán rộng rãi mà các nhà nghiên cứu thường nghiên cứu, được gọi là thuật toán “đồng nhất” và “không đồng nhất”. Các thuật toán thống nhất tuân theo cùng một quy trình cho mọi đầu vào - ví dụ: một chương trình thống nhất để sắp xếp danh sách các số sẽ hoạt động theo cùng một cách cho dù có 20 mục trong danh sách hay 20,000. Thay vào đó, các thuật toán không đồng nhất sử dụng các thủ tục khác nhau cho đầu vào có độ dài khác nhau.

Cấu trúc dữ liệu được thuật toán Fiat-Naor sử dụng luôn được điều chỉnh cho phù hợp với một chức năng cụ thể. Để đảo ngược một hàm xáo trộn chuỗi 10 bit, bạn cần một cấu trúc dữ liệu khác với cấu trúc mà bạn cần để đảo ngược một hàm xáo trộn chuỗi 20 bit, ngay cả khi việc xáo trộn được thực hiện theo cách tương tự. Điều đó làm cho Fiat-Naor trở thành một thuật toán không đồng nhất.

Kết quả của Santhanam và Ren gợi ý rằng có thể chuyển đổi thuật toán Fiat-Naor thành thuật toán để giải quyết các vấn đề nén. Nhưng việc điều chỉnh thuật toán từ vấn đề này sang vấn đề khác không hề đơn giản và họ đã không theo đuổi câu hỏi sâu hơn.

Pass nảy ra ý tưởng tương tự một năm sau đó, sau khi nghe Fiat nói chuyện về thuật toán cổ điển tại một hội thảo kỷ niệm những đóng góp của Naor cho ngành mật mã. Ông nói: “Ý tưởng sử dụng chức năng đảo ngược này đã nảy sinh trong tâm trí tôi kể từ đó. Sau đó, ông bắt đầu nghiên cứu vấn đề này một cách nghiêm túc với nhà nghiên cứu của Đại học Tel Aviv. Noam Mazor.

Trong khi đó, Ilango được truyền cảm hứng để tấn công vấn đề sau khi thảo luận với các nhà nghiên cứu khác, bao gồm cả Santhanam, trong chuyến thăm Viện Lý thuyết Máy tính Simons ở Berkeley, California. Santhanam nói: “Nó xuất phát từ một trong những cuộc trò chuyện rất tình cờ khi bạn ném mọi thứ xung quanh. Ilango sau đó gia nhập lực lượng với Williams và Hirahara Shuichi, một nhà lý thuyết phức tạp tại Viện Tin học Quốc gia ở Tokyo.

Phần khó khăn là tìm ra cách nhúng cấu trúc dữ liệu cốt lõi của thuật toán Fiat-Naor vào một thuật toán không đồng nhất để giải quyết các vấn đề nén. Có một quy trình chuẩn để thực hiện kiểu nhúng đó, nhưng nó sẽ làm chậm thuật toán, xóa sạch lợi thế của nó so với tìm kiếm toàn diện. Hai nhóm đã tìm ra những cách thông minh hơn để kết hợp cấu trúc dữ liệu Fiat-Naor và thu được các thuật toán cho các vấn đề nén hoạt động trên tất cả đầu vào và vẫn nhanh hơn tìm kiếm toàn diện.

Các chi tiết của hai thuật toán hơi khác nhau. Cách của Ilango và các đồng tác giả của anh ấy nhanh hơn tìm kiếm toàn diện ngay cả khi bạn giới hạn tìm kiếm ở những khả năng đơn giản nhất và nó áp dụng cho tất cả các vấn đề nén - độ phức tạp Kolmogorov giới hạn thời gian, vấn đề kích thước mạch tối thiểu và nhiều vấn đề khác. Nhưng ý tưởng cốt lõi của cả hai thuật toán đều giống nhau. Các kỹ thuật mã hóa đã chứng tỏ giá trị của chúng trong lĩnh vực mới này.

Hội tụ nghịch đảo

Bằng chứng mới cho các thuật toán không đồng nhất đặt ra một câu hỏi tự nhiên: Còn các thuật toán đồng nhất thì sao? Có cách nào để giải quyết vấn đề nén nhanh hơn việc tìm kiếm toàn diện bằng cách sử dụng chúng không?

Chuỗi kết quả gần đây ngụ ý rằng bất kỳ thuật toán nào như vậy sẽ tương đương với một thuật toán thống nhất để đảo ngược các hàm tùy ý – điều mà các nhà mật mã đã tìm kiếm không thành công trong nhiều thập kỷ. Vì vậy, nhiều nhà nghiên cứu nhận thấy khả năng này khó xảy ra.

“Tôi sẽ rất ngạc nhiên,” Santhanam nói. “Nó sẽ đòi hỏi một ý tưởng hoàn toàn mới.”

Nhưng Allender cho biết các nhà nghiên cứu không nên bỏ qua khả năng này. Ông nói: “Đối với tôi, một giả thuyết hữu ích là nếu có một cách không thống nhất để làm điều gì đó thì rất có thể sẽ có một cách thống nhất.

Dù sao đi nữa, công trình này đã khiến các nhà lý thuyết về độ phức tạp mới quan tâm đến những câu hỏi cũ về mật mã. Yuval Ishai, một nhà mật mã học tại Technion ở Haifa, Israel, cho biết đó là điều khiến nó trở nên thú vị nhất.

Ông nói: “Tôi thực sự vui mừng khi thấy sự hội tụ lợi ích giữa các cộng đồng khác nhau. “Tôi nghĩ nó rất tốt cho khoa học.”