Lưu ý của biên tập viên: Bài viết này đến từPhòng thí nghiệm Ambi (ID: secbitlabs), được in lại bởi Odaily với sự cho phép.

Lưu ý của biên tập viên: Bài viết này đến từ

Phòng thí nghiệm Ambi (ID: secbitlabs)

, được in lại bởi Odaily với sự cho phép.

Cách đây một thời gian, tôi đã tham gia khóa học CS355 (mật mã nâng cao) tại Stanford. Chúng tôi được dạy bởi ba nghiên cứu sinh tiến sĩ của Dan, Dima Kogan, Florian Tramer và Saba Eskandarian. Ba giảng viên tiến sĩ đều có những đặc điểm riêng, hướng nghiên cứu của họ cũng rất khác nhau. Dima tập trung vào công nghệ bảo vệ quyền riêng tư PIR (Truy xuất thông tin cá nhân), Florian tập trung vào nghiên cứu ML và chuỗi khối, còn Saba tập trung vào bằng chứng không kiến ​​thức.

CS355 Khóa học này bao gồm hầu hết mọi thứ trong lĩnh vực mật mã từ thời cổ đại cho đến nay. Từ hàm một chiều sớm nhất (Chức năng một chiều), đến phương trình elip (ECC) và Ghép nối, và cuối cùng là một số MPC phổ biến, kiến ​​thức không, truy xuất thông tin cá nhân (PIR), thuật toán đồng cấu hoàn toàn, v.v. trong những năm gần đây . Vì lớp học vừa mới kết thúc hai ngày trước, tôi đã tổ chức một đợt ghi chép trong khi nội dung kiến ​​thức vẫn còn trong trí nhớ nông cạn. Nội dung của khóa học rất thú vị, và phần còn lại của nội dung sẽ được chia sẻ với bạn khi tôi có thời gian ~

Trong số này, chúng ta sẽ nói về Mã hóa đồng hình hoàn toàn (FHE) phổ biến gần đây và công nghệ Mã hóa dựa trên lưới đi kèm.

tiêu đề phụ

Mã hóa đồng cấu hoàn toàn là gì

Tôi tin rằng nhiều bạn bè đã nghe nói đến cái tên Mã hóa đồng hình hoàn toàn (FHE). Trong những năm gần đây, ngày càng có nhiều chủ đề về bảo vệ quyền riêng tư cá nhân, đồng thời hàng loạt công nghệ ứng dụng mật mã trong đó có mã hóa đồng hình cũng được phổ biến rộng rãi.

Để hiểu rõ hơn về chủ đề này, tôi xin giới thiệu sơ lược về định nghĩa mã hóa đồng cấu đầy đủ.

• Đánh giá hệ thống mã hóa

• Trước khi bắt đầu, chúng ta hãy xem xét các hệ thống mã hóa truyền thống nhất.

• Chúng ta đều biết muốn xây dựng một hệ thống mã hóa thì thường cần phải có khóa (Key). Thông qua khóa này, chúng ta có thể mã hóa thông tin văn bản gốc thành bản mã ở một đầu, sau đó thay đổi bản mã trở lại dạng ban đầu thông qua khóa ở đầu kia. Nếu không có Key này, người khác khó biết được chúng ta đã chuyển những thông tin gì.

Hình minh họa ở trên về cơ bản cho thấy bức tranh toàn cảnh về tất cả các hệ thống mã hóa phổ biến. Tất cả các hệ thống mã hóa, nếu được mô tả một cách chính thức hơn, chắc chắn sẽ làm ba việc:

Đầu tiên, một cặp khóa để mã hóa và giải mã được tạo ngẫu nhiên bằng thuật toán tạo.

Bên mã hóa mã hóa văn bản gốc thông qua khóa mã hóa và thuật toán mã hóa, cuối cùng thu được bản mã.

Sau đó, khi giải mã, bên giải mã có thể giải mã bản mã thông qua khóa giải mã và thuật toán giải mã, cuối cùng khôi phục lại văn bản gốc ban đầu.

Những người bạn biết về thuật toán mã hóa chắc chắn sẽ biết một số thuật toán mã hóa phổ biến, chẳng hạn như AES, RSA, v.v. Mọi người cũng sẽ biết rằng các hệ thống mã hóa thường được chia thành hai loại: hệ thống mã hóa đối xứng và hệ thống mã hóa bất đối xứng. Ba bước chúng tôi mô tả ở đây có thể áp dụng cho bất kỳ hệ thống mã hóa nào. Nếu nó là đối xứng, thì khóa được sử dụng để mã hóa và giải mã là như nhau. Nếu là hệ thống bất đối xứng thì mã hóa sử dụng khóa công khai (Public Key), sau đó giải mã sử dụng khóa riêng khác (Private Key).

