Microsoft SEAL và Bình minh của Mã hóa Đồng hình

Mặc dù mã hóa đồng cấu đầy đủ (FHE) ban đầu đã đạt được vào năm 2009, nhưng giờ đây nó bắt đầu nhận được nhiều sự chú ý hơn khi sức mạnh tính toán đã bắt kịp nhu cầu tính toán của nó; tuy nhiên, mục tiêu của mã hóa đồng cấu đã có từ một thập kỷ trước.

Một tìm kiếm lướt qua sẽ tìm thấy nhiều định nghĩa cho nó. Đây là cách trực tiếp và ngắn gọn nhất:

Một dạng mã hóa cho phép tính toán trên bản mã tạo ra kết quả được mã hóa mà khi được giải mã sẽ khớp với kết quả của các thao tác như thể chúng đã được thực hiện trên bản rõ.

— Massimo Bertaccini ( Thuật toán mật mã )

Hãy xem xét tuyên bố đó trong giây lát. Mã hóa đồng cấu cho phép các thao tác được thực hiện trên các giá trị được mã hóa sao cho các kết quả được giải mã tạo ra kết quả của các thao tác như thể chúng được thực hiện trên các giá trị không được mã hóa ban đầu. Đề cập sớm nhất mà tôi tìm thấy là On Data Banks and Privacy Homomorphisms (1978), trong đó các tác giả đang cố gắng ngăn không cho các lập trình viên hệ thống truy cập dữ liệu tài chính nhạy cảm được lưu trữ trong hệ thống tại chỗ bằng cách sử dụng dịch vụ chia sẻ thời gian từ xa.

Dữ liệu tài chính nhạy cảm được lưu trữ trong ngân hàng dữ liệu. Các dịch vụ chia sẻ thời gian tính toán dữ liệu không thực hiện bảo mật đầy đủ. Các lập trình viên hệ thống có quyền truy cập vào dữ liệu tài chính. Bài báo viết:

Sử dụng một đồng hình riêng tư đặc biệt để mã hóa dữ liệu của nó sao cho máy tính chia sẻ thời gian có thể hoạt động trên dữ liệu mà không cần phải giải mã trước.

Nói cách khác, tôi muốn xóa quá trình xử lý dữ liệu của mình mà không cấp quyền truy cập vào dữ liệu đó.

Nói cách khác, hàm(A, B) = hàm (A , B ) trong đó A  and B lần lượt là các giá trị được mã hóa của A và B. Điều này cho phép các bên thứ ba tính toán dữ liệu được mã hóa và cung cấp kết quả mà không cần biết về giá trị ban đầu. Với RSA, hai giá trị được mã hóa bằng cùng một khóa có thể được nhân lên và sản phẩm có thể được giải mã mang lại sản phẩm của các giá trị được mã hóa.

Lấy 5_6 bằng RSA(5)_RSA(6):

1. RSA(5) = (5^17) chế độ 3233 = 3096

2. RSA(6) = (6^17) chế độ 3233 = 824

3. 3096*824 = 254864

4. RSA^-1(254864) = 254864^2753 (chế độ 3233) = 30

5. 5*6 = 30

   
   

Tuy nhiên, điều này không hoạt động để bổ sung. RSA là lược đồ Mã hóa đồng hình một phần (PHE) ở chỗ nó chỉ hỗ trợ phép nhân. Dòng thời gian bên dưới hiển thị tiến trình từ các lược đồ (PHE) thông qua Mã hóa Đồng hình Phần nào (SHWE) cho phép kết hợp hạn chế phép cộng và phép nhân. Các hoạt động này có thể được lặp lại tối đa năm lần trước khi đạt được kết quả không hợp lệ. Sau đó, lược đồ FHE đầu tiên của Craig Gentry ra đời, cho phép cộng và nhân lặp đi lặp lại mà không làm giảm độ trung thực.

Thư viện mã hóa đồng hình

Kể từ năm 2009, các chương trình và thư viện FHE đã phát triển nhanh chóng.

Microsoft SEAL (Thư viện số học được mã hóa đơn giản) được phát triển trong C++ 17 cùng với trình bao bọc C#. Được phát hành lần đầu vào năm 2015, nó vẫn đang được phát triển tích cực. Kho lưu trữ github bao gồm các ví dụ C# chuyên sâu nên được khám phá nếu bạn muốn tìm hiểu sâu hơn.

