Các nhà mật mã học nghĩ ra cách tiếp cận toàn diện về quyền riêng tư trong tìm kiếm | Tạp chí Quanta

Tất cả chúng ta đều biết phải cẩn thận với những chi tiết mình chia sẻ trực tuyến, nhưng thông tin chúng ta tìm kiếm cũng có thể tiết lộ thông tin. Tìm kiếm chỉ đường lái xe và vị trí của chúng tôi trở nên dễ đoán hơn nhiều. Kiểm tra mật khẩu trong kho dữ liệu bị xâm phạm và chúng ta có nguy cơ tự làm rò rỉ mật khẩu đó.

Những tình huống này đặt ra một câu hỏi quan trọng trong mật mã: Làm thế nào bạn có thể lấy thông tin từ cơ sở dữ liệu công cộng mà không tiết lộ bất cứ điều gì về những gì bạn đã truy cập? Nó tương đương với việc mượn một cuốn sách từ thư viện mà thủ thư không biết đó là cuốn nào.

Việc tạo ra một chiến lược giải quyết vấn đề này – được gọi là truy xuất thông tin cá nhân – là “một khối xây dựng rất hữu ích trong một số ứng dụng bảo vệ quyền riêng tư”, cho biết David Wu, một nhà mật mã học tại Đại học Texas, Austin. Kể từ những năm 1990, các nhà nghiên cứu đã giải quyết vấn đề này, cải thiện các chiến lược truy cập cơ sở dữ liệu một cách riêng tư. Một mục tiêu chính, vẫn không thể thực hiện được với cơ sở dữ liệu lớn, tương đương với tìm kiếm riêng tư trên Google, nơi bạn có thể sàng lọc hàng đống dữ liệu một cách ẩn danh mà không cần thực hiện bất kỳ công việc tính toán nặng nhọc nào.

Bây giờ, ba nhà nghiên cứu đã chế tạo một phiên bản truy xuất thông tin cá nhân được tìm kiếm từ lâu và mở rộng nó để xây dựng một chiến lược bảo mật tổng quát hơn. Tác phẩm đã nhận được giải Giải thưởng giấy tốt nhất vào tháng XNUMX hàng năm Hội nghị chuyên đề về lý thuyết máy tính, lật đổ một rào cản lý thuyết lớn trên con đường hướng tới một cuộc tìm kiếm thực sự riêng tư.

“[Đây là] thứ gì đó trong mật mã mà tôi đoán là tất cả chúng ta đều muốn nhưng không hoàn toàn tin rằng nó tồn tại,” nói Vinod Vaikuntanathan, một nhà mật mã học tại Viện Công nghệ Massachusetts, người không tham gia vào bài báo. “Đó là một kết quả mang tính bước ngoặt.”

Vấn đề truy cập cơ sở dữ liệu riêng tư đã hình thành vào những năm 1990. Lúc đầu, các nhà nghiên cứu cho rằng giải pháp duy nhất là quét toàn bộ cơ sở dữ liệu trong mỗi lần tìm kiếm, điều này giống như nhờ thủ thư lùng sục từng kệ trước khi quay lại với cuốn sách của bạn. Rốt cuộc, nếu tìm kiếm bỏ qua bất kỳ phần nào, thủ thư sẽ biết rằng sách của bạn không có trong phần đó của thư viện.

Cách tiếp cận đó hoạt động đủ tốt ở quy mô nhỏ hơn, nhưng khi cơ sở dữ liệu phát triển, thời gian cần thiết để quét nó ít nhất cũng tăng theo tỷ lệ. Khi bạn đọc từ cơ sở dữ liệu lớn hơn - và Internet là một cơ sở dữ liệu khá lớn - quá trình này trở nên cực kỳ kém hiệu quả.