Trong nghiên cứu mật mã, mỗi khi nhìn thấy định nghĩa về một hệ thống mới, chúng ta thường phải nêu ra các thuộc tính (Properties) mà hệ thống này cần phải có.

Đầu tiên, tài sản đầu tiên của chúng tôi để thực hiện là Correctness. Tính chính xác có nghĩa là nếu tôi có một khóa chính xác, thì tôi có thể khôi phục bản mã về văn bản gốc thông qua thuật toán giải mã. Chúng tôi thường sử dụng các phương pháp xác suất để biểu thị tỷ lệ giải mã thành công:

Phương trình trên biểu thị rằng nếu chúng ta có khóa chính xác, xác suất thuật toán giải mã có thể khôi phục bản mã do thuật toán mã hóa tạo ra là 100%.

Tài sản thứ hai chúng tôi muốn đạt được là Semantic Security.

Đối với định nghĩa về bảo mật ngữ nghĩa, chúng tôi sẽ không giải thích ở đây. Nhưng chúng ta có thể hiểu rằng nếu chúng ta có hai bản mã bất kỳ tương ứng với các văn bản gốc khác nhau thì chúng ta không thể phân biệt được bản mã nào tương ứng với văn bản gốc nào:

Ý nghĩa chính của bảo mật ngữ nghĩa là những người ngoài cuộc không thể phân biệt giữa hai thông điệp được mã hóa. Vì vậy, nếu kẻ xâm nhập nghe lén mạng và nhìn thấy thông tin được mã hóa mà tôi đã gửi, miễn là hệ thống mã hóa mà tôi sử dụng an toàn về mặt ngữ nghĩa, thì tôi có thể chắc chắn rằng kẻ xâm nhập không thể lấy được bất kỳ thông tin nào về nội dung được mã hóa từ bản mã.

Sau khi thỏa mãn hai thuộc tính trên, một hệ thống mã hóa sẽ hoạt động tốt.

Mã hóa đồng hình: một thuộc tính đặc biệt ngẫu nhiên

Sau khi hiểu tất cả những gì về hệ thống mã hóa, chúng ta có thể chú ý đến bản mã này dường như là các ký tự bị cắt xén được tạo ngẫu nhiên. Tất cả chúng ta đều biết rằng chúng ta sẽ không nhận được bất kỳ thông tin nào nếu chỉ nhìn vào bản mã. Nhưng điều này có nghĩa là nếu không có khóa và chỉ có bản mã, chúng ta không thể làm gì?

Tất cả chúng ta đều biết câu trả lời: không thực sự.

Nhưng trong số nhiều thuật toán mã hóa, bản mã do một lớp thuật toán sinh ra có một tính chất đồng cấu đặc biệt: nếu dùng thuật toán mã hóa lấy được bản mã của số 1 thì ta được bản mã của số 2. Lúc này nếu cộng lại bản mã thì chính xác là bản mã!

Đối với tài sản này, chúng tôi gọi là đồng cấu phụ gia. Điều đó có nghĩa là, bản mã được mã hóa duy trì một mối quan hệ đại số tinh tế với văn bản gốc trước đó. Nếu chúng ta cộng các bản mã, chúng ta có thể nhận được bản mã mới sau khi cộng các văn bản gốc và mã hóa chúng. Theo cách tương tự, bên cạnh thuật toán đồng cấu cộng, còn có một thuật toán mã hóa với thuật toán đồng cấu nhân. Chúng ta có thể nhân bản mã được tạo bởi thuật toán đồng hình nhân, sau đó thu được bản mã tương ứng với kết quả của phép nhân giữa các văn bản gốc. Trong toàn bộ quá trình, chúng tôi không cần biết bất kỳ thông tin nào liên quan đến khóa, chúng tôi chỉ kết hợp bản mã trông giống như các mã bị cắt xén ngẫu nhiên.

Ví dụ: Hệ thống bỏ phiếu ẩn danh

Tiếp theo, hãy đưa ra một ví dụ để mô tả một cách sinh động tính thực tế của mã hóa đồng hình.