Các sơ đồ này được hỗ trợ bởi SEAL và bao gồm các phép toán đồng hình để cộng, chia, trừ và lũy thừa, nhưng không chia.

• Brakerski-Gentry-Vaikuntanathan (BGV)/Fan-Vercauteren (BFV)

  
  

  • Số nguyên (dài)

  • Sử dụng nếu độ chính xác là một yêu cầu

  • Tính toán chậm hơn CKKS

  • Các giá trị được mã hóa bằng BGV có thể được sử dụng với các giá trị được mã hóa bằng BFV

  • Không thể sử dụng các giá trị được mã hóa bằng BGV/BVF với các giá trị được mã hóa bằng CKKS

  • Xem lại các lược đồ mã hóa đồng hình cho các trường hữu hạn

    
    

• Cheon-Kim-Kim-Song (CKKS)

  
  

  • Điểm nổi (gấp đôi)
  • Sử dụng nếu độ chính xác là không cần thiết
  • Không thể sử dụng các giá trị được mã hóa bằng CKKS với các giá trị được mã hóa bằng BGV/BFV
  • Tính toán nhanh hơn BFV/BGF

Mã hóa và tính toán với Microsoft SEAL

Những ví dụ này sử dụng gói Microsoft.Research.SEALNet Nuget và lược đồ CKKS. Các thiết bị theo dõi sức khỏe, như FitBit và AppleHeath, yêu cầu từ bỏ một số quyền riêng tư. Họ thu thập thông tin cá nhân như số bước và tọa độ địa lý của chuyển động của người đeo, tần số nhịp tim và các số liệu thống kê quan trọng khác. Với mã hóa đồng hình, các công cụ tổng hợp chỉ số sức khỏe này vẫn có thể hoạt động trên dữ liệu của chúng tôi mà không cần truy cập vào dữ liệu thô.

Trong ví dụ đơn giản này, khách hàng sẽ gửi các chỉ số chạy bao gồm khoảng cách và thời gian. Máy chủ tổng hợp dữ liệu được mã hóa và tính toán tốc độ trung bình.

Để bắt đầu, một khóa công khai được tạo bởi máy khách và chia sẻ với máy chủ. Nó được sử dụng để mã hóa dữ liệu và cũng để thực hiện các phép tính số học trên dữ liệu được mã hóa. Cả máy khách và máy chủ đều sử dụng Bộ mã hóa. Máy khách tạo và giữ lại một khóa riêng được sử dụng để giải mã được sử dụng bởi Decryptor có tên thích hợp.

Một bên độc hại chặn dữ liệu có thể sử dụng khóa chung trên dữ liệu được mã hóa và trả lại cho người gọi bằng cách giả mạo máy chủ. Máy chủ sẽ ký kết quả và máy khách sẽ xác minh chữ ký để đảm bảo nó được trả về từ một bên đáng tin cậy.

 using Microsoft.Research.SEAL; protected SEALContext _context; private KeyGenerator _keyGenerator; private Encryptor _encryptor; private Decryptor _decryptor; protected IFitnessTrackerApiClient _apiClient; . . . _context = SEALUtils.GetContext(_config.Value.PolyModulusDegree, this.SchemeType); _keyGenerator = new KeyGenerator(_context); _keyGenerator.CreatePublicKey(out PublicKey publicKey); _keyGenerator.CreateRelinKeys(out RelinKeys relinKeys); _encryptor = new Encryptor(_context, _publicKey); _decryptor = new Decryptor(_context, _keyGenerator.SecretKey); . . . PublicKeyModelCKKS keyModelCKKS = new( SEALUtils.KeyToBase64String(_publicKey), SEALUtils.KeyToBase64String(relinKeys)); await _apiClient.SendPublicKeyCKKSAsync(keyModelCKKS);

Các khóa tái tuyến tính hóa được chuyển từ máy khách sang máy chủ. Theo Microsoft SEAL, chúng không có ý nghĩa ngữ nghĩa nào khác ngoài việc giảm kích thước của Bản mã sau thao tác nhân.

Tại dòng lệnh, người dùng nhập thời gian và khoảng cách.