Vào đầu những năm 2000, các nhà nghiên cứu bắt đầu nghi ngờ rằng họ có thể tránh được rào cản quét toàn bộ bằng cách “tiền xử lý” cơ sở dữ liệu. Đại khái, điều này có nghĩa là mã hóa toàn bộ cơ sở dữ liệu dưới dạng một cấu trúc đặc biệt, do đó máy chủ có thể trả lời truy vấn bằng cách chỉ đọc một phần nhỏ của cấu trúc đó. Về mặt lý thuyết, việc xử lý trước đủ cẩn thận có thể có nghĩa là một máy chủ lưu trữ thông tin chỉ thực hiện quy trình một lần, cho phép tất cả người dùng trong tương lai lấy thông tin một cách riêng tư mà không cần nỗ lực thêm.

Trong Daniel Wichs, một nhà mật mã học tại Đại học Northeastern và là đồng tác giả của bài báo mới, điều đó có vẻ quá tốt để có thể trở thành sự thật. Khoảng năm 2011, ông bắt đầu cố gắng chứng minh rằng kế hoạch kiểu này là không thể. “Tôi tin chắc rằng không có cách nào có thể thực hiện được điều này,” anh nói.

Nhưng vào năm 2017, hai nhóm nhà nghiên cứu công bố các kết quả điều đó đã thay đổi suy nghĩ của anh ấy Họ đã xây dựng những chương trình đầu tiên có thể thực hiện kiểu truy xuất thông tin cá nhân này, nhưng họ không thể chứng minh rằng các chương trình đó an toàn. (Các nhà nghiên cứu mật mã chứng minh tính bảo mật của hệ thống bằng cách chỉ ra rằng việc phá vỡ nó cũng khó như giải một số bài toán khó. Các nhà nghiên cứu không thể so sánh nó với một bài toán khó điển hình.)

Vì vậy, ngay cả khi hy vọng được đổi mới, Wichs cho rằng bất kỳ phiên bản nào của những chương trình này được bảo mật vẫn còn rất lâu mới có. Thay vào đó, ông và các đồng tác giả -- Wei Kai Lin, hiện tại Đại học Virginia, và Ethan Mook, cũng tại Northeastern — đã giải quyết các vấn đề mà họ cho rằng sẽ dễ dàng hơn, liên quan đến các trường hợp có nhiều máy chủ lưu trữ cơ sở dữ liệu.

Trong các phương pháp họ nghiên cứu, thông tin trong cơ sở dữ liệu có thể được chuyển đổi thành biểu thức toán học mà máy chủ có thể đánh giá để trích xuất thông tin. Các tác giả cho rằng có thể làm cho quá trình đánh giá đó hiệu quả hơn. Họ đùa giỡn với một ý tưởng từ năm 2011, khi các nhà nghiên cứu khác đã tìm ra cách đánh giá nhanh một biểu thức như vậy bằng cách xử lý trước nó, tạo ra các bảng giá trị đặc biệt, nhỏ gọn cho phép bạn bỏ qua các bước đánh giá thông thường.

Phương pháp đó không tạo ra bất kỳ cải tiến nào và nhóm gần như đã từ bỏ — cho đến khi họ tự hỏi liệu công cụ này có thực sự hoạt động trong trường hợp một máy chủ mà họ mong muốn hay không. Họ thấy rằng họ đã chọn một đa thức đủ cẩn thận và một máy chủ duy nhất có thể xử lý trước nó dựa trên kết quả năm 2011 - mang lại sơ đồ tra cứu hiệu quả, an toàn mà Wichs đã cân nhắc trong nhiều năm. Đột nhiên, rốt cuộc họ đã giải quyết được vấn đề khó khăn hơn.

Lúc đầu, các tác giả không tin điều đó. “Hãy cùng tìm hiểu xem điều này có vấn đề gì,” Wichs nhớ lại mình đã nghĩ như vậy. “Chúng tôi tiếp tục cố gắng tìm ra nơi nó bị hỏng.”

