Các Nhà Khoa Học Đạt Được 'Viên Ngọc Quý' của Mật Mã Học

Năm 2018, Aayush Jain, một sinh viên sau đại học tại Đại học California, Los Angeles, đã đến Nhật Bản để trình bày về một công cụ mật mã mạnh mẽ mà anh và đồng nghiệp đang phát triển. Khi anh ta mô tả cách tiếp cận của đội ngũ đối với che giấu không phân biệt (gọi là iO), một người trong khán giả giơ tay với vẻ bối rối.

“Nhưng tôi nghĩ rằng iO không tồn tại, phải không?” anh ta nói.

Vào thời điểm đó, sự hoài nghi như vậy lan rộng. Nếu có thể xây dựng che giấu không phân biệt, nó sẽ có khả năng ẩn không chỉ bộ sưu tập dữ liệu mà còn là cấu trúc bên trong của chính một chương trình máy tính, tạo ra một loại công cụ mật mã chủ chốt từ đó gần như mọi giao thức mật mã khác có thể được xây dựng. Đó là 'một nguyên tắc mật mã để kiểm soát tất cả', như Boaz Barak của Đại học Harvard nói. Nhưng với nhiều nhà khoa học máy tính, sức mạnh này làm cho iO trở nên quá tốt để làm đúng.

Những nhà khoa học máy tính đưa ra các phiên bản ứng cử của iO bắt đầu từ năm 2013. Nhưng sự hứng thú mãnh liệt mà những công trình này tạo ra dần dần giảm bớt, khi những nghiên cứu khác tìm ra cách phá vỡ tính bảo mật của chúng. Khi những cuộc tấn công ngày càng gia tăng, “bạn có thể nhìn thấy nhiều cảm giác tiêu cực,” Yuval Ishai của Viện Công nghệ Technion ở Haifa, Israel nói. Các nhà nghiên cứu tự hỏi, ông nói, “Ai sẽ chiến thắng: người làm hay người phá?”

“Có những người là fanatics, và họ tin tưởng vào [iO] và tiếp tục làm việc trên nó,” Shafi Goldwasser, giám đốc Viện Simons về Lý thuyết Tính toán tại Đại học California, Berkeley nói. Nhưng theo thời gian trôi qua, bà nói, “càng ngày càng ít những người đó.”

Bây giờ, Jain—cùng với Huijia Lin của Đại học Washington và Amit Sahai, người hướng dẫn của Jain tại UCLA—đã đặt một lá cờ cho những người làm. Trong một bài báo được đăng trực tuyến vào ngày 18 tháng 8, ba nhà nghiên cứu đã cho thấy lần đầu tiên cách xây dựng che giấu không phân biệt bằng cách sử dụng chỉ các giả định bảo mật 'tiêu chuẩn'.

Tất cả các giao thức mật mã đều dựa trên giả định—một số, như thuật toán RSA nổi tiếng, phụ thuộc vào niềm tin phổ biến rằng máy tính tiêu chuẩn sẽ không bao giờ có khả năng phân tích nhanh chóng tích của hai số nguyên tố lớn. Một giao thức mật mã chỉ an toàn khi giả định của nó an toàn, và các thử nghiệm trước đây về iO được xây dựng trên các nền tảng chưa được kiểm tra và cuối cùng là không chắc chắn. Ngược lại, giao thức mới này phụ thuộc vào giả định bảo mật đã được sử dụng và nghiên cứu rộng rãi trong quá khứ.

“Trừ khi có một phát triển thực sự đáng kinh ngạc, những giả định này sẽ đứng vững,” Ishai nói.

Mặc dù giao thức này còn rất xa mới sẵn sàng triển khai trong các ứng dụng thực tế, từ góc độ lý thuyết, nó cung cấp một cách tức thì để xây dựng một loạt các công cụ mật mã trước đây là không thể. Ví dụ, nó cho phép tạo ra mã hóa “phủ nhận,” trong đó bạn có thể thuyết phục một kẻ tấn công rằng bạn đã gửi một thông điệp hoàn toàn khác với thông điệp thực sự bạn đã gửi, và mã hóa “chức năng,” trong đó bạn có thể cung cấp cho người dùng được chọn các cấp độ truy cập khác nhau để thực hiện tính toán bằng cách sử dụng dữ liệu của bạn.