Mỗi giá trị được mã hóa thành PlainText, sau đó được mã hóa thành Ciphertext và cuối cùng được mã hóa thành base64 trước khi gửi đến máy chủ.

 using Microsoft.Research.SEAL; var plaintext = new Plaintext(); _encoder.Encode(value, _scale, plaintext); var ciphertext = new Ciphertext(); _encryptor.Encrypt(value, ciphertext); using (var ms = new MemoryStream()) { ciphertext.Save(ms); return Convert.ToBase64String(ms.ToArray()); }

Vì các sơ đồ mã hóa đồng hình không hỗ trợ phân chia (CKKS cũng không ngoại lệ), máy khách cần hỗ trợ máy chủ. Công thức cho tốc độ là:

• khoảng cách/thời gian

  
  

Một cách khác để viết nó là,

• khoảng cách * (1/lần)

  
  

Vì vậy, khách hàng gửi:

 RunItemCKKS metricsRequest = new( EncryptBase64(runItem.Distance), EncryptBase64(runItem.Time), EncryptBase64(1 / runItem.Time)); await _apiClient.AddNewRunningDistanceCKKSAsync(metricsRequest);

Máy chủ thực hiện chức năng khởi động tương tự tạo SEALContext chỉ sử dụng khóa chung và khóa tuyến tính hóa lại, sau đó xử lý yêu cầu:

 var distance = SEALUtils.BuildCiphertextFromBase64String(request.Distance, _sealContext); var time = SEALUtils.BuildCiphertextFromBase64String(request.Time, _sealContext); var timeReciprocal = SEALUtils.BuildCiphertextFromBase64String(request.TimeReciprocal, _sealContext); Ciphertext speed = new(); _evaluator.Multiply(distance, timeReciprocal, speed); _evaluator.RelinearizeInplace(speed, _relinKeys); _runListCKKS.Add(new EncryptedRunInfoCKKS(distance, time, speed));

Nghịch đảo của thời gian được sử dụng để tính toán tốc độ cho lần chạy đã gửi và phương pháp RelinearizeInplace giảm kích thước của Bản mã kết quả . Khoảng cách, thời gian và tốc độ được lưu vào Danh sách trong bộ nhớ.

Phương thức GetMetrics tổng hợp danh sách và trả về:

• tổng số lần chạy

• tổng khoảng cách

• Tổng thời gian

