Về lý thuyết, vật lý lượng tử có thể vượt qua các bài toán toán học khó là nền tảng của mã hóa hiện đại. Một bằng chứng mới cho thấy điều này như thế nào.
Các bài toán khó thường không phải là điều đáng mừng. Nhưng các nhà mật mã học lại yêu thích chúng. Đó là bởi vì những bài toán toán học khó nhất định là nền tảng cho tính bảo mật của mã hóa hiện đại. Bất kỳ thủ thuật thông minh nào để giải quyết chúng sẽ hủy diệt hầu hết các hình thức mật mã.
Vài năm trước, các nhà nghiên cứu đã tìm ra một cách tiếp cận hoàn toàn mới đối với mã hóa mà không có điểm yếu tiềm ẩn này. Cách tiếp cận này khai thác các đặc điểm kỳ lạ của vật lý lượng tử. Nhưng không giống như các sơ đồ mã hóa lượng tử trước đây, chỉ hoạt động cho một số nhiệm vụ đặc biệt, cách tiếp cận mới có thể thực hiện một loạt nhiệm vụ rộng hơn nhiều. Và nó có thể hoạt động ngay cả khi tất cả các bài toán ở trung tâm của mật mã "cổ điển" thông thường hóa ra dễ giải quyết.
Nhưng khám phá nổi bật này dựa trên các giả định không thực tế. Kết quả là "giống như một bằng chứng về khái niệm hơn," Fermi Ma, một nhà nghiên cứu mật mã tại Viện Simons về Lý thuyết Tính toán ở Berkeley, California, nói. "Đó không phải là một tuyên bố về thế giới thực."
Giờ đây, một bài báo mới của hai nhà mật mã học đã vạch ra con đường đến mật mã lượng tử mà không có những giả định kỳ quặc đó. "Bài báo này đang nói rằng nếu một số phỏng đoán khác là đúng, thì mật mã lượng tử phải tồn tại," Ma nói.
Lâu Đài Trên Trời
Bạn có thể nghĩ về mật mã hiện đại như một tòa tháp với ba phần thiết yếu. Phần đầu tiên là nền tảng sâu bên dưới tòa tháp, được tạo thành từ các bài toán toán học khó. Bản thân tòa tháp là phần thứ hai—ở đó bạn có thể tìm thấy các giao thức mật mã cụ thể cho phép bạn gửi tin nhắn riêng tư, ký tài liệu kỹ thuật số, bỏ phiếu bí mật và hơn thế nữa.
Ở giữa, bảo mật các ứng dụng hàng ngày đó với nền tảng toán học, là một móng được tạo thành từ các khối xây dựng gọi là hàm một chiều. Chúng chịu tr책nhiệm cho tính bất đối xứng vốn có trong bất kỳ sơ đồ mã hóa nào. "Nó là một chiều vì bạn có thể mã hóa tin nhắn, nhưng bạn không thể giải mã chúng," Mark Zhandry, một nhà mật mã học tại NTT Research, nói.
Trong những năm 1980, các nhà nghiên cứu đã chứng minh rằng mật mã được xây dựng trên các hàm một chiều sẽ đảm bảo bảo mật cho nhiều nhiệm vụ khác nhau. Nhưng hàng thập kỷ sau đó, họ vẫn không chắc chắn rằng nền tảng đủ mạnh để hỗ trợ nó. Vấn đề là nền tảng được tạo thành từ các bài toán khó đặc biệt—được biết đến về mặt kỹ thuật là các bài toán NP—có đặc điểm xác định là dễ kiểm tra xem bất kỳ giải pháp ứng viên nào có đúng không. (Ví dụ, phân tích một số thành các thừa số nguyên tố là một bài toán NP: khó thực hiện đối với các số lớn, nhưng dễ kiểm tra.)
Nhiều bài toán này có vẻ khó khăn về bản chất, nhưng các nhà khoa học máy tính đã không thể chứng minh điều đó. Nếu ai đó khám phá ra một thuật toán tài tình để nhanh chóng giải quyết các bài toán NP khó nhất, nền tảng sẽ sụp đổ, và toàn bộ tòa tháp sẽ sập.
Thật không may, bạn không thể đơn giản di chuyển tòa tháp của mình đến nơi khác. Móng của tòa tháp—các hàm một chiều—chỉ có thể đứng trên nền tảng của các bài toán NP.
Để xây dựng một tòa tháp trên các bài toán khó hơn, các nhà mật mã học sẽ cần một móng mới không được tạo thành từ các hàm một chiều. Điều đó có vẻ không thể cho đến chỉ vài năm trước, khi các nhà nghiên cứu nhận ra rằng vật lý lượng tử có thể giúp ích.
Nó bắt đầu với một bài báo năm 2021 của một sinh viên tốt nghiệp tên William Kretschmer đã thu hút sự chú ý đến một bài toán kỳ lạ về các thuộc tính của hệ thống lượng tử. Các nhà nghiên cứu sớm cho thấy rằng bài toán của Kretschmer có thể thay thế các hàm một chiều làm nền tảng cho một tòa tháp mới của các giao thức mật mã. Năm sau, Kretschmer và những người khác đã chứng minh rằng cách tiếp cận thay thế này có thể hoạt động ngay cả không có các bài toán NP khó. Đột nhiên, có vẻ như có thể xây dựng một pháo đài mật mã sẽ vững chắc hơn nhiều.
Nhưng xây dựng nó ở đâu? Bài toán lượng tử mà Kretschmer sử dụng làm nền tảng của mình liên quan đến các thiết bị tính toán giả định gọi là oracle có thể ngay lập tức trả lời các câu hỏi cụ thể. Oracle có thể là những công cụ lý thuyết hữu ích, nhưng chúng không thực sự tồn tại. Các bằng chứng của Kretschmer giống như một bản thiết kế để xây dựng một lâu đài trên trời. Có cách nào để đưa nó xuống đất không?
Nền Tảng Thứ Hai
Vào mùa thu năm 2022, câu hỏi đó đã thu hút sự chú ý của Dakshita Khurana, một nhà mật mã học tại Đại học Illinois tại Urbana-Champaign và NTT Research. Khurana và sinh viên tốt nghiệp của cô, Kabir Tomer, đã bắt tay vào xây dựng một tòa tháp mật mã mới. Bước đầu tiên của cô là xây dựng một nền tảng mới sử dụng các khối xây dựng lượng tử thay vì các hàm một chiều cổ điển. Sau đó cô sẽ cần chứng minh rằng nền tảng mới này có thể hỗ trợ một tòa tháp của các giao thức mật mã khác. Khi cô chứng minh được rằng nền tảng có thể hỗ trợ tòa tháp, cô sẽ phải tìm một nơi vững chắc cho toàn bộ công trình—một nền tảng của các bài toán thế giới thực có vẻ thậm chí còn khó hơn các bài toán NP được sử dụng trong mật mã cổ điển.
Đối với bước đầu tiên, Khurana và Tomer tập trung vào phiên bản lượng tử của hàm một chiều, được gọi là bộ tạo trạng thái một chiều, thỏa mãn ba thuộc tính làm cho các hàm một chiều hữu ích. Đầu tiên, hàm phải chạy nhanh để bạn có thể dễ dàng tạo ra một khóa mật mã và khóa tương ứng để mở nó cho mỗi tin nhắn bạn muốn gửi. Thứ hai, mỗi khóa phải an toàn, đòi hỏi nỗ lực lớn để phá vỡ mà không có chìa khóa đúng. Cuối cùng, mọi khóa phải dễ mở bằng chìa khóa đúng.
Sự khác biệt quan trọng nằm ở bản chất của các khóa. Các hàm một chiều cổ điển tạo ra các khóa toán học được tạo thành từ bit—các số 0 và 1 lưu trữ thông tin trong máy tính cổ điển. Các bộ tạo trạng thái một chiều lượng tử thay vào đó sẽ tạo ra các khóa được tạo thành từ các đơn vị thông tin lượng tử gọi là qubit. Những khóa lượng tử này có thể vẫn an toàn ngay cả khi tất cả các khóa cổ điển đều dễ phá vỡ. Khurana và Tomer hy vọng bắt đầu với nền tảng lượng tử mới này và xây dựng một tòa tháp các giao thức mật mã trên đó. "Điều này hóa ra khá khó," Khurana nói. "Chúng tôi đã bị mắc kẹt trong nhiều, nhiều tháng."
"Chúng tôi chỉ đang cố gắng hiểu cảnh quan mới này." - Mark Zhandry
Đến tháng 7 năm 2023, Khurana đã gần chín tháng mang thai và đang lên kế hoạch nghỉ phép chăm sóc con. Tomer đã hết ý tưởng. "Tôi bi quan hơn Dakshita nhiều," anh nói. "Cô ấy luôn là người tin rằng mọi thứ sẽ ổn."
Sau đó họ đã có một bước đột phá. Bước quan trọng là định nghĩa một khối xây dựng toán học khác phục vụ như một tầng hầm: một cấu trúc sẽ kết nối nền tảng của các bộ tạo trạng thái một chiều với một tòa tháp các giao thức mật mã. Khi Khurana và Tomer tìm ra những thuộc tính mà khối xây dựng đó cần có, họ thấy rằng nó giống một hàm một chiều với một hỗn hợp khó hiểu của các đặc tính lượng tử và cổ điển. Như trong một hàm một chiều thông thường, cả khóa và chìa khóa đều được tạo thành từ bit cổ điển, nhưng quy trình tạo ra những khóa và chìa khóa này sẽ chỉ chạy trên máy tính lượng tử. Còn kỳ lạ hơn, khối xây dựng mới thỏa mãn hai thuộc tính xác định đầu tiên của các hàm một chiều, nhưng không phải thuộc tính thứ ba: Dễ tạo ra khóa và chìa khóa, và mọi khóa đều khó phá vỡ. Nhưng một chìa khóa sẽ không dễ dàng mở khóa của nó.
Khurana và Tomer đặt tên cho những khối xây dựng mới khó hiểu này là các câu đố một chiều. Theo trực giác, khó tưởng tượng chúng có thể hữu ích như thế nào: Một chìa khóa mà bạn không bao giờ có thể sử dụng có ích gì? Nhưng hai nhà mật mã học đã chỉ ra rằng các câu đố một chiều kết hợp với các thủ thuật lượng tử khác thực sự sẽ cho phép nhiều giao thức mật mã. Nếu bạn có thể tạo ra các khóa và chìa khóa phù hợp với nhau về nguyên tắc, không quan trọng liệu quy trình mở khóa có cực kỳ không hiệu quả.
"Chỉ cần biết rằng tồn tại một thuật toán nào đó có thể chậm tùy ý là đủ," Kretschmer, hiện là nhà nghiên cứu tại Viện Simons, nói. "Điều đó rất đáng ngạc nhiên."
Với mảnh ghép còn thiếu đó, họ nhanh chóng hoàn thành bằng chứng vào ngày 4 tháng 8. Con gái của Khurana được sinh chỉ vài ngày sau đó.
Hồ Sơ Vĩnh Viễn
Đến tháng 11, Khurana đã trở lại làm việc và sẵn sàng thử giai đoạn thứ hai của kế hoạch. Cô và Tomer đã chỉ ra rằng nhiều loại mật mã có thể được xây dựng trên các câu đố một chiều, và các câu đố một chiều lần lượt có thể được xây dựng trên một nền tảng lượng tử mới được tạo thành từ các bộ tạo trạng thái một chiều. Bước tiếp theo trong kế hoạch ban đầu của họ là kết nối nền tảng lượng tử đó với một nền tảng mới—một tập hợp tương đối không thể tấn công của các bài toán toán học thậm chí còn khó giải quyết hơn những bài toán trong NP.
Nhưng khi Khurana và Tomer vật lộn với nhiệm vụ đó, họ quyết định áp dụng một cách tiếp cận trực tiếp hơn: Quên đi các bộ tạo trạng thái một chiều, và thay vào đó neo các câu đố một chiều trực tiếp vào nền tảng toán học.
Từ một góc độ, điều đó có vẻ như một lựa chọn kỳ lạ. Các câu đố một chiều là những điều kỳ quặc toán học mà Khurana và Tomer đã sử dụng trong một bước trung gian của bằng chứng của họ.
Tuy nhiên, các câu đố một chiều có một số ưu điểm. Một điều là, mặc dù chúng là lượng tử, các khóa và chìa khóa mà chúng tạo ra là cổ điển. Khurana nghĩ rằng điều đó có thể làm cho việc kết nối chúng với nền tảng toán học cổ điển dễ dàng hơn. Ngoài ra, các câu đố một chiều tạo ra các chìa khóa quá cồng kềnh để thực sự mở khóa. Điều đó có thể làm cho việc liên kết chúng với các bài toán quá phức tạp đến mức ngay cả việc kiểm tra giải pháp cũng có vẻ vô vọng.
Nhưng những bài toán cụ thể nào sẽ hoạt động? Khurana có một ứng viên trong đầu: tính toán một kết hợp cụ thể của các mục trong một bảng số gọi là ma trận. Bài toán này, được biết đến là bài toán định thức vĩnh viễn ma trận, nổi tiếng khó giải quyết đối với các ma trận lớn, và không có cách đơn giản nào để kiểm tra xem một phép tính có đúng không. Bài toán định thức vĩnh viễn ma trận cũng có các thuộc tính toán học đặc biệt khác mà các nhà mật mã học thấy hấp dẫn.
"Đây sẽ là một bài toán đẹp để dựa mật mã vào," Khurana nói.
Bài toán định thức vĩnh viễn ma trận cũng kết nối với một bài toán khác mà máy tính lượng tử có thể dễ dàng giải quyết nhưng máy tính cổ điển dường như không thể. Các nhà nghiên cứu đang làm việc để chứng minh lợi thế tính toán lượng tử này theo nghĩa lý thuyết chính xác. Khurana và Tomer đã chỉ ra rằng một bằng chứng như vậy cũng sẽ cho phép họ xây dựng các câu đố một chiều an toàn—và do đó toàn bộ tòa tháp mật mã lượng tử—trên đỉnh bài toán vĩnh viễn.
"Họ đã có thể làm điều này từ những giả định được nghiên cứu kỹ lưỡng này," Kretschmer nói. "Tôi thực sự vui mừng khi thấy điều đó."
Với kết quả mới của họ, Khurana và Tomer đã hiệu quả giảm hai bài toán mở thành một. Nếu các nhà nghiên cứu hoàn thành bằng chứng rằng máy tính lượng tử thực sự vượt trội hơn máy tính cổ điển trong một nhiệm vụ cụ thể, điều đó sẽ tự động đặt mật mã lượng tử trên nền tảng lý thuyết mạnh mẽ hơn nhiều so với hầu như bất kỳ loại mật mã cổ điển nào.
Than ôi, bạn sẽ không thể sử dụng cách tiếp cận mới của Khurana và Tomer để gửi tin nhắn bí mật trong thời gian sớm. Mặc dù có tiến bộ gần đây, công nghệ tính toán lượng tử vẫn chưa đủ trưởng thành để đưa ý tưởng của họ vào thực tế. Trong khi đó, các nhà nghiên cứu khác đã nghĩ ra các phương pháp mật mã lượng tử có thể được sử dụng sớm hơn, mặc dù cần thêm công việc để thiết lập rằng chúng thực sự an toàn.
Mật mã lượng tử đã chứng minh đầy bất ngờ, và các nhà nghiên cứu chỉ mới bắt đầu khám phá các khả năng. "Chúng tôi chỉ đang cố gắng hiểu cảnh quan mới này thực sự đã tồn tại từ trước," Zhandry nói.