Nhưng giải pháp đã được đưa ra: Họ đã thực sự phát hiện ra một cách an toàn để xử lý trước cơ sở dữ liệu trên một máy chủ để bất kỳ ai cũng có thể lấy thông tin một cách bí mật. “Nó thực sự vượt xa mọi thứ chúng tôi mong đợi,” nói Yuval Ishai, một nhà mật mã học tại Technion ở Israel, người không tham gia vào công việc này. Đó là kết quả “chúng tôi thậm chí không đủ can đảm để yêu cầu,” anh nói.

Wichs cho biết, sau khi xây dựng sơ đồ tra cứu bí mật, các tác giả đã chuyển sang mục tiêu thực tế là tìm kiếm trên Internet riêng tư, việc này phức tạp hơn việc lấy các thông tin từ cơ sở dữ liệu. Bản thân lược đồ tra cứu riêng tư cho phép tạo ra một phiên bản tìm kiếm riêng tư giống như Google, nhưng nó cực kỳ tốn nhiều công sức: Bạn tự chạy thuật toán của Google và bí mật lấy dữ liệu từ internet khi cần thiết. Wichs cho biết một tìm kiếm thực sự, trong đó bạn gửi yêu cầu và ngồi lại trong khi máy chủ thu thập kết quả, thực sự là mục tiêu cho một cách tiếp cận rộng hơn được gọi là mã hóa đồng hình, giúp ngụy trang dữ liệu để người khác có thể thao túng nó mà không hề biết gì về nó. .

Các chiến lược mã hóa đồng hình điển hình sẽ gặp khó khăn tương tự như việc truy xuất thông tin cá nhân, phải cày nát tất cả nội dung trên Internet cho mỗi lần tìm kiếm. Nhưng bằng cách sử dụng phương pháp tra cứu riêng tư của họ làm giàn giáo, các tác giả đã xây dựng một sơ đồ mới chạy các phép tính giống với các chương trình chúng ta sử dụng hàng ngày hơn, lấy thông tin một cách bí mật mà không cần quét toàn bộ mạng Internet. Điều đó sẽ giúp tăng cường hiệu quả cho các tìm kiếm trên internet và bất kỳ chương trình nào cần truy cập nhanh vào dữ liệu.

Ishai cho biết, mặc dù mã hóa đồng cấu là một phần mở rộng hữu ích của sơ đồ tra cứu riêng tư nhưng ông coi việc truy xuất thông tin cá nhân là vấn đề cơ bản hơn. Giải pháp của các tác giả là “khối xây dựng kỳ diệu” và chiến lược mã hóa đồng cấu của họ là sự tiếp nối tự nhiên.

Hiện tại, cả hai sơ đồ đều không hữu ích trên thực tế: Quá trình tiền xử lý hiện hữu ích đến mức cực độ, khi kích thước cơ sở dữ liệu tăng dần đến vô tận. Nhưng trên thực tế, việc triển khai nó có nghĩa là những khoản tiết kiệm đó không thể thành hiện thực và quá trình này sẽ ngốn quá nhiều thời gian và dung lượng lưu trữ.

May mắn thay, Vaikuntanathan cho biết, các nhà mật mã học có lịch sử lâu dài trong việc tối ưu hóa các kết quả mà ban đầu không thực tế. Nếu công việc trong tương lai có thể hợp lý hóa cách tiếp cận, ông tin rằng việc tra cứu riêng tư từ cơ sở dữ liệu khổng lồ có thể nằm trong tầm tay. “Tất cả chúng tôi đều nghĩ mình bị mắc kẹt ở đó,” anh nói. “Kết quả của Daniel mang lại niềm hy vọng.”

Quanta đang tiến hành một loạt cuộc khảo sát để phục vụ khán giả của chúng tôi tốt hơn. Lấy của chúng tôi khảo sát độc giả khoa học máy tính và bạn sẽ được tham gia để giành chiến thắng miễn phí Quanta hàng hóa.