Tất cả chúng ta đều biết bỏ phiếu trực tuyến là như thế nào - nếu ông chủ của một công ty muốn bắt đầu làn sóng bỏ phiếu, hãy quyết định xem công ty có nên áp dụng hệ thống 996 hay không. Sau đó, ông chủ có thể yêu cầu CNTT thiết lập một máy chủ và để nhân viên đưa ra lựa chọn của riêng họ: bỏ phiếu 0 cho không, bỏ phiếu 1 cho đồng ý. Sau thời gian bỏ phiếu cuối cùng, ông chủ có thể cộng tất cả các phiếu bầu lại với nhau. Nếu tổng số phiếu cuối cùng vượt quá một nửa số nhân viên, công ty sẽ bắt đầu 996.

Cơ chế bỏ phiếu này có vẻ rất đơn giản, nhưng có một vấn đề lớn về quyền riêng tư: Nếu trong thâm tâm ông chủ muốn tất cả nhân viên đều 996, nhưng ông ta chỉ cố tình khởi xướng việc bỏ phiếu này để lừa đảo cơ quan thực thi pháp luật để xem nhân viên nào không muốn làm thêm giờ, thì ông chủ có thể âm thầm ủy thác cho em trai tôi nghe trộm Internet, ghi lại các lựa chọn do từng nhân viên đưa ra, cuối cùng xem ai bỏ phiếu 0. Kết quả là nhân viên rất sợ hãi và không dám tâm sự trong lòng.

Nếu chúng ta có thể sử dụng thuật toán mã hóa đồng hình phụ gia thì vấn đề này có thể được giải quyết dễ dàng.

Đầu tiên, CNTT có thể sử dụng thuật toán KeyGen để tạo một cặp khóa mã hóa và giải mã pk, sk, sau đó phân phối khóa chung cho từng nhân viên.

Sau đó, mỗi nhân viên mã hóa lựa chọn của mình (1 hoặc 0) thành bản mã thông qua thuật toán mã hóa, sau đó gửi bản mã đến máy chủ CNTT:

Cuối cùng, bộ phận CNTT có thể tổng hợp các lựa chọn của mọi người, lấy một bản mã kết hợp và gửi bản mã này cho sếp. Cuối cùng, ông chủ sử dụng khóa giải mã để mở bản mã và nhận được kết quả bình chọn cuối cùng:

Bằng cách này, chúng tôi đã hiện thực hóa thành công hệ thống kiểm phiếu với tính năng đồng cấu cộng tính và ngay cả khi ông chủ cử người theo dõi mạng, ông ấy chỉ có thể xem cti văn bản mã hóa được mã hóa và không có cách nào để biết mỗi phiếu bầu là gì người bình chọn cho. .

Đương nhiên, hệ thống này còn rất chưa hoàn thiện, ví dụ như bộ phận IT có thể trực tiếp giúp sếp giải mã phiếu bầu của mọi người và ghi thành văn bản. Có những công cụ mật mã khác có thể giúp chúng tôi giải quyết vấn đề này. Vì lý do không gian, tôi sẽ không giải thích ở đây.

Nhưng ở đây, chúng ta sẽ có thể cảm nhận được sức mạnh của thuật toán mã hóa đồng cấu. Ta có thể hiểu nôm na thế này: thông qua thuật toán mã hóa đồng cấu, người dùng có thể thực hiện một số loại tính toán ủy quyền an toàn (Secure Delegated Computation) với một máy chủ từ xa không tin cậy (đám mây). Người dùng có thể ủy thác đầu vào bảo mật nhạy cảm của họ cho đám mây thông qua công nghệ mã hóa đồng cấu, sau đó đám mây có thể thực hiện một mức độ tính toán nhất định trên dữ liệu được mã hóa và cuối cùng nhận được kết quả mã hóa mà người dùng muốn và trả lại cho người dùng. Cuối cùng, người dùng có thể sử dụng khóa giải mã để mở kết quả thu được. Trong suốt giao thức, hiệu trưởng (đám mây) không thể thấy bất kỳ thông tin hữu ích nào liên quan đến đầu vào riêng tư.

Phân loại hệ thống mã hóa đồng hình

Sau khi hiểu chung về hai tính chất đồng cấu cơ bản nhất, các khái niệm khác trở nên rất dễ hiểu. Từ quan điểm hệ thống, các hệ thống mã hóa đồng hình được chia thành bốn loại: đồng hình một phần, đồng hình gần đúng, đồng hình đầy đủ chuỗi hữu hạn và đồng hình hoàn toàn.

Tiếp theo, chúng ta hãy lần lượt xem xét các định nghĩa cụ thể của từng loại.

Mã hóa đồng hình một phần

Giai đoạn ban đầu của mã hóa đồng hình được gọi là mã hóa đồng hình từng phần Định nghĩa là bản mã chỉ có một đặc tính đồng hình. Giai đoạn này bao gồm hai chế độ đồng hình cộng và đồng hình nhân nhân mà chúng tôi đã mô tả ở trên.

