Hãy tưởng tượng bạn đã có một số kiến thức hữu ích - có thể là một công thức bí mật hoặc chìa khóa của mật mã. Bạn có thể chứng minh với một người bạn rằng bạn có kiến thức đó mà không tiết lộ bất cứ điều gì về nó không? Các nhà khoa học máy tính đã chứng minh hơn 30 năm trước rằng bạn có thể, nếu bạn sử dụng cái được gọi là bằng chứng không kiến thức.
Để hiểu một cách đơn giản về ý tưởng này, giả sử bạn muốn cho bạn bè của mình biết rằng bạn biết cách vượt qua mê cung mà không cần tiết lộ bất kỳ chi tiết nào về con đường. Bạn có thể đơn giản đi qua mê cung trong một giới hạn thời gian, trong khi bạn của bạn bị cấm xem. (Giới hạn thời gian là cần thiết vì có đủ thời gian, cuối cùng ai cũng có thể tìm ra lối thoát cho mình thông qua thử và sai.) Bạn của bạn sẽ biết bạn có thể làm điều đó, nhưng họ sẽ không biết làm thế nào.
Các bằng chứng không có kiến thức rất hữu ích cho các nhà mật mã, những người làm việc với thông tin bí mật, nhưng cũng cho các nhà nghiên cứu về độ phức tạp tính toán, giải quyết việc phân loại độ khó của các vấn đề khác nhau. “Rất nhiều mật mã hiện đại dựa trên các giả định về độ phức tạp - dựa trên giả định rằng một số vấn đề nhất định khó giải quyết, vì vậy luôn có một số kết nối giữa hai thế giới,” nói Claude Crépeau, một nhà khoa học máy tính tại Đại học McGill. “Nhưng [những] bằng chứng này đã tạo ra cả một thế giới kết nối.”
Các bằng chứng không có kiến thức thuộc về một danh mục được gọi là các bằng chứng tương tác, vì vậy để tìm hiểu cách thức hoạt động của công việc trước đây, bạn cần hiểu rõ về cách thức sau. Ngày thứ nhất mô tả trong một bài báo năm 1985 của các nhà khoa học máy tính Shafi Goldwasser, Silvio Micali và Charles Rackoff, các bằng chứng tương tác hoạt động giống như một cuộc thẩm vấn: Qua một loạt các thông điệp, một bên (phương ngôn) cố gắng thuyết phục bên kia (người xác minh) rằng một tuyên bố nhất định là đúng. Một bằng chứng tương tác phải thỏa mãn hai thuộc tính. Đầu tiên, một tuyên bố đúng cuối cùng sẽ luôn thuyết phục được người xác minh trung thực. Thứ hai, nếu tuyên bố đã cho là sai, thì không một câu châm ngôn nào - ngay cả một người giả vờ sở hữu một số kiến thức nhất định - có thể thuyết phục người xác minh, ngoại trừ với xác suất nhỏ không đáng kể.
Các chứng minh tương tác có tính chất xác suất. Câu tục ngữ có thể trả lời chính xác một hoặc hai câu hỏi chỉ đơn giản là do may mắn, vì vậy cần một số lượng lớn thử thách, tất cả những thử thách này đều phải đúng, để người xác minh tin tưởng rằng câu tục ngữ trên thực tế biết câu nói đó là đúng.
Ý tưởng về sự tương tác này xuất hiện khi Micali và Goldwasser - khi đó là sinh viên tốt nghiệp tại Đại học California, Berkeley - phân vân về hậu cần của việc chơi poker qua mạng. Làm thế nào để tất cả người chơi có thể xác minh rằng khi một trong số họ nhận được một lá bài từ bộ bài ảo, kết quả là ngẫu nhiên? Các bằng chứng tương tác có thể dẫn đầu. Nhưng sau đó, làm thế nào người chơi có thể xác minh rằng toàn bộ giao thức - bộ quy tắc đầy đủ - đã được tuân thủ một cách chính xác, mà không để lộ mọi bàn tay của người chơi trên đường đi?
Để đạt được mục tiêu này, Micali và Goldwasser đã thêm thuộc tính thứ ba vào hai tính chất cần thiết cho một bằng chứng tương tác: Bằng chứng không nên tiết lộ gì về bản thân kiến thức, chỉ có tính trung thực của tuyên bố. Goldwasser nói: “Có một khái niệm về việc đi qua một giao thức, khi kết thúc giao thức đó, bạn tin rằng [những người chơi poker] không biết gì nhiều hơn những gì họ phải biết.
Hãy xem xét ví dụ cổ điển. Alice muốn chứng minh với Bob rằng một biểu đồ nhất định G - một tập hợp các đỉnh (chấm) duy nhất được nối với nhau bởi các cạnh (đường) - có “chu trình Hamilton”. Điều này có nghĩa là biểu đồ có một đường dẫn đến mỗi điểm chính xác một lần và kết thúc tại cùng một điểm mà nó bắt đầu. Alice có thể làm điều này bằng cách chỉ cho Bob thấy con đường thực hiện điều này, nhưng tất nhiên sau đó anh ấy cũng sẽ biết đường đi.
Đây là cách Alice có thể thuyết phục Bob rằng cô ấy biết một con đường như vậy tồn tại mà không cần cho anh ta thấy. Đầu tiên, cô ấy vẽ một biểu đồ mới, H, trông không giống G nhưng giống nhau ở một điểm cốt yếu: Nó có cùng số đỉnh, được nối theo những cách giống nhau. (Nếu G thực sự có một chu trình Hamilton, sự tương tự này có nghĩa là H cũng vậy.) Sau đó, sau khi che mọi cạnh trong H với băng che mặt, cô ấy khóa H trong một chiếc hộp và đưa chiếc hộp cho Bob. Điều này ngăn anh ta nhìn thấy nó trực tiếp nhưng cũng ngăn cản cô ấy thay đổi nó. Sau đó, Bob đưa ra lựa chọn: Hoặc anh ấy có thể yêu cầu Alice cho xem H thực sự tương tự như Ghoặc anh ấy có thể yêu cầu cô ấy chỉ cho anh ấy chu trình Hamilton trong H. Cả hai yêu cầu đều dễ dàng đối với Alice, giả sử rằng H thực sự là đủ tương tự như G, và rằng cô ấy thực sự biết con đường.
Tất nhiên, ngay cả khi Alice không biết chu trình Hamilton trong G, cô ấy có thể cố gắng đánh lừa Bob, bằng cách vẽ các biểu đồ không tương tự như Ghoặc bằng cách gửi biểu đồ mà cô ấy không biết đường dẫn. Nhưng sau khi họ đã chơi nhiều vòng, khả năng Alice lừa được Bob mỗi lần đều trở nên nhỏ bé. Nếu cô ấy làm đúng mọi thứ, cuối cùng Bob sẽ tin rằng Alice biết một chu trình Hamilton trong đồ thị G, mà không bao giờ Bob nhìn thấy nó.
Sau bài báo đầu tiên mô tả những cách chứng minh như vậy, Micali và hai nhà toán học - Oded Goldreich và Avi Wigderson - đã phát hiện ra một hệ quả bất ngờ với những ảnh hưởng sâu rộng. Nó liên quan đến một loại bài toán chính có độ khó tương đương, được gọi là NP. Những vấn đề này khó giải quyết, nhưng giải pháp của chúng rất dễ kiểm chứng. Ba nhà nghiên cứu thấy rằng, nếu mã hóa thực sự an toàn có khả năng, thì lời giải cho mọi vấn đề trong NP cũng có thể được chứng minh bằng một chứng minh không có kiến thức. Nghiên cứu này đã giúp các nhà nghiên cứu quan niệm về các biến thể của bằng chứng không có kiến thức thậm chí không yêu cầu mã hóa an toàn ngay từ đầu; chúng được gọi là bằng chứng tương tác đa phương ngữ.
Và vào năm 1988, Micali và những người khác cho thấy rằng nếu một câu châm ngôn và một người xác minh chia sẻ một chuỗi ngắn gồm các bit ngẫu nhiên, thì không cần tương tác. Điều này về mặt lý thuyết có nghĩa là các bằng chứng không có kiến thức không cần phải tương tác, điều này có nghĩa là không cần thiết phải liên lạc liên tục giữa hai bên. Điều này sẽ khiến chúng trở nên hữu ích hơn nhiều đối với các nhà nghiên cứu, nhưng phải đến sau khi bước sang thế kỷ 21, những bằng chứng như vậy mới có hiệu quả.
“Vào cuối những năm 2000, chúng tôi bắt đầu thấy sự phát triển của các kỹ thuật hiệu quả để xây dựng các bằng chứng về kiến thức không”, Matthew D. Xanh, một nhà mật mã học tại Đại học John Hopkins. “Chúng tôi đã đến thời điểm mà chúng tôi nhận ra, 'Chờ một chút, thực sự có thể có một cách để sử dụng điều này trong thực tế.'
Giờ đây, một câu châm ngôn có thể gửi một thông điệp tới người xác minh mà không cần cả hai người trên mạng và các nhà nghiên cứu có thể tạo ra một bằng chứng rất ngắn có thể nhanh chóng được xác minh, ngay cả đối với những vấn đề rất phức tạp. Điều này đã dẫn đến một số ứng dụng thực tế, chẳng hạn như khả năng nhanh chóng xác minh blockchain sau một giao dịch tiền điện tử trong khi ẩn các chi tiết của giao dịch. Và vào năm 2016, một nhóm các nhà vật lý cho thấy Làm thế nào mà các bằng chứng không có kiến thức có thể giúp giải trừ hạt nhân: Không cần tiết lộ bất kỳ bí mật nào về thiết kế đầu đạn hạt nhân của mình, một quốc gia giờ đây có thể chứng minh cho các thanh sát viên hạt nhân xem đầu đạn đang hoạt động hay không hoạt động.
Gần đây hơn, những tiến bộ trong tính toán lượng tử đã buộc Crépeau phải kiểm tra lại những nghiên cứu trong quá khứ để đảm bảo rằng các giao thức không có kiến thức vẫn còn khả thi. Vào năm 2021, anh ấy đã giúp chứng minh rằng các bằng chứng tương tác đa phương thức vẫn giữ được bí mật của chúng ngay cả khi có sự tham gia của máy tính lượng tử, nhưng việc đạt được mức độ bảo mật tương tự khiến giao thức chậm hơn nhiều. Ông nói, phát hiện này là một tin tốt, nhưng những lo ngại mới sẽ nảy sinh khi công nghệ tiến bộ.
Crépeau nói: “Mọi loại tính toán mà chúng ta có thể thực hiện trong tương lai sẽ liên quan đến máy tính lượng tử. “Vì vậy, là những nhà mật mã học hoang tưởng giỏi, bất cứ khi nào chúng tôi đánh giá tính bảo mật của một hệ thống, chúng tôi muốn đảm bảo rằng hệ thống của chúng tôi an toàn”.
Ghi chú của biên tập viên: Shafi Goldwasser đã nhận được tài trợ từ Quỹ Simons, tổ chức này cũng tài trợ cho việc này xuất bản độc lập về mặt biên tập. Các quyết định tài trợ của Simons Foundation không ảnh hưởng đến phạm vi bảo hiểm của chúng tôi.
