Microsoft SEAL 和同态加密的黎明

虽然全同态加密 (FHE) 最初是在 2009 年实现的，但随着计算能力已经赶上其计算需求，它开始受到更多关注；然而，同态加密的目标可以追溯到十年前。

粗略搜索会找到它的多个定义。这是最直接简洁的：

一种加密形式，允许对密文进行计算，生成加密结果，解密后与操作结果相匹配，就好像它们是在明文上执行的一样。

— Massimo Bertaccini（ 密码算法）

考虑一下该声明。同态加密使得能够对加密值执行操作，使得解密结果产生操作结果，就好像它们是对原始未加密值执行的一样。我发现的最早提及是关于数据库和隐私同态（1978 年），其中作者试图防止系统程序员使用远程分时服务访问存储在本地系统中的敏感财务数据。

敏感的财务数据存储在数据库中。计算数据的分时服务没有实现足够的安全性。系统程序员可以访问财务数据。该论文指出：

使用特殊的隐私同态加密其数据，使分时计算机无需先解密即可对数据进行操作。

换句话说，我想在不放弃访问权限的情况下删除对我的数据的处理。

换句话说， function(A, B) = function (A , B ) 其中 A  and B分别是 A 和 B 的加密值。这使第三方能够计算加密数据并在不知道原始值的情况下提供结果。使用 RSA，可以将使用相同密钥加密的两个值相乘，并且可以解密乘积以产生加密值的乘积。

使用RSA(5)_RSA(6)得到5_6：

1. RSA(5) = (5^17) 模 3233 = 3096

2. RSA(6) = (6^17) mod 3233 = 824

3. 3096*824 = 254864

4. RSA^-1(254864) = 254864^2753 (mod 3233) = 30

5. 5*6 = 30

   
   

但是，这不适用于加法。 RSA 是一种部分同态加密 (PHE) 方案，因为它仅支持乘法。下面的时间线显示了从 (PHE) 方案到允许加法和乘法的有限组合的某种同态加密 (SHWE) 的进展。在达到无效结果之前，这些操作最多可以重复五次。随后出现了Craig Gentry的第一个 FHE 方案，该方案能够在不损失保真度的情况下重复加法和乘法。

同态加密库

自 2009 年以来，FHE 计划和图书馆激增。

Microsoft SEAL（简单加密算法库）是在 C++ 17 中与 C# 包装器一起开发的。最初于 2015 年发布，目前仍在积极开发中。 github 存储库包含深入的 C# 示例，如果您有兴趣进一步研究，应该探索这些示例。

这些方案由 SEAL 支持，包括加法、除法、减法和取幂的同态运算，但不包括除法。

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

  
  

  • 整数（长）

  • 如果需要精度，则使用

  • 计算比CKKS慢

  • 使用 BGV 加密的值可以与使用 BFV 加密的值一起使用

  • 使用 BGV/BVF 加密的值不能与使用 CKKS 加密的值一起使用

  • 重温有限域的同态加密方案

    
    

• Cheon-Kim-Kim-Song (CKKS)

  
  

  • 浮点数（双）
  • 如果不需要精度则使用
  • 使用 CKKS 加密的值不能与使用 BGV/BFV 加密的值一起使用
  • 计算速度比 BFV/BGF 快

使用 Microsoft SEAL 进行加密和计算

这些示例使用Microsoft.Research.SEALNet Nuget 包和 CKKS 方案。像 FitBit 和 AppleHeath 这样的健康追踪器需要放弃一些隐私。他们收集个人信息，如步数和佩戴者运动的地理坐标、心跳频率和其他重要统计数据。通过同态加密，这些健康指标聚合器仍然可以在不访问原始数据的情况下对我们的数据进行操作。

在这个简单的示例中，客户端发送包括距离和时间在内的跑步指标。服务器聚合加密数据并计算平均速度。

首先，公钥由客户端创建并与服务器共享。它用于加密数据，也用于对加密数据进行算术运算。客户端和服务器都使用加密器。客户端生成并保留用于解密的私钥，该私钥由恰当命名的Decryptor使用。