Nếu chúng ta đặt nó vào kịch bản tính toán proxy an toàn đã đề cập trước đó, nếu chúng ta có đầu vào riêng tư và sau đó chúng ta hy vọng rằng đám mây có thể giúp chúng ta tính toán (x1, x2,...), thì chúng ta có thể sử dụng đám mây để tính toán những điều này input.hàm biểu diễn.

Nếu chúng ta có thể tính toán nó thông qua một thuật toán mã hóa đồng cấu phụ gia, điều đó có nghĩa là hàm này chỉ được chứa bất kỳ tổ hợp tuyến tính nào của các đầu vào riêng (các phép toán cộng). Một ví dụ hoạt động sẽ là nhân các đầu vào riêng với một hằng số và cộng chúng lại với nhau:

Nhưng nếu chúng ta muốn nhân hai đầu vào với nhau, thì thuật toán đồng hình bổ sung đã đề cập ở trên là vô ích. chỉ có thể là sự kết hợp tuyến tính của tất cả các đầu vào riêng.

Thuật toán mã hóa đồng cấu phụ gia phổ biến là thuật toán mã hóa ElGamal dựa trên nhóm tuần hoàn.

ElGamal là một thuật toán mã hóa khóa công khai rất thuận tiện dựa trên giao thức trao đổi khóa Diffie-Hellman, sử dụng các đặc điểm của các nhóm tuần hoàn. Vì lý do không gian, chúng tôi sẽ không giải thích chi tiết định nghĩa của các nhóm tuần hoàn ở đây, chúng tôi chỉ cần biết rằng mỗi nhóm có thể tìm thấy một trình tạo

Trình tạo này sau đó có thể được lũy thừa. Phương pháp triển khai mã hóa ElGamal đại khái như sau:

Lúc đầu, chúng tôi

Chúng tôi sẽ không chứng minh tính đúng đắn và an toàn của ElGamal. Nhưng sau khi xem phương pháp mã hóa của hệ thống mã hóa này, chúng ta có thể tìm thấy các đặc điểm đồng hình phụ gia tiềm năng của ElGamal vì chúng đều là hoạt động năng lượng.

Nguyên tắc tương tự cũng có thể được áp dụng cho thuật toán mã hóa đồng cấu nhân - chúng ta chỉ có thể nhân tất cả các đầu vào riêng với nhau, nhưng không có cách nào để thực hiện bất kỳ tổ hợp tuyến tính (cộng nào). Các ví dụ về phép đồng cấu nhân hóa thực sự rất phổ biến Mã hóa RSA mà tất cả chúng ta đều quen thuộc là một hệ thống đồng hình nhân nhân.

Phương pháp triển khai mã hóa RSA đại khái như sau:

Ta được bản mã tương ứng với phép nhân hai thông điệp này! Đây chính là bản chất đồng hình của phép nhân.Chúng ta có thể tiếp tục chồng các bản mã mới lên trên bản mã này, để có được bất kỳ phép nhân nào giữa các bản mã.

Mã hóa hơi đồng hình

Như chúng tôi đã nói trong đoạn trước, nếu chúng tôi muốn nhân các đầu vào riêng tư và thu được kết hợp tuyến tính giữa chúng, thì không thể hoàn thành thuật toán mã hóa đồng cấu từng phần đơn giản (RSA, ElGamal). Vì vậy, chúng ta cần phải đi đến giai đoạn tiếp theo.

Giai đoạn tiếp theo của mã hóa đồng hình một phần là mã hóa đồng hình xấp xỉ, đây là một bước gần hơn với mã hóa đồng hình hoàn toàn mà chúng tôi muốn đạt được. Nếu chúng ta có một thuật toán mã hóa đồng cấu gần đúng, thì chúng ta có thể đồng thời tính toán cộng và nhân trên bản mã. Nhưng cần lưu ý rằng vì giai đoạn này là xấp xỉ đồng cấu (Something Homomorphic) nên số phép cộng và phép nhân có thể thực hiện là rất hạn chế, và các hàm có thể tính toán cũng nằm trong một phạm vi giới hạn.

Không có nhiều ví dụ phổ biến ở giai đoạn này về mã hóa đồng cấu gần đúng, nếu chúng ta nói về ví dụ dễ hiểu nhất, thì nó nên dựa trên thuật toán mã hóa nhóm tuần hoàn ghép nối (Pairing).