Kết quả mới này chắc chắn sẽ làm im lặng những người hoài nghi về iO, Ishai nói. “Bây giờ sẽ không còn nghi ngờ nào về sự tồn tại của che giấu không phân biệt,” ông nói. “Đó là một kết thúc hạnh phúc.”

Viên Ngọc Quý

Trong nhiều thập kỷ, các nhà khoa học máy tính tự hỏi liệu có cách nào an toàn và toàn diện để làm mờ chương trình máy tính, cho phép người ta sử dụng chúng mà không cần phải tìm hiểu về những bí mật bên trong. Việc làm mờ chương trình sẽ cho phép một loạt các ứng dụng hữu ích: Ví dụ, bạn có thể sử dụng một chương trình đã được làm mờ để ủy quyền các nhiệm vụ cụ thể trong tài khoản ngân hàng hoặc email của bạn cho những người khác mà không lo lắng rằng ai đó có thể sử dụng chương trình theo cách không được dự định hoặc đọc mật khẩu tài khoản của bạn (trừ khi chương trình được thiết kế để xuất chúng).

Nhưng cho đến nay, mọi nỗ lực để xây dựng các công cụ làm mờ thực tế đều thất bại. “Những cái xuất hiện trong đời thực thường là hoàn toàn bị hỏng, ... thường là trong vài giờ sau khi được phát hành ra môi trường tự nhiên,” Sahai nói. Ở mức tốt nhất, chúng chỉ tạo ra một tốc độ trở ngại cho kẻ tấn công, ông nói.

Năm 2001, tin xấu đến cả từ mặt lý thuyết: Hình thức mạnh nhất của làm mờ là không thể. Gọi là làm mờ hộp đen, nó đòi hỏi rằng kẻ tấn công phải có khả năng học được hoàn toàn không có thông tin gì về chương trình ngoại trừ những gì họ có thể quan sát bằng cách sử dụng chương trình và xem xét những gì nó xuất ra. Một số chương trình, Barak, Sahai và năm nhà nghiên cứu khác đã chỉ ra, tiết lộ bí mật của họ một cách quyết liệt đến mức không thể làm mờ hoàn toàn.

Những chương trình này, tuy nhiên, được tạo ra đặc biệt để thách thức sự làm mờ và ít giống với các chương trình thực tế. Vì vậy, các nhà khoa học máy tính hy vọng có thể có một loại làm mờ khác mà yếu đủ để khả thi nhưng mạnh mẽ đủ để che giấu những bí mật mà mọi người thực sự quan tâm. Các nhà nghiên cứu cùng một nhóm đã chỉ ra rằng làm mờ hộp đen là không thể đã đề xuất một lựa chọn khả dĩ trong bài báo của họ: che giấu không phân biệt.

Trên bề mặt, iO dường như không phải là một khái niệm đặc biệt hữu ích. Thay vì yêu cầu rằng bí mật của một chương trình được giấu, nó chỉ đơn giản yêu cầu rằng chương trình được làm mờ đủ nhiều để nếu bạn có hai chương trình khác nhau thực hiện cùng một nhiệm vụ, bạn không thể phân biệt được phiên bản làm mờ nào đến từ phiên bản gốc nào.

Nhưng iO mạnh mẽ hơn so với âm thanh của nó. Ví dụ, giả sử bạn có một chương trình thực hiện một số nhiệm vụ liên quan đến tài khoản ngân hàng của bạn, nhưng chương trình chứa mật khẩu không mã hóa của bạn, khiến bạn trở nên dễ bị tổn thương đối với bất kỳ ai có chương trình đó. Sau đó—miễn là có một chương trình nào đó có thể thực hiện cùng một nhiệm vụ trong khi giữ mật khẩu của bạn được giấu kín—một máy che giấu không phân biệt sẽ mạnh mẽ đủ để thành công che giấu mật khẩu. Sau cùng, nếu nó không làm điều đó, thì nếu bạn đưa cả hai chương trình qua máy che giấu, bạn sẽ có thể nói được phiên bản làm mờ nào đến từ chương trình gốc của bạn.