拦截数据的恶意方可以使用加密数据的公钥，并通过欺骗服务器将其返回给调用者。服务器应该对结果进行签名，而客户端应该验证签名以确保它是从可信方返回的。

 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);

再线性化密钥从客户端传递到服务器。根据 Microsoft SEAL，除了减少乘法运算后的密文大小外，它们没有任何语义意义。

在命令行，用户输入时间和距离。

每个值都被编码为PlainText，然后加密为Ciphertext ，最后在将其发送到服务器之前编码为 base64。

 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()); }

由于同态加密方案不支持除法（CKKS也不例外），客户端需要给服务端一个协助。速度公式为：

• 距离/时间

  
  

另一种写法是，

• 距离 * (1/次)

  
  

因此，客户端发送：

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

服务器执行类似的引导功能，仅使用公钥和重新线性化密钥创建SEALContext ，然后处理请求：

 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));

时间的倒数用于计算提交运行的速度，并且RelinearizeInplace方法减少了生成的密文的大小。距离、时间和速度被保存到内存列表中。

GetMetrics方法聚合列表并返回：

• 总运行次数

• 总距离

• 总时间

• 平均速度

  
  

  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; . . . }

  
  

为了获得平均速度，使用计数的倒数，而不是使用：

（速度总和）/我们使用的运行次数：

（速度总和）*（1/运行次数）

由于服务器跟踪运行提交的次数，因此运行总数不是加密值。该未加密的值可以转换为明文并用于对密文执行的操作。虽然这是一个简单的示例，但其含义值得注意。服务器可以提供用于加密数据的附加值，使第三方提供商能够将专有数据应用于针对客户提供的加密数据的计算。

在下面的示例中，总计数被转换为倒数并添加到List<double>。 CKKS 操作需要加密的列表值，即使列表只包含一个值。因此， List<double>被编码为PlainText 。 MultiplyPlainInplace将 totalSpeed 乘以（1/运行次数）得到平均速度。为了节省空间，将结果应用于 totalSpeed密文，并且重新线性化密钥减少了输出的大小。

 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);

这些值在客户端进行 base64 编码、返回和解密。客户端采取额外的步骤将解密的明文转换为List<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);

发送以下值会产生总计和平均配速，该服务计算出总计和平均配速表，而无需解密从客户端发送的数据。

服务器计算数据并返回总跑步、距离、时间和配速，而不解密任何发送的数据。

概括

Microsoft SEAL 是 Microsoft Research 项目，尚未准备好用于生产应用程序。所有类都实现IDisposable并使用非托管资源。生产代码需要防止内存泄漏。 SEALContext类不遵循单一职责原则。它包括 BGV/BVF 和 CKKS 的方法。此外，CKKS 支持向量运算，但不支持向量加法。单个List<double>可以加密为单个CipherText ，但无法对单个CipherText 中的值求和。它可以用vector rotation来完成，但这是一个次优的解决方案。

此 Fitness Tracker 代码示例是对复杂主题的简单介绍。有许多具有更多逻辑的引人注目的用例：

• 基因标记检测

• 生物识别模板保护

• 对就地老化进行安全的人工监控

• 信用卡欺诈检测

  
  

同态加密已在学术界和原型中大量使用。实际应用受到同态加密方案所需计算能力的限制。 GPU 加速和 ASIC 处理器将继续削弱这一障碍。英特尔正在与微软和 DARPA 合作开发专为同态加密方案构建的FHE 硬件加速器。纳斯达克还资助了一个使用同态加密和机器学习进行欺诈检测的研发项目。 FHE.org 社区是该领域最新发展的绝佳资源。它有一个活跃的Discord 服务器。

本文中的所有代码示例均可从johniwasz/microsoft-seal-samples 获得。有关更深入的 Microsoft SEAL 示例，请参阅这些.NET 示例。

也发布在这里。