Ở trên, chúng tôi đã thảo luận ngắn gọn về thuật toán mã hóa ElGamal dựa trên các nhóm tuần hoàn thông thường. Chúng ta đều biết rằng thuật toán này là đồng cấu bổ sung, có nghĩa là có thể thu được bất kỳ tổ hợp tuyến tính nào giữa các bản mã. Trong thực tế, trong một số nhóm tuần hoàn đặc biệt, chúng ta có thể tìm thấy một số tính chất đồng cấu nhân yếu.

Bằng cách này, chúng ta có được tích kết hợp giữa lũy thừa của hai giá trị đầu tiên được ngụy trang! Kết hợp với tính chất mà sức mạnh của hai giá trị có thể được kết hợp tuyến tính trong mã hóa ElGamal, thì chúng ta có được một hệ thống đồng cấu đầy đủ.

Trên thực tế, thực tế không đẹp như vậy, bởi vì tính chất đặc biệt của Ghép nối không xuất hiện trong tất cả các nhóm tuần hoàn. Vì vậy, nếu chúng ta nhân các giá trị trong hai nhóm có thể được ghép nối bằng cách ghép nối và ánh xạ chúng vào một nhóm mới, thì nhóm mới có thể không tìm thấy thuộc tính ghép nối tương ứng!

Điều đó có nghĩa là, với các nhóm tuần hoàn có thuộc tính Ghép nối, chúng ta chỉ có thể thực hiện các phép nhân rất hạn chế. Nếu nhóm hiện tại của chúng tôi hỗ trợ ghép nối, nhưng nhóm ánh xạ mới GT không hỗ trợ bất kỳ ghép nối nào, điều đó có nghĩa là nếu chúng tôi muốn thực hiện các hoạt động mã hóa đồng cấu dựa trên hệ thống hiện tại, mặc dù các chức năng có thể được vận hành có thể bao gồm bất kỳ kết hợp tuyến tính nào, nhưng nó chỉ có thể chứa tối đa một lớp phép nhân.

Hạn chế này chứng tỏ rằng hệ thống xấp xỉ đồng cấu, vì chúng ta không thể tính toán một hàm F có độ sâu và logic tùy ý.

Mã hóa đồng hình được phân cấp đầy đủ

Sau khi đạt đến giai đoạn tiếp theo, chúng ta tiến một bước gần hơn đến mục tiêu đồng hình hoàn toàn.

Giai đoạn này được gọi là mã hóa đồng hình đầy đủ chuỗi hữu hạn. Ở giai đoạn này, chúng ta đã có thể thực hiện bất kỳ tổ hợp cộng và nhân nào trên bản mã mà không có bất kỳ giới hạn nào về số lần.

Nhưng lý do tại sao nó được gọi là đồng cấu chuỗi hữu hạn là thuật toán ở giai đoạn này sẽ đưa ra một khái niệm mới về giới hạn trên của độ phức tạp L, hạn chế độ phức tạp của hàm F. Nếu chúng ta có thể biểu thị nó trong mạch nhị phân C, thì độ sâu và kích thước phải nằm trong phạm vi của L, cụ thể là:

Nói cách khác, nếu L tương đối lớn, thì chúng ta có thể thực hiện nhiều phép toán đồng hình đơn giản hơn (độ phức tạp thấp). Thuật toán mã hóa đồng cấu chuỗi hữu hạn cũng là nền tảng của giai đoạn tiếp theo của mã hóa đồng cấu hoàn toàn, khi chúng ta nhận ra đồng cấu hoàn toàn trong độ phức tạp, thì việc hiện thực hóa đồng cấu hoàn toàn không còn xa nữa.

Chúng ta có thể hiểu giới hạn trên L của độ phức tạp này đến từ đâu. Trước hết, chúng ta có thể hình dung rằng nếu có một thuật toán mã hóa đồng hình hoàn toàn thì bất kỳ phép toán cộng và nhân nào cũng có thể thực hiện được trên bản mã. Tuy nhiên, thuật toán này sẽ thêm một lượng nhiễu ngẫu nhiên nhất định vào bản mã khi mã hóa.

Khi nhiễu nằm trong phạm vi có thể kiểm soát, thuật toán giải mã có thể dễ dàng khôi phục văn bản gốc từ văn bản mật mã. Nhưng khi chúng ta xếp chồng các bản mã lại với nhau để tính toán đồng hình, tiếng ồn trong mỗi bản mã sẽ được chồng lên và phóng to. Nếu chúng ta chỉ thực hiện logic tương đối đơn giản trên bản mã, thì nhiễu chồng chất vẫn nằm trong phạm vi chấp nhận được. Nhưng nếu chúng ta xếp các bản mã lại với nhau quá phức tạp, một khi phạm vi nhiễu vượt quá giá trị tới hạn, văn bản gốc sẽ bị ghi đè hoàn toàn, dẫn đến việc giải mã không thành công.