Qua nhiều năm, các nhà khoa học máy tính đã chứng minh rằng bạn có thể sử dụng iO làm cơ sở cho hầu hết mọi giao thức mật mã bạn có thể tưởng tượng (trừ làm mờ hộp đen). Điều đó bao gồm cả các nhiệm vụ mật mã cổ điển như mã hóa khóa công khai (được sử dụng trong giao dịch trực tuyến) và những cái mới lòe loẹt như mã hóa homomorphic đầy đủ, trong đó máy tính đám mây có thể tính toán trên dữ liệu được mã hóa mà không học bất cứ điều gì về nó. Và nó bao gồm các giao thức mật mã mà không ai biết cách xây dựng, như mã hóa phủ nhận hoặc chức năng.

“Nó thực sự là loại ngọc quý” của các giao thức mật mã, theo lời của Rafael Pass từ Đại học Cornell. “Khi bạn đạt được điều này, chúng ta có thể đạt được về cơ bản mọi thứ.”

Năm 2013, Sahai và năm đồng tác giả đề xuất một giao thức iO chia chương trình thành những mảnh như mảnh ghép hình, sau đó sử dụng các đối tượng mật mã gọi là bản đồ đa tuyến để làm rối tung các mảnh cá thể. Nếu các mảnh được ghép đúng, quá trình làm rối sẽ bị hủy và chương trình sẽ hoạt động như ý, nhưng mỗi mảnh cá thể trông không có ý nghĩa. Kết quả này đã được ca ngợi như một bước đột phá và kích thích hàng chục bài báo theo dõi. Nhưng trong vài năm, các nhà nghiên cứu khác đã chỉ ra rằng các bản đồ đa tuyến được sử dụng trong quá trình làm rối không an toàn. Các ứng cử viên iO khác xuất hiện và lần lượt bị phá vỡ.

“Có một số lo ngại rằng có lẽ đây chỉ là một ảo ảnh, có lẽ iO đơn giản là không thể có được,” Barak nói. Người ta bắt đầu cảm thấy, ông nói, rằng “có lẽ toàn bộ dự án này đều định mệnh.”

Che Đi Ít Hơn để Che Nhiều Hơn

Năm 2016, Lin bắt đầu khám phá xem có thể có cách nào để vượt qua nhược điểm của bản đồ đa tuyến bằng cách đơn giản là đòi hỏi ít hơn từ chúng. Bản đồ đa tuyến về cơ bản chỉ là cách bí mật để tính toán với đa thức—biểu thức toán học được tạo ra từ tổng và tích của các số và biến số, như 3xy + 2yz². Những bản đồ này, Jain nói, đòi hỏi một cái gì đó giống như một máy tính tính toán đa thức được kết nối với một hệ thống các tủ khoá bí mật chứa giá trị của các biến số. Người dùng nếu đưa vào một đa thức mà máy chấp nhận được thì được xem vào một tủ khoá cuối cùng để xem liệu giá trị ẩn có làm cho đa thức đánh giá thành 0 hay không.

Đối với kế hoạch này là an toàn, người dùng không nên có khả năng tìm hiểu bất cứ điều gì về nội dung của các tủ khoá khác hoặc các số đã được tạo ra trong quá trình tính toán. “Chúng tôi muốn điều đó là đúng,” Sahai nói. Nhưng trong tất cả các bản đồ đa tuyến ứng viên mà mọi người có thể nghĩ ra, quá trình mở tủ khoá cuối cùng lại làm lộ thông tin về phép tính mà nó nên được giấu kín.

