- Mã hóa đồng hình hoàn toàn (FHE) là công nghệ cho phép thực hiện phép toán trực tiếp trên bản mã mà không cần giải mã dữ liệu
- Hiện tại, FHE vẫn còn những hạn chế như tính thực tiễn thấp, tốc độ xử lý chậm hơn 1.000 đến 10.000 lần và nhu cầu lưu trữ tăng 40 đến 1.000 lần
- Tuy nhiên, gần đây các thuật toán FHE đã cải thiện tốc độ gấp 8 lần mỗi năm, và có khả năng sớm bước vào giai đoạn ứng dụng thực tế trong điện toán đám mây, suy luận LLM, smart contract blockchain, v.v.
- Nếu FHE trở nên phổ biến, nó sẽ thúc đẩy một sự thay đổi mang tính công nghiệp, trong đó quyền riêng tư dữ liệu trở thành mặc định trên toàn bộ môi trường tính toán
- Bài viết tổng hợp toàn diện các khái niệm cốt lõi như mật mã dựa trên lưới, LWE, bootstrapping, cùng lịch sử phát triển thuật toán FHE, ví dụ triển khai thực tế và xu hướng cải thiện hiệu năng
Giới thiệu: Mã hóa đồng hình hoàn toàn là gì
- Mã hóa đồng hình hoàn toàn (Fully Homomorphic Encryption, FHE) là phương pháp cho phép thực hiện các phép toán tùy ý trên dữ liệu ở trạng thái mã hóa mà không cần giải mã, tức là có thể tính toán trực tiếp trên dữ liệu đã mã hóa
- Nói cách khác, máy chủ có thể tính toán truy vấn và kết quả để gửi lại mà không cần biết nội dung bản rõ
- Công nghệ này hiện đã bắt đầu được đưa vào nhiều hệ thống thực tế ngày nay
Tiềm năng và giới hạn của FHE: "Định luật Moore của FHE"
- FHE có thể giữ dữ liệu luôn ở trạng thái mã hóa trên toàn bộ mạng, từ đó hiện thực hóa quyền riêng tư hoàn toàn bằng cách chặn tận gốc nguy cơ rò rỉ dữ liệu
- Dù vậy, lý do khiến việc ứng dụng thực tế hiện nay còn bị hạn chế là vì phép toán trên bản mã chậm hơn phép toán trên bản rõ từ 1.000 đến 10.000 lần, và dung lượng lưu trữ cũng tăng khoảng 40 đến 1.000 lần, gây ra sự suy giảm hiệu năng rất lớn
- Điều này tương tự với thời kỳ đầu của Internet trong thập niên 1990
- Tuy nhiên, gần đây FHE đang nhanh hơn gấp 8 lần mỗi năm, nên được kỳ vọng sẽ sớm bước vào nhiều lĩnh vực ứng dụng thực tế
Điểm bùng phát: thời điểm FHE trở nên thực dụng đang đến gần
- Nếu tốc độ tiến bộ đột phá như vậy tiếp tục được duy trì, trong tương lai FHE có thể được ứng dụng thực tế trong các lĩnh vực sau
- Điện toán đám mây được mã hóa
- Suy luận LLM được mã hóa
- Smart contract blockchain có khả năng bảo mật bí mật
- Sự thay đổi này có thể làm lung lay tận gốc mô hình kinh doanh Internet dựa trên việc thu thập dữ liệu người dùng
- Nhờ FHE, có thể kỳ vọng vào sự chuyển đổi bản chất từ một Internet mà "giám sát là mặc định" sang một Internet mà "riêng tư là mặc định"
Điểm yếu chí mạng của bảo mật dữ liệu và lời giải của FHE
- Dữ liệu có 3 trạng thái (lưu trữ, truyền tải, sử dụng), và trạng thái 'đang sử dụng' thường bị giải mã nên trở thành điểm yếu bảo mật
- Đám mây, nội gián, hacker, CPU dễ bị tổn thương, v.v. đều có thể truy cập dữ liệu bản rõ trong bộ nhớ
- Phần lớn các vụ rò rỉ dữ liệu quy mô lớn cũng xảy ra khi dữ liệu 'đang được sử dụng' hoặc 'đang được lưu trữ'
- FHE giữ dữ liệu ở trạng thái mã hóa trong toàn bộ vòng đời của nó, qua đó giải quyết tận gốc những điểm yếu này
Định nghĩa về điện toán riêng tư hoàn toàn
- Môi trường lý tưởng là dữ liệu luôn được mã hóa khi lưu trữ, truyền tải và sử dụng (tính toán)
- Ví dụ, máy chủ hoàn toàn không nhìn thấy truy vấn bản rõ, mà chỉ nhận truy vấn đã mã hóa và trả về kết quả đã mã hóa
- Chỉ người dùng mới có thể giải mã kết quả đó
Cách FHE hoạt động: cấu trúc và khái niệm toán học
- "Đồng hình" dựa trên một phép biến đổi toán học bảo toàn cùng cấu trúc (ví dụ tương tự phép biến đổi Fourier)
- FHE biến đổi qua lại giữa không gian bản rõ và không gian bản mã, sao cho giải mã kết quả phép toán trên bản mã sẽ đúng bằng kết quả phép toán trên bản rõ
- Các phép biến đổi này chủ yếu sử dụng mật mã dựa trên lưới và LWE (Learning With Errors)
- Mật mã dựa trên lưới là một bài toán vectơ trong không gian có số chiều rất cao, được biết đến là khó giải ngay cả với máy tính lượng tử (kháng lượng tử)
- LWE là bài toán suy ngược một hệ tuyến tính có lẫn nhiễu, nên trên thực tế gần như không thể phá giải
Quản lý nhiễu và bootstrapping
- Trong FHE, khi số lần tính toán tăng lên, nhiễu (noise) trong bản mã cũng tăng theo
- Với phép cộng, nhiễu tăng tuyến tính; với phép nhân, nó tăng theo cấp số nhân, cuối cùng có thể khiến việc giải mã trở nên bất khả thi
- Công nghệ cốt lõi để giải quyết vấn đề này là bootstrapping, tức kỹ thuật tái mã hóa bản mã bằng một 'khóa công khai mới' để đặt lại mức nhiễu về ngưỡng nhất định
- Quá trình này là nút thắt hiệu năng của hệ thống FHE, nhưng đang được cải thiện nhanh chóng qua từng năm
Các thành phần cốt lõi bổ sung của FHE
- Tuyến tính hóa lại (relinearization): quá trình giải quyết vấn đề bậc của khóa tăng lên 2 sau phép nhân, rồi đưa nó trở lại bậc 1
- Chuyển modulus (modulus switching): kỹ thuật thu nhỏ modulus của bản mã để quản lý nhiễu
Ngoài ra, cùng với sự phát triển của thuật toán, nhiều kỹ thuật đa dạng khác cũng liên tục được đề xuất
Phân loại các hệ mã hóa đồng hình (HE) và ví dụ Python
- Mã hóa đồng hình từng phần (Partial HE): chỉ hỗ trợ một phép toán (ví dụ, mã hóa Paillier chỉ hỗ trợ phép cộng)
- Mã hóa đồng hình một phần hạn chế (Somewhat HE): hỗ trợ cả cộng và nhân, nhưng số lần lặp phép nhân bị giới hạn
- Mã hóa đồng hình hoàn toàn (FHE): hỗ trợ không giới hạn cả cộng và nhân, bảo đảm tính đầy đủ Turing
Thông qua ví dụ mật mã Paillier được triển khai bằng Python, có thể trực quan trải nghiệm tính đồng hình từng phần
Lịch sử phát triển của FHE và "Định luật Moore của FHE"
- 1978: lần đầu xuất hiện khái niệm "đồng cấu riêng tư"
- 2009: Craig Gentry hiện thực hóa FHE đầu tiên (luận án tiến sĩ)
- 2011: triển khai đầu tiên, mất 30 phút cho mỗi bit (rất chậm)
- Từ 2013: thời gian bootstrapping rút xuống còn mức vài ms
- 2017: CKKS và các kỹ thuật khác hỗ trợ xấp xỉ số thực dấu phẩy động, bắt đầu được áp dụng nghiêm túc vào ML/AI
Các thuật toán FHE đã cải thiện gấp 8 lần mỗi năm kể từ 2011, từ mức overhead ban đầu 10¹⁰ lần xuống còn khoảng 10³ đến 10⁴ lần gần đây
Các bài báo mới nhất đã giảm thông lượng phép nhân FHE xuống 1.000 lần và độ trễ xuống 10 lần; khi kết hợp tăng tốc phần cứng, vẫn còn dư địa cải thiện tốc độ thêm hơn 1.000 lần
Tương lai nơi mã hóa trở thành mặc định
- Các vụ rò rỉ dữ liệu quy mô lớn là thực tế khó tránh khỏi
- Nếu dùng FHE để máy chủ có thể chỉ tính toán trên dữ liệu đã mã hóa mà không cần khóa giải mã, điều đó sẽ trở thành một chuẩn mực mới cho bảo vệ quyền riêng tư
- Dù hiện vẫn chưa hoàn toàn thực dụng trong mọi lĩnh vực, công nghệ này đang được cải thiện với tốc độ đáng kinh ngạc mỗi năm
- Khi nhu cầu về quyền riêng tư của người dùng kết hợp với việc siết chặt quy định liên quan, FHE cuối cùng được dự đoán sẽ trở thành tiêu chuẩn của phần lớn điện toán đám mây
- Điện toán Internet trong tương lai sẽ tiến hóa theo hướng luôn ở trạng thái mã hóa
Thập niên 2010: HTTPS là mặc định
Trong tương lai: được kỳ vọng sẽ đến thời đại FHE là mặc định
Tài liệu tham khảo và tài liệu bổ sung
- FHE Reference Library: tổng hợp toàn diện tài liệu học thuật
- Luận án tiến sĩ năm 2009 của Craig Gentry: điểm khởi đầu của FHE
- Vitalik Buterin: Phân tích chuyên sâu về FHE
- Cộng đồng: FHE.org (hub dành cho nhà phát triển)
- GitHub: awesome-he: bộ sưu tập các dự án liên quan đến mã hóa đồng hình
1 bình luận
Ý kiến trên Hacker News
Xin nói trước từ góc độ một người rất thích FHE và mật mã học. Dù FHE đang dần nhanh hơn, nhưng chừng nào còn phụ thuộc vào bootstrapping thì nó không thể bắt kịp tốc độ xử lý trên bản rõ. Overhead hơn khoảng 1000 lần do bootstrapping về cơ bản là không thể tránh, và khi người ta nhận ra không thể tiếp tục tăng tốc thêm đáng kể thì bắt đầu xuất hiện câu chuyện tăng tốc bằng phần cứng. Nhưng ở thời điểm mà toàn bộ năng lực tính toán đều đang đổ vào LLM như hiện nay, điều đó không hề dễ. Chỉ cần nghĩ đến chi phí trên mỗi token sẽ tăng lên bao nhiêu khi tính toán bằng FHE thì có thể thấy, nếu không thấp hơn mức hơn 1000 lần thì gần như không có tính khả thi trong thực tế. Nếu mục tiêu là bảo vệ quyền riêng tư thì hiện tại confidential computing là phương án thay thế thực dụng duy nhất. Tôi cũng không thích chuyện phải tin vào phần cứng, nhưng đó là điều tốt nhất chúng ta đang có
Có một lý do còn cơ bản hơn khiến FHE khó dùng cho tính toán tùy ý. Đó là có những loại phép toán mà độ phức tạp trên bản mã tăng lên bất thường so với bản rõ. Ví dụ với truy vấn cơ sở dữ liệu, trên bản rõ là O(log n), nhưng nếu tìm bằng khóa đã mã hóa thì thành O(n). Vì vậy, Google Search hoàn toàn đồng hình về cơ bản là bất khả thi. Tuy nhiên, suy luận DNN hoàn toàn đồng hình có thể là một câu chuyện khác
Ngay cả không có bootstrapping thì FHE cũng không thể nhanh như phép toán trên bản rõ. Bản mã lớn hơn bản rõ khoảng 1000 lần. Điều đó có nghĩa là cần băng thông bộ nhớ và lượng tính toán lớn hơn rất nhiều. Không thể thu hẹp được khoảng cách này
Tôi tự hỏi liệu có một nhóm nhu cầu cụ thể nào thực sự muốn quyền riêng tư có thể kiểm chứng, ngay cả khi chi phí tính toán tăng 1000 lần hay không. Có lẽ sẽ không lớn như Dropbox, nhưng tôi hình dung vẫn có một thị trường nhất định
Nhìn lại thời trước khi mọi thứ đều là card mở rộng PCIe. GPU cũng vậy, các bộ tăng tốc chuyên dụng như math coprocessor cũng vậy. Bây giờ chúng được tích hợp vào phần cứng phổ thông nên rẻ và tiện hơn, nhưng không thể làm tốt bằng silicon tối ưu cho một chức năng cụ thể. Vì thế tôi cho rằng nên dùng card chuyên dụng riêng cho AI/ML thay vì dựa trên GPU. Kiến trúc có chồng lấn một phần, nhưng card AI dựa trên GPU là chấp nhận thiệt thòi ở nhiều mặt. Theo tôi, bộ tăng tốc AI thực sự là phần cứng chuyên dụng gắn vào socket SXM mới nhất. Nhưng socket SXM chỉ có trên server và giá cũng không hề rẻ
Tôi công nhận cơn sốt LLM, nhưng cũng tự hỏi liệu có thật sự không còn ứng dụng nào khác đáng dùng FHE hay không. Ví dụ có thể nghĩ đến cách host một thuật toán giao dịch không cần tốc độ cao trên server bằng FHE để đảm bảo an toàn
FHE quan trọng vì hiện nay có những trường hợp doanh nghiệp bị sức ép từ chính phủ buộc phải phá mã nhắm vào một mục tiêu cụ thể. FHE cho phép doanh nghiệp đường hoàng nói rằng “chúng tôi tuyệt đối không thể nhìn thấy bản rõ”. Ở vai trò nhà mạng thì điều này phần nào đã làm được bằng E2E encryption, nhưng khi dữ liệu cần được xử lý ở trạng thái bản rõ thì vẫn chưa thể. Tôi cho rằng quyền riêng tư là một quyền con người cơ bản. Quyền lực của chính phủ chỉ nên vận hành rất hạn chế đối với các hoạt động dân chủ như bỏ phiếu, nghệ thuật, báo chí, biểu đạt, v.v.
Dù FHE cho phép tính toán tùy ý, phần lớn dịch vụ tồn tại là vì chúng cung cấp dữ liệu cụ thể. Nếu Google muốn đảm bảo bảo mật cho truy vấn của tôi thì họ phải mã hóa toàn bộ chỉ mục tìm kiếm, mà điều đó là bất khả thi trong thực tế. Về mặt kinh doanh, tôi cũng cho rằng ngoài một số rất ít lĩnh vực đòi hỏi độ tin cậy cao và rủi ro cao, gần như không có động lực để áp dụng dịch vụ kiểu FHE
Theo tôi biết, chỉ cần mã hóa dữ liệu nhạy cảm là đủ (ví dụ: dữ liệu giao dịch ngân hàng của tôi). Bản thân hàm cần tính không nhất thiết phải mã hóa, mà có thể dùng kết hợp với dữ liệu công khai
Xét cho cùng, từ góc độ doanh nghiệp lớn thì họ phải trực tiếp nhìn vào dữ liệu hoặc truy vấn của người dùng mới kiếm ra tiền, nên họ không có động lực để áp dụng FHE như một thói quen. Trong lĩnh vực tài chính như ngân hàng thì nghe có vẻ hay, nhưng ngoài ra thì chưa rõ bao giờ mới được áp dụng
Phần nói về động lực là đúng. Nhưng phần đầu thì khác. Tra cứu riêng tư vào cơ sở dữ liệu bản rõ đã khả thi từ vài năm trước. Chỉ là hoặc phải tiền xử lý cơ sở dữ liệu bản rõ theo cách khá phức tạp, hoặc trong trường hợp xấu nhất phải quét tuyến tính toàn bộ cơ sở dữ liệu
Giới thiệu spiralwiki.com như một ví dụ triển khai công cụ tìm kiếm FHE hoàn toàn riêng tư. Đây là cách mà server hoàn toàn không thể biết người dùng đang đọc bài Wikipedia nào spiralwiki.com
Ở “góc nhìn client”, chắc chắn sẽ có người sẵn sàng trả tiền để dùng dịch vụ bảo vệ dữ liệu hoàn hảo như FHE, nhưng trên thực tế nó sẽ cực kỳ đắt và số người đăng ký sẽ rất ít. Nếu tính với giả định chi phí tính toán cao hơn hiện tại hàng chục lần, thì ngay cả khi một dịch vụ thay thế Google tập trung vào quyền riêng tư có giá $100/năm, cũng sẽ khó thu hút nhiều người dùng. Chi phí càng tăng thì số người đăng ký càng giảm. Đã có những lựa chọn thay thế như Tor, dù không hoàn hảo nhưng vẫn cung cấp mức bảo vệ khá lớn miễn phí. Không phải HE (mã hóa đồng hình) là vô dụng, mà là chỉ có một số rất ít người sẵn sàng trả chi phí để dùng nó
Có nhắc đến khả năng Internet chuyển từ “mặc định là giám sát” sang “mặc định là quyền riêng tư”. Tôi cũng đã nhiều năm phổ biến các công nghệ quyền riêng tư như tạo chữ ký số. Nhưng phải nhìn vào thực tế rằng Hacker News hay Facebook đều đang nắm giữ danh tính của mọi người. Đó là vì nó quá dễ và có thể kiếm tiền. FHE cũng là kiểu “công nghệ mà mọi người muốn nhưng trên thực tế không được phổ biến rộng nhanh chóng”. Nguyên nhân là trong hầu hết trường hợp, người ta cho rằng cách làm hiện tại đã đủ tốt nếu xét đến gánh nặng vận hành và độ phức tạp
Mỗi khi gắn thứ như chữ ký số ở cuối email, tôi chỉ nhận được phản ứng kiểu “cái đó là gì vậy?”. Tôi tò mò không biết có ai từng thuyết phục được người dùng phổ thông tham gia vào mã hóa phía client hay chưa
Có ý kiến cho rằng khi FHE kết hợp với AI, chính AI có thể gánh bớt một phần độ phức tạp, và đây có thể là tổ hợp sát thủ đủ sức phổ biến thật sự
Trên thực tế, tôi không thấy có lý do gì để doanh nghiệp áp dụng một giải pháp kiểu dịch vụ FHE, nơi họ phải dùng lượng tính toán gấp 1.000.000 lần, khó debug hơn, lại không thể phân tích hành vi sử dụng
Bắt đầu câu chuyện bằng ví dụ Google có thể gây hiểu lầm. Thông thường khi nói “Google”, người ta nghĩ đến “tìm kiếm web”, trong khi FHE được mô tả trong bài có thể không hợp với bối cảnh dịch vụ tìm kiếm vì toàn bộ đầu vào phải được mã hóa bằng một khóa duy nhất. Chỉ mục tìm kiếm của Google có kích thước tới hàng TB, nên việc mã hóa toàn bộ bằng một khóa cụ thể theo tôi là bất khả thi. Nói cách khác, FHE chỉ hữu ích khi người dùng kiểm soát toàn bộ đầu vào. Ví dụ về Google làm mọi thứ rối hơn
Trong những trường hợp như CallerID của Apple, có vẻ không nhất thiết phải mã hóa toàn bộ cơ sở dữ liệu theo từng người dùng Nghiên cứu mã hóa đồng hình của Apple / Tìm kiếm riêng tư của Apple
Dịch vụ đồng hình ngay từ đầu không cần biết trước khóa mã hóa. Đó chính là điểm cốt lõi. Với một ví dụ mã hóa rất đơn giản, có thể xây dựng cấu trúc cho phép cộng các bản mã với nhau khi chưa chỉ định khóa. Nếu hỗ trợ các phép toán phức tạp hơn trên loại mã mạnh hơn, có thể triển khai rất nhiều chức năng đa dạng
Khi nói đến Google thì không chỉ là tìm kiếm, mà còn có Gmail, Google Docs và rất nhiều dịch vụ liên quan đến dữ liệu cá nhân. Ai chỉ nghĩ đến tìm kiếm có lẽ còn chưa đọc bài viết liên quan
Tôi nghĩ FHE sẽ không dễ được đưa ngay vào điện toán đa dụng hay dịch vụ Internet. Có lẽ phải chờ thêm nhiều thế hệ của định luật Moore nữa mới khả thi. Tuy vậy, các lĩnh vực mà FHE đã bắt đầu phát huy là những nơi độ phức tạp thấp hơn nhưng yêu cầu bảo mật và độ tin cậy rất cao, như smart contract, tài chính và y tế. Gần đây nhờ định luật Moore và tối ưu phần mềm, đường cong dường như đã bắt đầu bẻ về phía tính thực dụng. Có nhắc đến công việc về phần cứng/Devtools của Zama như một ví dụ
E2EE git đã được phát triển rồi. Tôi từng hỏi người tạo ra nó liệu có thể giải quyết các yêu cầu như protected branch hay ngăn force push ở phía server hay không, nhưng nếu client có ác ý thì không có biện pháp nào thật sự phù hợp. Tôi cũng tò mò không biết liệu thứ này một ngày nào đó có thể phát triển thành E2EE Github hay không liên kết Hacker News liên quan
Mỗi khi nghe những lời bàn rằng tốc độ của FHE sẽ tiếp tục được cải thiện, tôi lại nhớ đến một bài toán toán học cũ về tốc độ trung bình. Ví dụ, nếu đi 1 dặm lên dốc với tốc độ 15 dặm/giờ, thì phải đi nhanh đến mức nào trên 1 dặm xuống dốc để tốc độ trung bình của cả 2 dặm đạt 30 dặm/giờ? Tốc độ cải thiện trong quá khứ không đảm bảo khả năng trong tương lai. Đây không phải giới hạn vật lý mà là giới hạn thuật toán
Nếu đoạn xuống dốc là vách đá thì sao? Nếu lấy vận tốc cực đại của ô tô khoảng 200-300mph để tính, thì về mặt con số có thể 1 dặm rơi tự do chỉ mất 15 giây. Để trung bình 30mph trên toàn bộ 2 dặm thì tổng thời gian là 4 phút, nên tốc độ lên dốc cũng sẽ phải điều chỉnh cho phù hợp với thời gian còn lại, nhưng trên thực tế có quá nhiều biến số nên không thể thực hiện được
Nếu tính thật chặt chẽ thì chỉ cần đi xuống dốc ở 41mph là tốc độ trung bình toàn hành trình sẽ là 30mph. Nếu giả định trong câu hỏi có làm tròn số hoặc sai số đo lường thì sẽ ra kết quả như vậy