Mã hóa đồng hình hoàn toàn (FHE)

Sau rất nhiều cuộc gọi, cuối cùng chúng tôi cũng đến với mã hóa đồng cấu hoàn toàn (FHE) mà chúng tôi đang chờ đợi.

Khi chúng tôi đạt đến giai đoạn này, tính toán proxy an toàn đã nói ở trên sẽ trở nên khả thi. Nếu chúng tôi có thể tìm thấy một hệ thống mã hóa đồng cấu hoàn toàn hiệu quả cao, chúng tôi có thể ủy quyền tất cả máy tính cục bộ lên đám mây một cách an toàn mà không làm rò rỉ bất kỳ dữ liệu nào!

tiêu đề phụ

Định nghĩa về hệ thống mã hóa đồng hình hoàn toàn

Trước khi bắt đầu thảo luận về lịch sử của các hệ thống đồng cấu đầy đủ dưới đây, chúng ta có thể xác định một cách hệ thống định nghĩa chính thức của các hệ thống đồng cấu đầy đủ. Một hệ thống mã hóa đồng cấu hoàn toàn có tổng cộng bốn thuật toán:

tiêu đề phụ

Thuộc tính của hệ thống mã hóa đồng hình hoàn toàn

Bây giờ chúng ta hãy xem xét các thuộc tính của hệ thống này (Properties). Đầu tiên, hệ thống phải chính xác.

Nghĩa là, nếu ta chọn tùy ý một mạch F, và tùy ý chọn một tập các tin nhắn gốc m1,m2,.... Nếu chúng ta có khóa được tạo bởi thuật toán KeyGen lúc đầu, thì:

Thứ hai, hệ thống cần phải an toàn về mặt ngữ nghĩa. Chúng tôi đã giải thích định nghĩa này ở trên.

Cuối cùng, để làm cho hệ thống mã hóa đồng cấu hoàn toàn trở nên thiết thực, chúng ta phải thêm một yêu cầu bổ sung: tính gọn nhẹ.

Tại sao chúng ta cần thêm tính năng ngắn gọn này? Bởi vì nếu không có yêu cầu này, chúng ta có thể dễ dàng tạo ra một hệ thống đồng cấu hoàn toàn vô nghĩa (gian lận):

Nếu không hạn chế kích thước đầu ra của Eval, thì sau khi chúng ta lặp đi lặp lại chồng Eval nhiều lần, kích thước của bản mã thu được sẽ ngày càng lớn hơn. Cuối cùng khi giải mã, bạn chỉ cần giải mã tất cả các bản mã gốc, rồi tính toán nó. Điều này giống như một người dùng mã hóa thông tin sức khỏe của mình và yêu cầu bệnh viện phán đoán xem anh ta có bị bệnh hay không. Bệnh viện gửi lại bản mã nguyên vẹn, sau đó gửi lại toàn bộ mô hình dữ liệu cộng với sách y khoa của anh ta. Nó có nghĩa giống như nói người dùng mà bạn nên tự tính toán.

Loại hệ thống đồng cấu hoàn toàn này còn có một nhược điểm lớn hơn, đó là bản mã cuối cùng không thể che đậy hoàn toàn các chi tiết cụ thể của mạch hoạt động F. Trong kịch bản sử dụng bệnh viện này, có thể tài sản quý giá nhất của bệnh viện là hệ thống phân tích dữ liệu này. Nếu bạn gửi lại F của mình cho người dùng một cách vô ích, thì thành quả lao động chăm chỉ của bạn sẽ dễ dàng bị người khác đánh cắp.

Tóm lại, chỉ cần đáp ứng đủ ba yếu tố chính xác, bảo mật ngữ nghĩa và ngắn gọn, chúng ta sẽ có một hệ thống mã hóa đồng cấu đầy đủ không tầm thường.

tiêu đề phụ

Đánh giá lịch sử về mã hóa đồng hình hoàn toàn

Trước khi bắt đầu tìm hiểu cách triển khai thuật toán mã hóa đồng cấu hoàn toàn, chúng ta cũng có thể xem khái niệm mã hóa đồng cấu hoàn toàn ra đời như thế nào.