Vì tất cả các bản đồ máy tính đa tuyến đều có nhược điểm về an ninh, Lin tự hỏi liệu có cách nào để xây dựng iO bằng cách sử dụng các máy tính không cần phải tính toán nhiều loại đa thức khác nhau (và do đó có thể dễ dàng xây dựng an toàn hơn). Bốn năm trước, cô ấy đã tìm ra cách xây dựng iO chỉ bằng cách sử dụng các bản đồ đa tuyến tính toán các đa thức có “bậc” là 30 hoặc ít hơn (nghĩa là mỗi thuật ngữ là một tích của tối đa 30 biến số, đếm cả các biến số lặp lại). Trong vài năm tiếp theo, cô ấy, Sahai và các nhà nghiên cứu khác dần dần tìm ra cách hạ bậc xuống thấp hơn, cho đến khi họ có thể chỉ ra cách xây dựng iO chỉ bằng cách sử dụng bản đồ đa tuyến bậc 3.

Trên giấy tờ, nó trông như một cải thiện lớn. Chỉ có một vấn đề: Từ góc độ an ninh, “bậc 3 thực sự cũng bị hỏng” như những chiếc máy có thể xử lý đa thức của mọi bậc, Jain nói.

Những bản đồ đa tuyến duy nhất mà các nhà nghiên cứu biết cách xây dựng một cách an toàn là những bản đồ tính toán đa thức có bậc 2 hoặc thấp hơn. Lin hợp tác với Jain và Sahai để cố gắng tìm hiểu cách xây dựng iO từ các bản đồ đa tuyến bậc 2. Nhưng “chúng tôi bị mắc kẹt trong một khoảng thời gian rất dài, rất dài,” Lin nói.

“Đó là một thời kỳ khá u ám,” Sahai nhớ lại. “Có một nghĩa đen với tất cả những ý tưởng không thành công.”

Cuối cùng, tuy nhiên—cùng với Prabhanjan Ananth của Đại học California, Santa Barbara, và Christian Matt của dự án blockchain Concordium—họ nảy ra một ý tưởng về một loại thoả hiệp: Vì iO dường như cần bản đồ bậc 3, nhưng các nhà khoa học máy tính chỉ có xây dựng an toàn cho bản đồ bậc 2, thì có điều gì đó ở giữa—một loại bản đồ bậc 2.5?

Các nhà nghiên cứu đã tưởng tượng ra một hệ thống trong đó một số tủ khoá có cửa sổ rõ, để người dùng có thể nhìn thấy giá trị bên trong. Điều này giúp máy không phải bảo vệ quá nhiều thông tin ẩn. Để đạt được sự cân bằng giữa sức mạnh của bản đồ đa tuyến bậc cao và sự an toàn của bản đồ bậc 2, máy được phép tính toán với đa thức có bậc cao hơn 2, nhưng có một hạn chế: Đa thức phải có bậc 2 đối với các biến số ẩn. “Chúng tôi đang cố gắng không giấu nhiều” như trong bản đồ đa tuyến tổng quát, Lin nói. Các nhà nghiên cứu đã có thể chỉ ra rằng hệ thống tủ khoá lai này có thể được xây dựng an toàn.

Tuy nhiên, để chuyển từ những bản đồ đa tuyến ít mạnh mẽ này sang iO, đội ngũ cần một thành phần cuối cùng: một loại trình tạo số giả ngẫu nhiên mới, cái gì đó mở rộng một chuỗi bit ngẫu nhiên thành một chuỗi dài vẫn trông đủ ngẫu nhiên để đánh lừa máy tính. Đó là điều mà Jain, Lin và Sahai đã tìm ra cách thực hiện trong bài báo mới của họ. “Có một tháng cuối cùng tuyệt vời nơi mọi thứ hòa quyện trong một loạt cuộc gọi điện thoại,” Sahai nói.

Kết quả là một giao thức iO cuối cùng tránh được nhược điểm an ninh của bản đồ đa tuyến. “Công việc của họ trông tuyệt vời,” Pass nói.

An ninh của kế hoạch này dựa trên bốn giả thuyết toán học đã được sử dụng rộng rãi trong ngữ cảnh mật mã khác. Và thậm chí giả thuyết ít được nghiên cứu nhất, được gọi là giả thuyết “học cộng với nhiễu”, liên quan đến một vấn đề đã được nghiên cứu từ những năm 1950.

