同态加密和SEAL库的介绍（一）简介

写在前面：

最近在做同态相关的内容，这里记录下相关的知识点和所踩过的坑，希望对大家有帮助。预计分几篇来详细介绍，从概念简介到不同模式介绍，具体包括了每种模式的编解码和加解密以及他们性能的比对。
虽然同态加密涉及了较多的密码学原理，但是Microsoft SEAL提供了一套开源的加密库，降低了我们的学习成本，使得实现一些同态下的计算变得简单。但是其使用规则有较多需要注意的地方，这里写出来和大家一起学习。
本文的参考主要来自于官方的介绍，这里先贴一下链接，方便大家查找：
Microsoft SEAL: Fast and Easy-to-Use Homomorphic Encryption LibraryMicrosoft SEAL is an easy-to-use and powerful open-source homomorphic encryption library that enables running computations directly on encrypted data.https://www.microsoft.com/en-us/research/project/microsoft-seal/

一、同态加密简介

1.1 引入

大多数加密方案包括三个功能：密钥生成、加密和解密。

对称密钥加密方案使用相同的密钥进行加密和解密；公钥加密方案分别使用公钥进行加密和密钥进行解密。
因此，公钥加密方案允许任何知道公钥的人加密数据，但只有那些知道密钥的人才能解密和读取数据。对称密钥加密可以高效地加密大量数据，并实现安全的外包云存储。公钥加密是实现今天安全在线通信的基础概念，但通常比对称密钥加密效率低得多。

虽然传统的对称和公钥加密可以用于安全存储和通信，但任何外包计算都必然需要在计算前移除这些加密层。因此，提供外包计算功能的云服务必须访问密钥，并实施访问控制策略以防止未经授权的员工访问这些密钥。

即：在传统的云存储和计算解决方案中，云需要对客户数据有未加密的访问权限以进行计算，必然会将数据暴露给云操作员。数据隐私依赖于由云实施的访问控制策略，并由客户信任这些策略。

1.2 同态原理

同态加密是一种密码学技术，允许对加密数据直接进行计算，而不需要解密数据。这种加密计算的结果仍然是加密的，只有用密钥（数据所有者）才能解密。

1.同态性质

同态加密的核心特性是“同态性”。如果某个加密方案是同态的，它允许对加密数据进行某些操作，且解密操作的结果与对未加密数据进行同样操作的结果一致。例如，假设有两个数据 a 和 b，及其相应的加密形式 $E(a)$ 和 $E(b)$ 。如果加法是同态的，那么：

$E(a)+E(b)=E(a+b)$

即加密数据相加后再解密的结果与先解密再相加的结果相同。

2.部分同态加密和全同态加密：

部分同态加密：仅支持一种运算（加法或乘法）的同态加密。例如，只支持加法的加密方案称为“加法同态加密”。
全同态加密（FHE, Fully Homomorphic Encryption）：支持任意运算（加法和乘法）的同态加密。这种加密方案最为通用但也最为复杂。

3.实际应用：

云计算：企业将数据加密后上传到云端，云服务提供商可以在不解密数据的情况下对其进行处理，从而保护数据隐私。
隐私保护的数据分析：在医学研究中，患者数据可以加密后供研究人员分析，确保患者隐私不会泄露。
安全的投票系统：选票可以加密后进行计数，确保投票过程的隐私和安全。

综上，同态加密并不是一种通用技术：只有某些计算可以在加密数据上进行。它还带有相当大的性能开销，因此在未加密数据上已经非常昂贵的计算在加密数据上可能不可行。
此外，用同态加密加密的数据比未加密数据大很多倍，所以可能不适合用这种技术加密整个大型数据库。而是在严格隐私要求禁止未加密云计算的情况下，但计算本身相对轻量的场景中有意义。

1.3 同态加密示例

为了更好的理解，这里把运算过程简单的举个例子：

1.密钥生成：生成一个公钥和一个私钥，分别用于加密和解密。

$(pk,sk)=KeyGen()$

2.加密：用公钥加密两个数 a 和 b。

$E(a)=Encrypt(pk,a), E(b)=Encrypt(pk,b)$

3.同态操作：在加密状态下对这两个数进行加法运算。(乘法同理)

$E(a+b)=E(a)+E(b)$

4.解密：用私钥解密运算结果。

$Decrypt(sk,E(a+b))=a+b$

二、SEAL库简介

2.1 引入

Microsoft SEAL（Simple Encrypted Arithmetic Library）是一个同态加密库，由微软开发，用于在加密数据上执行算术运算。该库旨在使同态加密变得更易于使用和集成，同时提供高性能和灵活性。数据隐私依赖于最先进的加密技术（数学），所有信息发布将由客户控制。

SEAL 库允许在加密的整数或实数上执行加法和乘法。其他操作，如加密比较、排序或正则表达式，在大多数情况下使用此技术在加密数据上评估是不可行的。因此，只有程序中特定的隐私关键的云计算部分应使用 Microsoft SEAL 实现。（故要注意适用范围）

2.2 安装

先贴一下官方库链接：