Khái niệm về FHE (đồng cấu hoàn toàn) đã thực sự được đề xuất vào cuối những năm 1970. Năm 1978, trong bài báo On Data Banks and Privacy Homomorphisms, Rivest, Adleman và Dertouzos, một số tên tuổi lớn trong lĩnh vực mật mã, lần đầu tiên đề cập đến khái niệm về một hệ thống có thể thực hiện một số tính toán nhất định trên bản mã và hoạt động gián tiếp trên văn bản gốc. Sau đó, ý tưởng này được đúc kết lại và đặt tên là mã hóa đồng cấu đầy đủ.

Có thể thấy khái niệm mã hóa đồng cấu hoàn toàn đã được đề xuất từ ​​lâu. Đáng ngạc nhiên là vào năm 1976, hai năm trước khi bài báo được xuất bản, giao thức trao đổi khóa Diffle-Hellman chỉ mới được đề xuất! Có thể thấy trí tưởng tượng về lĩnh vực cơ yếu còn rất phong phú.

Khi khái niệm về FHE được đề xuất, toàn bộ cộng đồng học thuật đã bị lay động bởi nó và bắt đầu cuộc tìm kiếm kéo dài hàng thập kỷ, cố gắng tìm ra một thuật toán hoàn hảo với các thuộc tính đồng hình hoàn toàn. Nhưng trong vài thập kỷ qua, mọi người đã thử tất cả các tùy chọn có thể tưởng tượng được, nhưng họ không thể tìm thấy tùy chọn nào có thể đáp ứng tất cả các điều kiện của đồng cấu đầy đủ và có thể dễ dàng xác minh tính bảo mật của nó.

Cho đến năm 2009, tiến sĩ Craig Gentry, đang theo học tại Stanford, chợt lóe lên một cảm hứng và đột phá những khó khăn của thuật toán FHE. Trong luận án tiến sĩ của mình, lần đầu tiên ông đưa ra một hệ thống mã hóa đồng hình hoàn toàn hợp lý và an toàn! Hệ thống này dựa trên giả định về một mạng tinh thể lý tưởng. Hệ thống mã hóa đồng cấu đầy đủ do Gentry09 đề xuất thường được gọi là hệ thống mã hóa đồng cấu hoàn toàn thế hệ thứ nhất.

Trong bài báo của Gentry, ông cũng đề cập đến một khái niệm quan trọng gọi là Bootstrapping. Bootstrapping là một kỹ thuật xử lý đặc biệt đối với bản mã, sau khi xử lý, nó thực sự có thể "làm mới" một bản mã có độ nhiễu gần với giá trị tới hạn thành một bản mã mới có độ nhiễu rất thấp. Thông qua Bootstrapping, nhiễu của một hệ thống chuỗi hữu hạn không bao giờ có thể vượt quá giá trị tới hạn, do đó trở thành một hệ thống đồng hình hoàn toàn. Bằng cách này, chúng ta có thể tính toán đồng hình bất kỳ kích thước nào.

Sau bước đột phá lớn của Gentry, toàn bộ thế giới tiền điện tử lại rơi vào tình trạng điên loạn và mọi người bắt đầu tranh giành để tìm ra một hệ thống đồng hình hoàn toàn linh hoạt và hiệu quả hơn dựa trên ý tưởng của Gentry.

Vào năm 2011, hai ông lớn Brakerski và Vaikuntanathan đã đề xuất một hệ thống mã hóa đồng hình hoàn toàn mới, dựa trên Learning With Errors (LWE), một giả định khác về mã hóa mạng. Cũng trong năm đó, Brakerski, Gentry và Vaikuntanathan đã cùng nhau hoàn thiện hệ thống và chính thức xuất bản nó. Hệ thống đồng hình đầy đủ mà họ phát minh ra được gọi tắt là hệ thống BGV. Hệ thống BGV là một hệ thống mã hóa đồng hình với chuỗi giới hạn, nhưng nó có thể được chuyển thành một hệ thống đồng hình hoàn toàn bằng Bootstrapping. Hệ thống BGV sử dụng giả định LWE thực tế hơn hệ thống do Gentry09 đề xuất. Nói chung, chúng tôi gọi hệ thống BGV là hệ thống mã hóa đồng hình hoàn toàn thế hệ thứ hai.