Có lẽ chỉ có một điều có thể phá vỡ kế hoạch mới này: máy tính lượng tử, nếu một máy tính lượng tử hoàn toàn mạnh mẽ được xây dựng. Một trong bốn giả thuyết này dễ bị tấn công lượng tử, nhưng trong vài tháng gần đây, một hướng nghiên cứu riêng đã xuất hiện trong ba bài báo riêng của Pass và các nhà nghiên cứu khác đề xuất một con đường tiếp cận iO khác có thể an toàn ngay cả trước các tấn công lượng tử. Những phiên bản iO này dựa trên giả thuyết an ninh ít được thiết lập hơn so với những giả thuyết mà Jain, Lin và Sahai đã sử dụng, nhiều nhà nghiên cứu nói. Nhưng có khả năng, Barak nói, hai phương pháp này có thể được kết hợp trong những năm sắp tới để tạo ra một phiên bản iO dựa trên giả thuyết an ninh tiêu chuẩn và cũng chống lại các tấn công lượng tử.

Xây dựng của Jain, Lin và Sahai có thể sẽ làm cho những nhà nghiên cứu mới hứng thú với lĩnh vực này để làm cho kế hoạch trở nên thực tế hơn và phát triển các phương pháp mới, Ishai dự đoán. “Khi bạn biết rằng điều gì đó có thể được thực hiện về nguyên tắc, nó khiến cho việc làm việc trong lĩnh vực này tâm lý dễ dàng hơn nhiều,” ông nói.

Các nhà khoa học máy tính vẫn còn nhiều công việc phải làm trước khi giao thức (hoặc một biến thể nào đó của nó) có thể được sử dụng trong các ứng dụng thực tế. Nhưng đó là phần của quá trình, các nhà nghiên cứu nói. “Trong mật mã có nhiều khái niệm, khi chúng đầu tiên xuất hiện, mọi người đều nói, ‘Đây chỉ là lý thuyết thuần túy, [nó] không có liên quan đến thực tế,’” Pass nói. “Sau đó 10 hoặc 20 năm sau, Google đang triển khai những điều này.”

Con đường từ một đột phá lý thuyết đến một giao thức thực tế có thể là một hành trình dài, Barak nói. “Nhưng bạn có thể tưởng tượng,” ông nói, “rằng có lẽ 50 năm nữa sách giáo trình mật mã sẽ cơ bản nói, ‘OK, đây là một cách xây dựng rất đơn giản của iO, và từ đó chúng ta sẽ tạo ra tất cả phần còn lại của mật mã.’”

Bài viết gốc được tái bản với sự cho phép từ Quanta Magazine, một tờ báo độc lập biên tập thuộc Quỹ Simons, nhiệm vụ của nó là nâng cao sự hiểu biết của công chúng về khoa học bằng cách đưa ra các phát triển nghiên cứu và xu hướng trong toán học và các ngành khoa học tự nhiên và sinh học.

Những điều Tuyệt Vời Khác Trên Mytour

• 📩 Muốn nhận thông tin mới nhất về công nghệ, khoa học, và nhiều hơn nữa? Đăng ký nhận bản tin của chúng tôi!
• Một người đi bộ vô danh và vụ án mà internet không thể giải quyết
• Một người lính SEAL, một chiếc drone, và hành trình cứu sống trong chiến đấu
• Đây là cách tái chế các thiết bị cũ của bạn
• Tại sao con bọ “quỷ dữ” có thể sống sót sau khi bị ô tô cán qua
• Tại sao mọi người đều đang xây dựng một chiếc xe tải điện?
• 🎮 Mytour Games: Nhận các mẹo, đánh giá, và nhiều hơn nữa
• 🏃🏽‍♀️ Muốn có những công cụ tốt nhất để khỏe mạnh? Hãy kiểm tra bộ chọn lựa của đội Gear chúng tôi cho những chiếc đồng hồ theo dõi sức khỏe tốt nhất, trang thiết bị chạy (bao gồm giày và tất), và tai nghe tốt nhất