GitHub - microsoft/SEAL: Microsoft SEAL is an easy-to-use and powerful homomorphic encryption library.Microsoft SEAL is an easy-to-use and powerful homomorphic encryption library. - microsoft/SEALhttps://github.com/microsoft/SEAL在所有平台上，微软 SEAL 都使用 CMake 构建。先看要求:

这里简述一下构建步骤，当然具体问题还是看官方最新的说明好一些：

1.克隆代码库：

git clone https://github.com/microsoft/SEAL.git
cd SEAL

2.构建库：

cmake -S . -B build
cmake --build build

3.安装：

如果有root权限，可以选择全局安装：

cmake -S . -B build
cmake --build build
sudo cmake --install build

也可以安装到特定地方，这里假设是 ~/mylibs/

cmake -S . -B build -DCMAKE_INSTALL_PREFIX=~/mylibs
cmake --build build
sudo cmake --install build

安装好后，大概包含这些文件：

2.3 官方示例

在下载的文件中，包含了一些官方的示例，帮助用户理解基本概念和演示API功能，后续我也会基于这些例子给大家具体介绍。这些示例在 C++ 和 C# 中是相同的，并且分为几个源文件，分别位于 native/examples/（C++）和 dotnet/examples/（C#）目录中。包含：

C++	C#	描述
examples.cpp	Examples.cs	示例运行程序
1_bfv_basics.cpp	1_BFV_Basics.cs	使用 BFV 方案的加密模运算
2_encoders.cpp	2_Encoders.cs	将更复杂的数据编码到 Microsoft SEAL 明文对象中
3_levels.cpp	3_Levels.cs	介绍“层次”的概念；使用 CKKS 方案的前提知识
4_bgv_basics.cpp	4_BGV_Basics.cs	使用 BGV 方案的加密模运算
5_ckks_basics.cpp	5_CKKS_Basics.cs	使用 CKKS 方案的加密实数运算
6_rotation.cpp	6_Rotation.cs	在 BFV 和 CKKS 方案中对加密向量执行循环旋转
7_serialization.cpp	7_Serialization.cs	在 Microsoft SEAL 中序列化对象
8_performance.cpp	8_Performance.cs	性能测试

2.4 三种模式简介

Microsoft SEAL 提供了三种主要的同态加密方案：BFV、BGV 和 CKKS。每种方案都有其独特的特点和适用场景。这里简单做个介绍：

1. BFV（Brakerski/Fan-Vercauteren）方案

BFV 方案是一种基于整数的同态加密方案，支持在加密数据上进行模运算。它允许对加密整数进行加法和乘法操作，结果仍然是加密的。BFV 方案使用大整数和多项式环上的数学运算来实现其同态性质。

整数运算：适用于需要在加密整数上执行加法和乘法的场景。
模运算：操作结果是在一个大整数模数下计算的，类似于有限域中的运算。
适用性：适用于需要精确计算的应用，如加密投票系统和财务数据计算。

2. BGV（Brakerski-Gentry-Vaikuntanathan）方案

BGV 方案也是一种基于多项式环的同态加密方案，与 BFV 类似。BGV 方案支持在加密数据上执行模运算，并且可以处理更复杂的操作。

多项式运算：适用于在加密多项式上执行加法和乘法。
模块化设计：支持灵活的参数选择，可以根据应用需求调整性能和安全性。
适用性：适用于需要复杂多项式运算的应用，如加密搜索和过滤。

BGV是较新的版本才可用，给出的论文在这里，大家也可以按需参考下：
https://eprint.iacr.org/2020/1481.pdfhttps://eprint.iacr.org/2020/1481.pdf3. CKKS（Cheon-Kim-Kim-Song）方案

CKKS 方案是一种支持近似计算的同态加密方案，专为浮点数和复数运算设计。它允许在加密的实数或复数上执行加法和乘法，但结果是近似的。这种方案特别适合需要浮点数计算的应用，如机器学习和信号处理。

浮点数运算：适用于需要在加密浮点数上执行加法和乘法的场景。
近似计算：操作结果是近似的，非常适合需要大量浮点数运算的应用。
适用性：适用于机器学习模型评估、数据聚合和加密数据分析。

总结来说，三种加密方案各有其优势和适用场景，后面会对BFV和CKKS具体展开介绍。由于其性能差异巨大，故选择合适的加密方案和加密参数显得尤为重要。

2.5 总结

将未加密计算转化为加密数据上的计算并不总是容易或直接的，例如，不可能在加密数据上进行分支。尽管微软 SEAL 的 API 并不复杂，但它本身有一个陡峭的学习曲线，需要用户理解许多同态加密特有的概念。
即使用户能够编写和运行特定的计算，效率高低的实现之间的差异可能有几个数量级，新用户很难知道如何改进计算的性能。
并且建议学习上面提到的示例，它们旨在为读者提供必要的同态加密概念背景。直接复用示例中的代码效果并不好，因为示例通常演示单个功能，未优化性能。如果不深入学习这些示例就编写 Microsoft SEAL 代码，必然会导致代码易受攻击、运行故障或极其缓慢。