Sau năm 2013, thế giới tiền điện tử về cơ bản đã nở rộ. Dựa trên hệ thống đồng cấu hoàn toàn ba thế hệ ban đầu, nhiều thiết kế mới đã xuất hiện để tối ưu hóa và tăng tốc hiệu quả hoạt động của các hệ thống BGV và GSW. IBM đã phát triển một thư viện điện toán đồng cấu hoàn toàn mã nguồn mở HElib dựa trên hệ thống BGV và thư viện này đã được chuyển thành công sang các nền tảng di động lớn. Đồng thời, có một dự án mã nguồn mở khác là TFHE cũng rất đáng chú ý. TFHE dựa trên hệ thống GSW, và nhiều cải tiến và tăng tốc khác nhau đã được thêm vào, và nó hiện đã rất nổi tiếng.

Ngoài việc phát triển các thư viện đồng cấu hoàn toàn truyền thống, nhiều nhóm cũng đang nghiên cứu cách tăng tốc tốt hơn việc tính toán các thuật toán mã hóa đồng cấu hoàn toàn thông qua phần cứng không đồng nhất như GPU, FPGA và ASIC. Ví dụ: cuFHE là một hệ thống mã hóa đồng hình hoàn toàn được tăng tốc bởi GPU dựa trên CUDA nổi tiếng.

Theo quan điểm ngày nay, có vẻ như đã 11 năm trôi qua kể từ khi Gentry gõ cửa hệ thống đồng hình hoàn toàn. Bây giờ ngành công nghiệp có rất nhiều nghiên cứu về FHE và nhiều người đang nghiên cứu các hệ thống đồng cấu hoàn toàn từ các góc độ và yêu cầu ứng dụng khác nhau. Cho đến hôm nay, chúng ta đã có nhiều phương thức triển khai FHE khả thi, nhưng điều mà mọi người vẫn đang theo đuổi là hiệu quả vận hành của hệ thống FHE. Lấy thư viện FHE tiên tiến hiện tại làm ví dụ, có thể mất hàng chục mili giây hoặc hàng chục giây để tính toán đồng hình một số logic tương đối đơn giản trên nền tảng di động. Các đơn vị thời gian này cực kỳ chậm đối với hệ thống máy tính.

Làm thế nào để hệ thống FHE chạy hiệu quả hơn trên các nền tảng không đồng nhất vẫn là một bí ẩn chưa có lời giải. Nếu vấn đề này được giải quyết, sẽ là một tương lai trong tầm tay để biến mọi tính toán của máy tính thành đồng cấu hoàn toàn và tác nhân thực hiện các phép tính trên đám mây của bên thứ ba.

tiêu đề phụ

Mối quan hệ giữa FHE và MPC

MPC thực sự là một lĩnh vực rất nổi tiếng đã được nghiên cứu trong một thời gian dài. Kể từ khi nhà mật mã học Yao Zhizhi tung ra Mạch bị cắt xén của mình vào thế kỷ trước, lĩnh vực MPC đã được công nhận rộng rãi và đã có nhiều bước đột phá. Bây giờ chúng tôi có rất nhiều thư viện MPC có thể được sử dụng và chúng cũng có hiệu quả hoạt động nhất định.

Nếu bạn biết MPC, bạn có thể có nhiều câu hỏi sau khi xem lịch sử khó khăn của hệ thống mã hóa đồng cấu hoàn toàn: Tại sao bạn không thể trực tiếp thay thế mã hóa đồng cấu hoàn toàn bằng giao thức MPC?

Thật vậy, một giao thức MPC hoàn toàn có thể thay thế một giao thức FHE. Chúng ta chỉ cần sử dụng người dùng và đầu vào riêng tư làm một bên trong một giao thức, sau đó sử dụng máy chủ tính toán proxy từ xa làm một bên khác, đáp ứng các điều kiện để thực hiện giao thức MPC.Chỉ thông qua một số tương tác nhất định, tính toán proxy mới có thể được thực hiện đã nhận ra. Và máy chủ cũng không thấy đầu vào riêng tư.

Nhưng có một điểm rất quan trọng mà chúng ta bỏ qua: vì MPC có tính tương tác nên nó cần người dùng và máy chủ tính toán và giao tiếp với nhau để hoàn thành thỏa thuận. Điều này cũng xung đột với yêu cầu cơ bản nhất của tính toán proxy FHE. Nếu người dùng cần luôn trực tuyến để hoàn thành thỏa thuận mọi lúc và cũng trả một phần sức mạnh tính toán, thì việc tính toán hoàn toàn không phải là "ủy quyền" và hai bên chỉ thực hiện nhiều phép tính hơn để bảo mật thông tin . Điều này cũng giải thích tại sao lĩnh vực MPC đã có những bước đột phá lớn, nhưng lĩnh vực FHE vẫn là ẩn số, bởi hai hệ thống giải quyết các vấn đề hoàn toàn khác nhau.

tiêu đề phụ