同态加密是密码学领域自1978年以来的经典难题，也是实现数据隐私计算的关键技术，在云计算、区块链、隐私计算等领域均存在着广泛的应用需求和一些可行的应用方案。

本文首先介绍同态加密的基本概念、研究进展以及标准化进展，然后对主流的乘法/加法半同态加密算法和全同态加密算法及其工程实现情况进行概述，最后对同态加密在各领域的应用场景进行分析。

一、同态加密概述

1、基本概念

同态加密（Homomorphic Encryption, HE）是指满足密文同态运算性质的加密算法，即数据经过同态加密之后，对密文进行特定的计算，得到的密文计算结果在进行对应的同态解密后的明文等同于对明文数据直接进行相同的计算，实现数据的“可算不可见”。同态加密的实现效果如图1所示。

图1：同态加密原理

如果一种同态加密算法支持对密文进行任意形式的计算，则称其为全同态加密（Fully Homomorphic Encryption, FHE）；如果支持对密文进行部分形式的计算，例如仅支持加法、仅支持乘法或支持有限次加法和乘法，则称其为半同态加密或部分同态加密，英文简称为SWHE（Somewhat Homomorphic Encryption）或PHE（Partially Homomorphic Encryption）。一般而言，由于任意计算均可通过加法和乘法构造，若加密算法同时满足加法同态性和乘法同态性，则可称其满足全同态性。

目前，同态加密算法已在区块链、联邦学习等存在数据隐私计算需求的场景实现了落地应用。由于全同态加密仍处于方案探索阶段，现有算法存在运行效率低、密钥过大和密文爆炸等性能问题，在性能方面距离可行工程应用还存在一定的距离。因此，实际应用中的同态加密算法多选取半同态加密（如加法同态），用于在特定应用场景中实现有限的同态计算功能。

2、研究进展

1978年，Rivest、Adleman（“RSA”中的“R”和“A”）和Dertouzos提出了全同态加密的构想[1]，自此成为了密码学研究领域的一个公开难题。目前，同态加密算法主要分为半同态加密和全同态加密两大类。半同态加密主要包括以RSA算法[2]和ElGamal算法[3]为代表的乘法同态加密、以Paillier算法[4]为代表的加法同态加密以及以Boneh-Goh-Nissim方案[5]为代表的有限次数全同态加密；全同态加密算法主要包括以Gentry方案[6][7]为代表的第一代方案、以BGV方案[8]和BFV方案[9][10]为代表的第二代方案、以GSW方案[11]为代表的第三代方案以及支持浮点数近似计算的CKKS方案[12]等等。上述方案及其基本特性和应用情况总览如表1所示。

表1：各类同态加密算法

3、标准化进展

（1）半同态加密标准化

Outsourcing computation, privately

Homomorphic evaluation function:

Eval: f, Enc(x) -> Enc(f(x))

Fully homomorphic encryption

Fully homomorphic = correctness for any efficient f = correctness for universal set

Approximate eigenvector method

基于GSW13的特征向量的构造，我们可以在ciphertext上计算加法和乘法，然后可以通过secret key恢复出message的计算结果。但是这个方法不安全，因为特征向量很容易被找到。

**idea：**使用approximate eigenvectors，在secret key右乘cipher text

Microsoft SEAL

Ref

https://www.youtube.com/watch?v=XaYEHnaAg8M

What’s is CKKS

Approximate arithmetic

For floating-point arithmetic, we keep the bits of significand to be the same.

For fixed-point arithmetic, we keep the scaling factor to be the same.

Algorithms in CKKS

Run Ubuntu Linux in Docker with Desktop Environment and VNC

Step 1 – Install Docker on your System

1

sudo systemctl start docker && sudo systemctl enable docker

Add your system user to the Docker group to be able to execute Docker commands without *sudo*.

1
2

sudo usermod -aG docker $USER
newgrp docker

Verify the installed Docker version.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

$ docker version
Client: Docker Engine - Community
 Version:           20.10.12
 API version:       1.41
 Go version:        go1.16.12
 Git commit:        e91ed57
 Built:             Mon Dec 13 11:45:48 2021
 OS/Arch:           linux/amd64
 Context:           default
 Experimental:      true
....

Step 2 – Pull the Ubuntu Docker Image

As said earlier, there are several images for Ubuntu that can be pulled. These images are available on the Docker page and can be pulled using Docker as shown.