• tốc độ trung bình

  
  

   public SummaryItemCKKS GetMetrics() { int count = _runListCKKS.Count; var totalDistanceCKKS = SumEncryptedValues(_runListCKKS.Select(m => m.Distance)); var totalTimeCKKS = SumEncryptedValues(_runListCKKS.Select(m => m.Time)); var totalSpeed = SumEncryptedValues(_runListCKKS.Select(m => m.Speed)); . . . protected Ciphertext SumEncryptedValues(IEnumerable<Ciphertext> encryptedData) { . . . Ciphertext encTotal = new(); _evaluator.AddMany(encryptedData, encTotal); return encTotal; . . . }

  
  

Để có được tốc độ trung bình, nghịch đảo của số đếm được sử dụng, thay vì sử dụng:

(tổng tốc độ)/số hoặc lần chạy chúng tôi sử dụng:

(tổng tốc độ) * (1/số lần chạy)

Vì máy chủ theo dõi số lần gửi lần chạy nên tổng số lần chạy không phải là giá trị được mã hóa. Giá trị không được mã hóa đó có thể được chuyển đổi thành Văn bản gốc và được sử dụng trong một thao tác được thực hiện trên Bản mã. Mặc dù đây là một ví dụ đơn giản, nhưng ý nghĩa rất đáng chú ý. Máy chủ có thể cung cấp các giá trị bổ sung được sử dụng trên dữ liệu được mã hóa, cho phép các nhà cung cấp bên thứ ba áp dụng dữ liệu độc quyền để tính toán đối với dữ liệu được mã hóa do khách hàng cung cấp.

Trong ví dụ bên dưới, tổng số đếm được chuyển đổi thành số nghịch đảo và được thêm vào Danh sách<double>. Hoạt động CKKS yêu cầu các giá trị danh sách được mã hóa, ngay cả khi danh sách chỉ chứa một giá trị. Vì vậy, List<double> được mã hóa thành PlainText . MultiplyPlainInplace nhân tổng Tốc độ với (1/số lần chạy) dẫn đến tốc độ trung bình. Để tiết kiệm không gian, kết quả được áp dụng cho TotalSpeed Ciphertext và các phím tuyến tính hóa lại làm giảm kích thước của đầu ra.

 Plaintext encodedCountReciprocal = new(); List<double> averagePaceList = new(); double runCountReciprocal = 1 / (double)count; averagePaceList.Add(runCountReciprocal); _encoder.Encode(averagePaceList, _scale, encodedCountReciprocal); _evaluator.MultiplyPlainInplace(totalSpeed, encodedCountReciprocal); _evaluator.RelinearizeInplace(totalSpeed, _relinKeys);

Các giá trị được mã hóa, trả về và giải mã base64 trên máy khách. Máy khách thực hiện thêm bước chuyển đổi Bản rõ đã được giải mã thành Danh sách<double> .

 var payload = Convert.FromBase64String(encryptedDistanceText); using var ms = new MemoryStream(payload); var ciphertext = new Ciphertext(); ciphertext.Load(_context, ms); var decryptedText = new Plaintext(); _decryptor.Decrypt(cypherText, decryptedText); List<double> distanceList = new(); _encoder.Decode(decryptedText, distanceList);

Việc gửi các giá trị sau mang lại tổng số và tốc độ trung bình được tính toán bởi một dịch vụ lập bảng tổng số và trung bình mà không cần giải mã dữ liệu được gửi từ ứng dụng khách.

Máy chủ tính toán dữ liệu và trả về tổng số lần chạy, khoảng cách, thời gian và tốc độ mà không cần giải mã bất kỳ dữ liệu nào được gửi.

Tóm lược

Microsoft SEAL là một dự án Nghiên cứu của Microsoft và chưa sẵn sàng cho ứng dụng sản xuất. Tất cả các lớp triển khai tài nguyên không được quản lý và sử dụng IDisposable . Mã sản xuất sẽ cần bảo vệ chống rò rỉ bộ nhớ. Lớp SEALContext không tuân theo nguyên tắc trách nhiệm duy nhất. Nó bao gồm các phương thức cho cả BGV/BVF và CKKS. Hơn nữa, CKKS hỗ trợ các phép toán vectơ, nhưng không hỗ trợ phép cộng vectơ. Một Danh sách đơn lẻ<double> có thể được mã hóa thành một Văn bản mật mã duy nhất nhưng không có phương tiện nào để tính tổng các giá trị trong một Văn bản mật mã duy nhất . Nó có thể được thực hiện với phép quay vectơ , nhưng đó là một giải pháp dưới mức tối ưu.

Mẫu mã Fitness Tracker này là phần giới thiệu đơn giản về một chủ đề phức tạp. Có một số trường hợp sử dụng hấp dẫn với logic liên quan hơn:

• Phát hiện gen đánh dấu

• Bảo vệ mẫu sinh trắc học

• An toàn giám sát con người để lão hóa tại chỗ

• Phát hiện gian lận thẻ tín dụng

  
  

Mã hóa đồng cấu phần lớn đã được sử dụng trong giới học thuật và trong các nguyên mẫu. Các ứng dụng thực tế đã bị hạn chế bởi khả năng tính toán theo yêu cầu của các sơ đồ mã hóa đồng hình. Khả năng tăng tốc GPU và bộ xử lý ASIC sẽ tiếp tục làm xói mòn rào cản này. Intel đang phát triển Bộ tăng tốc phần cứng FHE , được xây dựng có mục đích cho các sơ đồ mã hóa đồng hình, với sự cộng tác của Microsoft và DARPA. NASDAQ cũng đang tài trợ cho một dự án R&D sử dụng mã hóa đồng hình với máy học để phát hiện gian lận. Cộng đồng FHE.org là một nguồn tài nguyên tuyệt vời cho những phát triển mới nhất trong không gian này. Nó có một máy chủ Discord đang hoạt động.

Tất cả các mẫu mã trong bài viết này đều có sẵn tại johniwasz/microsoft-seal-samples . Để biết thêm chi tiết về ví dụ Microsoft SEAL, hãy xem các ví dụ .NET này.

Cũng được xuất bản ở đây.