【乘求值修正完毕】同态加密标准（译稿）

今天无意中看到开放隐私计算（微信公众号：OpenMPC）的文章《同态加密标准化简介》。文章中提到：

后面我们会给出同态加密标准的译稿，敬请期待。

大约在半年前，为了简要了解同态加密的当前进展，我曾经翻译过此标准的部分内容，特把原稿分享出来。欢迎开放隐私计算团队继续补充此标准的完整翻译。此翻译稿授权给开放隐私计算团队参考使用。

我翻译的标准是同态加密标准化组织（Homomorphic Encryption Standardization）于2018年11月21日发布的标准。目前，此标准已经于2019年1月7日再次更新。

注：我翻译原始使用的是markdown语法，转换为知乎文章时需要将所有公式变为公式编辑器，这方面还需继续处理。

同态加密标准（Homomorphic Encryption Standard）

We met as a group during the Homomorphic Encryption Standardization Workshop on July 13-14, 2017, hosted at Microsoft Research in Redmond（雷德蒙德，美国华盛顿州城市，微软总部）, and again during the second workshop on March 15-16, 2018 in MIT. Researchers from around the world represented government, industry, and academia. There are several research groups around the world who have made libraries for general-purpose homomorphic encryption available for applications and general-purpose use. Some examples include [SEAL], [HElib], [PALISADE], [cuHE], [cuFHE], [NFLlib], [HEAAN], and [TFHE]. Most general-purpose libraries for homomorphic encryption implement schemes that are based on the ring learning-with-error (RLWE) problem, and many of them displayed common choices for the underlying rings, error distributions, and other parameters.

我们于2017年7月13日至7月14日在雷德蒙德微软研究院形成了同态加密标准化组织，并于2018年3月15日至3月16日在MIT召开了第二次工作组会议。来自全世界的政府、工业届、学术界研究代表加入了这一组织。全世界有多个研究组织在实现通用同态加密函数库，以方便实际应用场景下使用同态加密。典型的同态加密库包括[SEAL]、[HElib]、[PALISADE]、[cuHE]、[cuFHE]、[NFLlib]、[HEAAN]和[TFHE]。多数同态加密通用库的实现基于RLWE假设构造，多数方案使用了相同的环、错误分布和其他参数。

Homomorphic Encryption is a breakthrough new technology which can enable private cloud storage and computation solutions, and many applications were described in the literature in the last few years. But before Homomorphic Encryption can be adopted in medical, health, and financial sectors to protect data and patient and consumer privacy, it will have to be standardized, most likely by multiple standardization bodies and government agencies. An important part of standardization is broad agreement on security levels for varying parameter sets. Although extensive research and benchmarking has been done in the research community to establish the foundations for this effort, it is hard to find all the information in one place, along with concrete parameter recommendations for applications and deployment.

同态加密是一个突破性的技术，是隐私保护云存储和云计算的解决方案。在过去的几年间，很多论文都在使用同态加密。但在医疗、健康、金融等领域应用同态加密保护病人和消费者的隐私之前，首先要借助标准化组织和政府机构的力量实现同态加密的标准化。标准化中的一个重要部分是对相应安全级别的参数设置达成一致。虽然学术研究已经进行了充分的研究，建立了全面的参数设置方法，但目前还没有一个地方可以统一列举所有的参数设置方式，并在应用和部署角度给出参数设置建议。

Homomorphic Encryption is a breakthrough new technology which can enable private cloud storage and computation solutions, and many applications were described in the literature in the last few years. But before Homomorphic Encryption can be adopted in medical, health, and financial sectors to protect data and patient and consumer privacy, it will have to be standardized, most likely by multiple standardization bodies and government agencies. An important part of standardization is broad agreement on security levels for varying parameter sets. Although extensive research and benchmarking has been done in the research community to establish the foundations for this effort, it is hard to find all the information in one place, along with concrete parameter recommendations for applications and deployment.

同态加密是一个突破性的技术，是隐私保护云存储和云计算的解决方案。在过去的几年间，很多论文都在使用同态加密。但在医疗、健康、金融等领域应用同态加密保护病人和消费者的隐私之前，首先要借助标准化组织和政府机构的力量实现同态加密的标准化。标准化中的一个重要部分是对相应安全级别的参数设置达成一致。虽然学术研究已经进行了充分的研究，建立了全面的参数设置方法，但目前还没有一个地方可以统一列举所有的参数设置方式，并在应用和部署角度给出参数设置建议。

文档大纲（Outline of the document）

HES Section 1.1 standardizes the encryption schemes to be used. Section 1.1 consists of:

• Section 1.1.1: introduces notation and definitions.
• Section 1.1.2: defines the security properties for homomorphic encryption.
• Section 1.1.3: describes the BGV and BFV schemes.
• Section 1.1.4: described the GSW scheme.
• Section 1.1.5: mentions some alternative schemes: [YASHE13], [HPS98]/[LTV12], and [CKKS17].
• Section 1.1.6: describes additional features of the schemes.

同态加密标准1.1节标准化相应的加密方案。1.1节包括：

• 1.1.1节：介绍符号表示和定义。
• 1.1.2节：定义同态加密的安全性质。
• 1.1.3节：描述BGV和BFV方案。
• 1.1.4节：描述GSW方案。
• 1.1.5节：提及其他一些可选方案：[YASHE13]、[HPS98]/[LTV12]和[CKKS17]。
• 1.1.6节：描述这些方案的附加特性。

HES Section 2.1 recommends parameter choices to achieve security. Section 2.1 consists of:

• Section 2.1.1: describes the hard problems: the LWE and RLWE assumptions.
• Section 2.1.2: describes known lattice attacks and their estimated running times.
• Section 2.1.3: mentioned the Arora-Ge attack on LWE.
• Section 2.1.4: discusses algebraic attacks on RLWE.
• Section 2.1.5: recommends concrete parameters to achieve various security levels.

同态加密标准2.1节推荐安全等级对应的参数选择。2.1节包括：

• 2.1.1节：描述困难问题：LWE和RLWE假设。
• 2.1.2节：描述已知格攻击和预估执行时间。
• 2.1.3节：提及LWE的Arora-Ge攻击。
• 2.1.4节：讨论RLWE的代数攻击。
• 2.1.5节：为不同安全等级推荐实际参数。
• It is expected that future work to update and expand this Homomorphic Encryption Standard will use the following numbering convention:
• updates to the encryption schemes or additional schemes may be added as Sections 1.2, 1.3, …
• updates to security levels or recommended parameters may be added as Sections 2.2, 2.3, …
• a new section to cover API design is planned to be added as Section 3.0, and updated as 3.1, …
• a new section to cover applications may be added as Section 4.0, and updated as 4.1, …

我们期望对同态加密标准的更新和扩展工作可以使用下述章节编号约定：

• 更新加密方案或增加新的加密方案，应用的章节编号为1.2、1.3等。
• 更新安全等级或推荐参数，应用的章节编号为2.2、2.3等。
• 增加新的章节，描述API设计，期望使用章节编号3.0，并随3.1等更新。
• 增加新的章节，描述应用场景，期望使用章节编号4.0，并随4.1等更新。

In the appendix we list some aspects that are not specified in this document and are expected to be covered by future documents.

在附录中，我们列举本文档没有涉及到的一些观点，并期望在未来版本的文档中增加这一些观点。

第1.1节：推荐加密方案（Section 1.1 Recommended Encryption Schemes）

第1.1.1节：符号表示和定义（Section 1.1.1 Notation and Definitions）

参数生成（ParamGen）

The parameter generation algorithm is used to instantiate various parameters used in the HE algorithms outlined below. As input, it takes:

参数生成算法 用于实例化同态加密算法的变量参数。参数生成算法的输入为：

• denotes the desired security level of the scheme. For instance, 128-bit security ( ) or 256-bit security.
• denotes the underlying plaintext space. Currently this standard specifies two types of parametrized plaintext spaces: modular integers (MI), and extension fields/rings (EX). We expect future versions of this document to introduce a third type of approximate numbers (AN).
  • (MI) Modular integers are parametrized by the modulus of the plaintext numbers to be encrypted, namely the plaintext space is . For instance, the parameter means that the plaintext space is , i.e., each individual element of the message space is an integer from the range and all operations on individual elements are performed modulo .
  • (EX) Extension rings/fields are parameterized by a modulus as above, and in addition by a polynomial over , specifying the plaintext space as . Namely, each element of the message space is an integer polynomial of degree smaller than with coefficients from the range , and all operations over individual elements are performed modulo , and modulo .
  • denotes the dimension of the vectors to be encrypted. For instance, means the messages to be encrypted are vectors where each is chosen from the range and operations are performed component-wise. That is, by defintion, . The multiplication operation over two vectors is defined similarly. The space of all possible vectors is referred to as the message space (MS).
  • denotes an auxiliary parameter that is used to control the complexity of the programs/circuits that one can expect to run over the encrypted messages. Lower parameters denote "smaller", or less expressive, or less complex programs/circuits. Lower parameters generally mean smaller parameters of the entire scheme. This, as a result, translates into smaller ciphertexts and more efficient evaluation procedures. Higher parameters generally increase key sizes, ciphertext sizes, and complexity of the evaluation procedures. Higher parameters are, of course, necessary to evaluate more complex programs.
• 表示期望的方案安全等级。例如，128比特安全性（ ）或256比特安全性。
• 表示明文空间。当前标准定义了两种明文空间：模整数（MI）和扩域/环（EX）。我们期望在后续版本的文档中引入第三类明文空间：近似数（AN）。
  • 模整数（MI）明文空间的实例化参数为模数 ，所有待加密的明文都需要模 ，即明文空间为 。例如，参数 意味着明文空间是 ，即明文空间的每个独立的元素都是 范围内的整数，对明文空间中每个独立元素的运算都在模 下执行。
  • 扩环/扩域（EX）的参数也包含上述的模数 ，还包含一个 上的多项式 ，这使得明文空间变为 。也就是说，明文空间的每一个元素是一个阶小于 的整数多项式，系数取值范围是 ，每个元素的运算都在模 和模 下定义。
  • 表示待加密向量的维度。例如， 的意思是待加密的消息为向量 ，其中每个 属于 ，且相应运算均逐维处理。也就是说，根据定义， 。两个向量上的乘法运算定义也是逐维处理。向量 所有可能的取值所对应的空间称为消息空间（MS）。
  • 表示一个辅助参数，用于控制在密文上执行同态运算的程序/电路复杂度。更低的参数意味着程电路序更“小”、更轻量级或者更简单。低参数一般意味着整个方案的密码学参数更小，而这会导致密文更短、相应算法的求值过程更高效。更高的参数一般意味着密钥和密文长度更长，相应算法的求值过程更复杂。当然了，更高的参数也意味着同态运算的程序/电路可以更复杂。

公钥生成（PubKeygen）

The public key-generation algorithm is used to generate a pair of secret and public keys. The public key can be shared and used by anyone to encrypt messages. The secret key should be kept private by a user and can be used to decrypt messages. The algorithm also generates an evaluation key that is needed to perform homomorphic operations over the ciphertexts. It should be given to any entity that will perform homomorphic operations over the ciphertexts. Any entity that has only the public and the evaluation keys cannot learn anything about the messages from the ciphertexts only.

公钥生成算法 用于生成一对私钥和公钥。公钥可以分享给任何人，用于加密消息。私钥需要由用户秘密存储，用于解密消息。算法还会生成一个求值密钥，用于在密文上执行同态运算。需要将求值密钥分发给在密文上执行同态运算的实体。任意仅拥有公钥和求值密钥的实体都无法仅从密文中得到与消息相关的任何信息。

私钥生成（SecKeygen）

The secret key-generation algorithm is used to generate a secret key. This secret key is needed to both encrypt and decrypt messages by the scheme. It should be kept private by the user. The algorithm also generates an evaluation key that is needed to perform homomorphic operations over the ciphertexts. The evaluation key should be given to any entity that will perform homomorphic operations over the ciphertexts. Any entity that has only the evaluation key cannot learn anything about the messages from the ciphertexts only.

私钥生成算法 用于生成一个私钥。私钥同时用于加密和解密消息。用户需要保证私钥的秘密性。算法还生成一个求值密钥，用于在密文上执行同态运算。需要把求值密钥提供给在密文上执行运算的实体。任意只拥有求值密钥的实体都无法仅通过密文得到与明文相关的任何信息。

公钥加密（PubEncrypt）

The public encryption algorithm takes as input the public key of the scheme and any message from the message space. The algorithm outputs a ciphertext . This algorithm generally needs to be randomized (that is, use random or pseudo-random coins) to satisfy the security properties.

公钥加密算法 的输入是方案的公钥和消息空间中的任意消息 。算法输出一个密文 。此算法一般是一个随机化算法（即需要利用随机或伪随机状态），从而满足安全性。

私钥加密（SecEncrypt）

The secret encryption algorithm takes as input the secret key of the scheme and any message from the message space. The algorithm outputs a ciphertext . This algorithm generally needs to be randomized (that is, use random or pseudo-random coins) to satisfy the security properties.

私钥加密算法 的输入是方案的私钥和消息空间中的任意消息 。算法输出一个密文 。此算法一般是一个随机化算法（即需要利用随机或伪随机状态），从而满足安全性。

解密（Decrypt）

The decryption algorithm takes as input the secret key of the scheme, , and a ciphertext . It outputs a message from the message space. The algorithm may also output special symbol , if the decryption cannot successfully recover the encrypted message .

解密算法 的输入是方案的私钥 和密文 。解密算法输出消息空间中的一个消息 。如果解密算法无法成功恢复加密的消息 ，则解密算法会输出一个特殊的符号 。

加求值（EvalAdd）

is a randomized algorithm that takes as input the system parameters , the evaluation key , two ciphertexts and , and outputs a ciphertext .

加求值算法 是一个随机化算法，以系统参数 、求值密钥 、两个密文 和 为输入，输出一个密文 。

The correctness property of is that if is an encryption of plaintext element and is an encryption of plaintext element , then should be an encryption of .

的正确性要求如果 是明文元素 的密文， 是明文元素 的密文，则 是 的密文。

常数加求值（EvalAddConst）

is a randomized algorithm that takes as input the system parameters , the evaluation key , a ciphertext , and a plaintext , and outputs a ciphertext .

常数加求值算法 是一个随机化算法，以系统参数 、求值密钥 、密文 和明文 作为输入，输出密文 。

The correctness property of is that if is an encryption of plaintext element , then should be an encryption of .

的正确性要求如果 是明文元素 的密文，则 是 的密文。

乘求值（EvalMult）

is a randomized algorithm that takes as input the system parameters , the evaluation key , two ciphertexts and , and outputs a ciphertext .

乘求值算法 是一个随机化算法，以系统参数 、求值密钥 、两个密文 为输入，输出密文 。

The correctness property of is that if is an encryption of plaintext element and is an encryption of plaintext element , then should be an encryption of .

的正确性要求如果 是明文元素 的密文， 是明文元素 的密文，则 是 的密文。

常数乘求值（EvalMultConst）

$\text{EvalMultConst}(Params, EK, C_1, M_2) \rightarrow C_3$ is a randomized algorithm that takes as input the system parameters $Params$, the evaluation key $EK$, a ciphertexts $C_1$, and a plaintext $M_2$, and outputs a ciphertext $C_3$.

常数乘求值算法$\text{EvalMultConst}(Params, EK, C_1, M_2) \rightarrow C_3$是一个随机化算法，以系统参数$Params$、求值密钥$EK$、密文$C_1$和明文$M_2$为输入，输出密文$C_3$。

The correctness property of $\text{EvalMultConst}$ is that if $C_1$ is an encryption of plaintext element $M_1$, then $C_3$ should be an encryption of $M_1 \times M_2$.

$\text{EvalMultConst}$的正确性要求如果$C_1$是明文元素$M_1$的密文，则$C_3$是$M_1 \times M_2$的密文。

刷新（Refresh）

$\text{Refresh}(Params, flag, EK, C_1) \rightarrow C_2$ is a randomized algorithm that takes as input the system parameters $Params$, a multi-valued $flag$ (which can be either one of "Relinearize", "ModSwitch" or "Bootstrap"), the evaluation key $EK$, and a ciphertext $C_1$, and outputs a ciphertext $C_2$.

刷新算法$\text{Refresh}(Params, flag, EK, C_1) \rightarrow C_2$是一个随机化算法，以系统参数$Params$、多值参数$flag$（可以为“重线性化”、“模转化”或“自举”）、求值密钥$EK$和密文$C_1$为输入，输出密文$C_2$。

The correctness property of $\text{Refresh}$ is that if $C_1$ is an encryption of plaintext element $M_1$, then $C_2$ should be an encryption of $M_1$ as well.

$\text{Refresh}$的正确性要求如果$C_1$是明文元素$M_1$的密文，则$C_2$也是$M_1$的密文。

The desired property of $\text{Refresh}$ is that it turns a "complex" ciphertext of a message into a "simple" one encrypting the same message. Two embodiments of $\text{Refresh}$ are:

• the bootstrapping procedure, which takes a ciphertext with large noise and outputs a ciphertext of the same message with a fixed amount of noise;
• the key-switching procedure, which takes a ciphertext under one key and outputs a ciphertext of the same message under a different key.

$\text{Refresh}$的性质是其可以把一个消息的”复杂“密文转换为相同消息的”简单“密文。$\text{Refresh}$的两种体现形式为：

• 自举过程，以带有大噪声的密文为输入，输出噪声量固定的密文，且对应的明文保持不变。
• 密钥转换过程，以某个密钥对应的密文为输入，输出另一个密钥的密文，且对应的明文保持不变。

有效性检查（ValidityCheck）

$\text{ValidityCheck}(Params, EK, [C], COMP) \rightarrow flag$ is an algorithm that takes as input the system parameters $Params$, the evaluation key $EK$, an array of ciphertexts $[C]$, and a specification of the homomorphic computation encoded as a straight-line program $COMP$, and outputs a Boolean $flag$.

有效性检查算法$\text{ValidityCheck}(Params, EK, [C], COMP) \rightarrow flag$以系统参数$Params$、求值密钥$EK$、密文数组$[C]$、以及一个用直线式程序描述的同态运算描述$COMP$为输入，输出布尔值$flag$。

The correctness property of $\text{ValidityCheck}$ is that if $\text{ValidityCheck}$ outputs $flag = 1$, then doing the homomorphic computation $COMP$ on the vector of ciphertexts $[C]$ produces a ciphertext that decrypts to the correct answer.

$\text{ValidityCheck}$的正确性要求如果$\text{ValidityCheck}$输出$flag = 1$，则在密文向量$[C]$执行同态计算$COMP$将生成一个可以解密成功、计算结果正确的密文。

第1.1.2节：性质（Section 1.1.2 Properties）

**Semantic Security or IND-CPA Security**: At a high level, a homomorphic encryption scheme is said to be secure if no adversary has an advantage in guessing (with better than 50% chance) whether a given ciphertext is an encryption of either one of two equally likely distinct messages. This requires encryption to be randomized so that two different encryptions of the same message do not look the same.

**语义安全性或IND-CPA安全性**：从更高层面看，如果攻击者无法有优势（有超过50%的概率）猜测出给定密文是两个长度相等的不同明文中哪个消息加密得到的，则同态加密方案就是安全的。这要求加密算法是随机化过程，使得相同消息的两次加密结果不同。

Suppose a user runs the parameter and the key-generation algorithms to provide the key tuple. An adversary is assumed to have the parameters, the evaluation key $EK$, a public key $PK$ (only in the public-key scheme) and can obtain encryptions of messages of its choice. The adversary is then given an encryption of one of two messages of its choice, computed by the above encryption algorithm, without knowing which message the encryption corresponds to. The security of HE then guarantees that the adversary cannot guess which message the encryption corresponds to with significant advantage better than a 50% chance. This captures the fact that no information about the messages is revealed in the ciphertext.

假设一个用户执行参数生成和密钥生成算法生成了密钥。假设攻击者持有参数$Params$、求值密钥$EK$、公钥$PK$（只有公钥同态加密方案存在公钥），且攻击者能获得自己选择消息所对应的密文。攻击者随后得到由加密算法计算得到的、自己选择两个消息其中一个消息的密文，但攻击者不知道得到的是哪个消息得到的密文。同态加密方案的安全性保证攻击者无法有远超过50%的机会正确猜测出此密文是哪个消息加密得到的。这一定义说明，密文不会泄露与明文相关的任何信息。

**Compactness**: The compactness property of a homomorphic encryption scheme guarantees that homomorphic operations on the ciphertexts do not expand the length of the ciphertexts. That is, any evaluator can perform an arbitrary supported list of evaluation function calls and obtain a ciphertext in the ciphertext space (that does not depend on the complexity of the evaluated functions).

**紧致性**：同态加密方案的紧致性要求密文上的同态运算不会扩展密文的长度。也就是说，任意求值方可以执行求值函数支持的任意运算，且得到的密文属于密文空间，而密文空间与求值函数的复杂度无关。

**Efficient decryption**: Efficient decryption property says that the homomorphic encryption scheme always guarantees that the decryption runtime does not depend on the functions which was evaluated on the ciphertexts.

**高效解密**：高效解密性要求同态加密方案保证解密执行时间与密文上执行求值函数的复杂度无关。

第1.1.3节：BGV和BFV同态加密方案（Section 1.1.3. The BGV and BFV Homomorphic Encryption Schemes）

In this section, we describe the two primary schemes for implementation of homomorphic encryption, \[BGV12\] and \[B12\]/\[FV12\], these two schemes are very similar. In Section 1.1.4. below we describe the GSW scheme, which is somewhat different. In Section 1.1.5, we also mention some alternative schemes \[YASHE13\], \[HPS98\]/\[LTV12\], and \[CKKS17\], but they are not described in this standard.

a. Brakerski-Gentry-Vaikuntanathan（BGV）方案（Brakerski-Gentry-Vaikuntanathan (BGV)）

We focus here on describing the basic version of the BGV encryption scheme. Optimizations to the basic scheme will be discussed at the end of this section.

我们聚焦于BGV加密方案的基础版本。本节的末尾将讨论基础方案的优化方法。

- $\text{BGV.ParamGen}(\lambda, PT, K, B) \rightarrow Params$

Recall that $\lambda$ is the security level parameter, for BGV the plaintext space $PT$ is either of type $MI$ or $EX$ with integer modulus $p > 1$, and $K \geq 1$ is an integer vector length.

注意$\lambda$是安全级别参数，BGV方案的明文空间$PT$可以为$MI$或$EX$，模整数满足$p > 1$，而$K \geq 1$是整数向量长度。

In the basic BGV scheme, the auxiliary input $B$ is an integer that determines the maximum multiplicative depth of the homomorphic computation. This is simply the maximum number of sequential multiplications required to perform the computation. For example, the function $g(x_1, x_2, x_3, x_4) = x_1x_2 + x_3x_4$ has multiplicative depth $1$.

在基础BGV方案中，辅助输入$B$是一个整数，决定同态运算的乘法最大深度，也就是计算过程中必须按顺序执行乘法运算的最大数量。例如，函数$g(x_1, x_2, x_3, x_4) = x_1x_2 + x_3x_4$的乘法深入为$1$。

In the basic BGV scheme, the parameters $param$ include the ciphertext modulus parameter $q$ and a ring $R = Z[x]/f(x)$ and corresponding plaintext ring $R/pR$ and ciphertext ring $R/qR$. The parameters $param$ also specify a "key distribution" $D_1$ and an "error distribution" $D_2$ over $R$, the latter is based on a Gaussian distribution with standard deviation $\sigma$ set according to the security guidelines specified in Section 2.1.5.

在基础BGV方案中，参数$param$包含密文模数$q$、环$R = Z[x]/f(x)$以及与之关联的明文环$R/pR$和密文环$R/qR$。参数$param$还指定了一个$R$上的“密钥分布”$D_1$和一个“错误分布”$D_2$，其中错误分布式一个标准差为$\sigma$的高斯分布，需根据2.1.5节的安全指南设置标准差。

In the basic BGV scheme, the secret key $SK$ is an element $s$ in the ring $R$, chosen from distribution $D_1$. In the basic BGV scheme, there is no evaluation key $EK$.

- $\text{BGV.PubKeygen}(params) \rightarrow (SK, PK, EK)$

In the basic BGV scheme, $\text{PubKeygen}$ first runs $\text{SecKeygen}$ and obtains $(SK, EK)$ where $SK$ is an element $s$ that belongs to the ring $R$. $\text{PubKeygen}$ chooses a uniformly random element $a$ from the ring $R/qR$ and outputs the public key $PK$ which is a pair of ring elements $(pk_0, pk_1) = (−a, as + pe)$ where $e$ is chosen from the error distribution $D_2$.

- $\text{BGV.SecEncrypt}(SK, M) \rightarrow C$

In the basic BGV scheme, $\text{SecEncrypt}$ first maps the message $M$ which comes from the plaintext space (either $\mathbb{Z}_{p^r}$ or $\left(\mathbb{Z}_p[x]/f(x)\right)^r$) into an element $\hat{M}$ of the ring $R/pR$.

$\text{SecEncrypt}$ then samples a uniformly random element $a$ from the ring $R/qR$ and outputs the pair of ring elements $(c_0, c_1) = (−a, as + pe + \hat{M})$ where $e$ is chosen from the error distribution $D_2$. (See Comments 1, 2 below for more general methods of encoding the message during encryption. The same comments apply also to public-key encryption with BGV.)

- $\text{BGV.PubEncrypt}(PK, M) \rightarrow C$

In the basic BGV scheme, $\text{PubEncrypt}$ first maps the message $M$ which comes from the plaintext space (either $\mathbb{Z}_{p^r}$ or $\left(\mathbb{Z}_p[x]/f(x)\right)^r$) into an element $\hat{M}$ of the ring $R/pR$. Recall that the public key $PK$ is a pair of elements $(pk_0, pk_1)$.

$\text{PubEncrypt}$ then samples three elements $u$ from distribution $D_1$ and $e_1, e_2$ from the error distribution $D_2$ and outputs the pair of ring elements $(c_0, c_1) = (pk_0 u + pe_1, pk_1 u + pe_2 + \hat{M})$.

$\text{PubEncrypt}$随后采样三个元素：根据分布$D_1$采样$u$，根据错误分布$D_2$采样$e_1, e_2$，并输出一对环元素$(c_0, c_1) = (pk_0 u + pe_1, pk_1 u + pe_2 + \hat{M})$。

- $\text{BGV.Decrypt}(SK, C) \rightarrow M$

In the basic BGV scheme, $\text{Decrypt}$ takes as input the secret key which is an element $s$ of the ring $R$, and a ciphertext $C = (c_0, c_1)$ which is a pair of elements from the ring $R/qR$.

We remark that a ciphertext $C$ produced as the output of the encryption algorithm has two elements in $R/qR$, but upon homomorphic evaluation, ciphertexts can grow to have more ring elements. The decryption algorithm can be modified appropriately to handle such ciphertexts.

$\text{Decrypt}$ first computes the ring element $c_0 s + c_1$ over $R/qR$ and interprets it as an element $c'$ in the ring $R$. It then computes $c' (\bmod p)$, an element of $R/pR$, which it outputs.

In the basic BGV scheme, $\text{EvalAdd}$ takes as input ciphertexts $C_1 = (c_{1,0}, c_{1,1})$ and $C_2 = (c_{2,0}, c_{2,1})$ and outputs $C_3 = (c_{1,0} + c_{2,0}, c_{1,1} + c_{2,1})$, where the operations are done in $R/qR$.

- $\text{BGV.EvalMult}(Params, EK, C_1, C_2) \rightarrow C_3$

In the basic BGV scheme, $\text{EvalMult}$ takes as input ciphertexts $C_1 = (c_{1,0}, c_{1,1})$ and C_2 = (c_{2,0}, c_{2,1})$ and outputs $C_3 = (c_{1,0}c_{2,0}, c_{1,0}c_{2,1} + c_{1,1}c_{2,0}, c_{1,1}c_{2,1})$, where the operations are done in $R/qR$.

**Comment 1**. The noise term $pe + \hat{M}$ in the encryption procedure can be generalized to an error term drawn from the coset $\hat{M} + pR$, according to an error-sampling procedure. All the considerations discussed below for the error distribution $D_2$, apply equally to the error-sampling procedure in this more general implementation.

**Comment 2**. There is also an equivalent "MSB encoding" of the message for BGV encryption, where the message is encoded as $W \hat{M} + e$ (with $W = \lfloor q / p \rfloor$, similarly to the BFV scheme below). There are lossless conversions between these two encoding methods, as long as the plaintext modulus $p$ is co-prime with the ciphertext modulus $q$.

**The Full BGV Scheme.** In the basic BGV scheme, ciphertexts grow as a result of $\text{EvalMult}$. For example, given two ciphertexts each composed of two ring elements, $\text{EvalMult}$ as described above results in three ring elements. This can be further repeated, but has the disadvantage that upon evaluating a degree-$d$ polynomial on the plaintexts, the resulting ciphertext has $d + 1$ ring elements.

This deficiency is mitigated in the full BGV scheme, with two additional procedures. The first is called "Key Switching" or "Relinearization" which is implemented by calling the Refresh subroutine with flag = “KeySwitch”, and the second is “Modulus Switching” or “Modulus Reduction” which is implemented by

calling the $\text{Refresh}$ subroutine with $flag = \text{"ModSwitch"}$. Support for key switching and modulus switching also necessitates augmenting the key generation algorithm.

For details on the implementation of the full BGV scheme, we refer the reader to \[BGV12\].

有关实现完整BGV方案的细节，我们建议读者参考\[BGV12\]。

**Properties Supported.** The BGV scheme supports many features described in Section 6, including packed evaluations of circuits and can be extended into a threshold homomorphic encryption scheme. In terms of security, the BGV homomorphic evaluation algorithms can be augmented to provide evaluation privacy (with respect to semi-honest adversaries).

**支持特性**。BGV方案支持第6节描述的多种性质，如电路打包求值、可扩展为门限同态加密方案。从安全角度看，BGV同态求值算法可以进一步扩展为支持求值隐私性（但仅能抵御半可信攻击者的攻击）。

b. Brakerski / Fan-Vercauteren（BFV）方案（Brakerski / Fan-Vercauteren (BFV)）

（略）

Note that the ciphertext size increases in this operation. One may apply a Relinearization algorithm as in the BGV scheme to obtain a new ciphertext of the original size encrypting the same message $M_1 \times M_2$.

注意到密文大小会因曾乘法运算而增加。我们可以应用BGV方案的重线性化算法获得与原始密文长度相同的、加密相同消息$M_1 \times M_2$的新密文。

**Properties Supported**. The complete BFV scheme supports many features described in Section 6, including packed evaluations of circuits and can be extended into a threshold homomorphic encryption scheme. In terms of security, the BFV homomorphic evaluation algorithms can be augmented to provide evaluation privacy.

**支持特性**。完整BFV方案支持第6节描述的多种性质，如电路打包求值、可扩展为门限同态秘密分享方案。从安全角度看，BFV同态求值算法可以进一步扩展为支持求值隐私性。

For details on the implementation of the full BFV scheme, we refer the reader to \[B12\], \[FV12\].

有关实现完整BFV方案的细节，我们建议读者参考\[BGV12\]。

c. BGV和BFV方案比较（Comparison between BGV and BFV）

When implementing HE schemes, there are many choices which can be made to optimize performance for different architectures and different application scenarios. This makes a direct comparison of these schemes quite challenging. A paper by Costache and Smart \[CS16\] gives some initial comparisons between BGV, BFV and two of the schemes described below: YASHE and LTV/NTRU. A paper by Kim and Lauter \[KL15\] compares the performance of the BGV and YASHE schemes in the context of applications. Since there is further ongoing work in this area, we leave this comparison as an open research question.

在实现同态加密方案时，可以在根据不同的架构和场景需求，通过多个层面选择相应的优化技巧。因此，很难直接对比各个方案的优劣。Costache和Smart的论文\[CS16\]给出了BGV、BFV方案的简单对比，同时对比了接下来要描述的两个方案：YASHE和LTV/NTRU。Kim和Lauter的论文\[KL15\]结合实际应用场景比较了BGV和YASHE方案的性能。由于这个领域还有很多的研究和实现工作需要去完成，我们将方案比较留作一个公开的研究问题。

第1.1.4节：GSW方案和自举（Section 1.1.4. The GSW Scheme and bootstrapping）

Currently, the most practical homomorphic encryption schemes only allow to perform bounded depth computations. These schemes can be transformed into fully homomorphic ones (capable of arbitrary computations) using a "bootstrapping" technique introduced by Gentry \[G09\], which essentially consists of a homomorphic evaluation of the decryption algorithm given the encryption of the secret key. Bootstrapping is a very time-consuming operation and improving on its efficiency is still a very active research area. So, it may still not be ready for standardization, but it is the next natural step to be considered.

当前，大多数高效的同态加密方案只支持有限深度的密文同态运算。可以应用Gentry\[G09\]提出的”自举“技术将方案转换为全同态加密（支持任意深度的密文同态运算）。自举的基本思想是用加密的私钥对解密算法进行同态求值。自举是一个非常费时的运算，如何提高自举运算的性能仍然是一个活跃的研究领域。我们目前认为自举运算还未到可以标准化的程度，下一阶段再考虑标准化。

Bootstrapping using the BGV or BFV schemes requires assuming that lattice problems are computationally hard to approximate within factors that grow superpolynomially in the lattice dimension $n$. This is a stronger assumption than the inapproximability within polynomial factors required by standard (non-homomorphic) lattice-based public key encryption.

应用BGV和BFV方案实现自举运算要求格困难问题是计算困难的，但困难系数与格维度$n$成超多项式递增关系。相比标准（非同态）格公钥加密所以来的困难假设，这个假设显然更强。

In \[GSW13\], Gentry, Sahai and Waters proposed a new homomorphic encryption scheme (still based on lattices) that offers a different set of trade-offs than BGV and BFV. An important feature of this scheme is that it can be used to bootstrap homomorphic encryption based on the assumption that lattice problems are hard to approximate within polynomial factors. Here we briefly describe the GSW encryption and show how both its security and applicability to bootstrapping are closely related to LWE encryption, as used by the BGV and BFV schemes. So, future standardization of bootstrapping (possibly based on the GSW scheme) could build on the current standardization effort.

在\[GSW13\]中，Gentry、Sahai和Waters提出了一个新的同态加密方案（方案仍然基于格），从而在BGV和BFV方案之外提供了一系列新的权衡点。GSW13方案的一个重要特性是，同态加密自举运算所依赖假设的困难系数与格维度$n$成多项式递增关系。这里我们简要描述GSW加密，指出GSW加密的安全性和可用性和BGV/BFV方案类似，与LWE加密非常相关。因此，未来自举运算的标准化工作（很可能基于GSW方案）也可以在当前标准化工作的基础上进行。

（略）

In \[GSW13\] it is shown how (a public key version of) this cryptosystem supports both addition and multiplication, without the need for an evaluation key, which has applications to identity-based and attribute-based homomorphic encryption. Later, in \[BV14\] it was observed how the GSW multiplication operation exhibits an asymmetric noise growth that can be exploited to implement bootstrapping based on the hardness of approximating lattice problems within polynomial factors. Many subsequent papers (e.g., \[AP14, DM15, GINX16, CGGI16\]) improve on the efficiency of \[BV14\], but they all share the following features with \[BV14\]:

• They all use variants of the GSW encryption to implement bootstrapping.
• Security only relies on the hardness of approximating lattice problems within polynomial factors.
• They are capable of bootstrapping any LWE-based encryption scheme, i.e., any scheme which includes an LWE encryption of the message as part of the ciphertext. LWE-based schemes include BGV, BFV and GSW.

论文\[GSW13\]展示了（公钥版本的）方案如何在不需要求值密钥的条件下支持加法和乘法运算，这一性质可被用于构造基于身份和基于属性同态加密。随后，论文\[BV14\]发现如何在GSW乘法运算中引入非对称噪声增加量，从而基于多项式因子的近似格问题困难性实现自举。很多后续的论文（如\[AP14, DM15, GINX16, CGGI16\]）提高了\[BV14\]的性能，但他们都应用了\[BV14\]的特性：

• 所有方案都应用GSW加密的变种形式实现自举。
• 安全性仅依赖于多项式因子近似格问题的困难性。
• 所有方案可以自举任意基于LWE的加密方案，即加密方案中包含一个LWE形式的密文。LWE加密方案包括BGV、BFV和GSW。

In particular, GSW can be used to implement the bootstrapping procedure for BGV and BFV and turn them into fully homomorphic encryption (FHE) schemes.

特别地，可以利用GSW实现BGV和BFV的自举，使这两个方案转换为全同态加密方案。

第1.1.5节：其他方案（Section 1.1.5 Other Schemes）

Yet Another Somewhat Homomorphic Encryption (\[YASHE13\]) is similar to the BGV and BFV schemes and offers the same set of features.

另一个部分同态加密（Somewhat Homomorphic Encryption）(\[YASHE13\])与BGV和BFV方案很相似，也具有相同的特性。

The scheme NTRU/Lopez-Alt-Tromer-Vaikuntanathan (\[HPS98\]/\[LTV12\]) relies on the NTRU assumption (also called the "small polynomial ratios assumption"). It offers all the features of BGV and BFV, and in addition, also offers an extension that supports multi-key homomorphism. However, it must be used with a much wider error distribution than the other schemes that are described in this document (or else it becomes insecure), and therefore it should only be used with a great deal of care. This standard does not cover security for these schemes.

方案NTRU/Lopez-Alt-Tromer-Vaikuntanathan（\[HPS98\]/\[LTV12\]）依赖于NTRU假设（也成为小多项式比率假设）。此方案提供了BGV和BFV方案的全部特性，并进一步可以扩展为支持多密钥同态特性。然而，方案所使用的错误分布要比其他方案更大（否则方案将变得不安全），因此使用时需要特别小心谨慎。本标准的推荐参数无法满足此方案的安全性。

Another scheme, called CKKS, with plaintext type approximate numbers, was recently proposed by Cheon, Kim, Kim and Song \[CKKS17\]. This scheme is not described here, but we expect future version of this standard to include it.

另一个方案称为CKKS，由Cheon、Kim、Kim和Song提出\[CKKS17\]，支持的明文类型为近似数。本标准没有描述此方案，我们期望本标准的未来版本可以包含此方案。

Section 1.1.6. Additional Features & Discussion

a. Distributed HE

Homomorphic Encryption is especially suitable to use for multiple users who may want to run computations on an aggregate of their sensitive data. For the setting of multiple users, an additional property which we call threshold-HE is desirable. In threshold-HE the key-generation algorithms, encryption and decryption algorithms are replaced by a distributed-key-generation (DKG) algorithm, distributed-encryption (DE) and distributed-decryption (DD) algorithms. Both the distributed-key-generation algorithm and the distributed-decryption algorithm are executed via an interactive process among the participating users. The evaluation algorithms EvalAdd, EvalMult, EvalMultConst, EvalAddConst and Refresh remain unchanged.

同态加密特别适用于多个用户在敏感数据上计算数据聚合结果的场景。在多个用户的场景下，我们进一步需要一个称为门限同态加密（Threshold-HE）的性质。在门限同态加密中，密钥生成算法、加密算法和解密算法被替换为分布式密钥生成（DKG）算法、分布式加密（DE）算法和分布式解密（DD）算法。分布式密钥生成算法和分布式解密算法要通过参与方交互的过程来完成。求值算法EvalAdd、EvalMult、EvalMultConst、EvalAddConst和Refresh保持不变。

We will now describe the functionality of the new algorithms.

我们现在要描述这些新算法的功能。

We begin with the distributed-key-generation (DKG) algorithm to be implemented by an interactive protocol among $t$ parties $p_1, \ldots, p_t$. The DKG algorithm is a randomized algorithm. The inputs to DKG are: security parameter, number of parties $t$, and threshold parameter $d$. The output of DKG is a vector of secret keys $s = (s_1, \ldots, s_t)$ of dimension $t$ and a public evaluation key $EK$ where party $p_i$ receives $(EK, s_i)$. We remark that party $p_i$ doesn’t receive $s_j$ for $i \neq j$ and party $i$ should maintain the secrecy of its secret key $s_i$.

我们从分布式密钥生成（DKG）算法开始，实现此算法需要构造一个涉及$t$个参与方$p_1, \ldots, p_t$交互执行的协议。DKG算法是一个随机化算法。DKG的输入是：安全参数、参与方数量$t$、门限参数$d$。DKG的输出是一个$t$维密钥向量$s = (s_1, \ldots, s_t)$和一个公开求值密钥$EK$，参与方$p_i$收到$(EK, s_i)$。需要强调的是，参与方$p_i$不能收到$i \neq j$的$s_j$，且参与方$i$需要保证其私钥$s_i$的秘密性。

Next, the distributed-encryption (DE) algorithm is described. The DE algorithm is a randomized algorithm which can be run by any party $p_i$. The inputs to DE run by party $p_i$ are: the secret key $s_i$ and the plaintext $M$. The output of DE is a ciphertext $C$.

我们接下来描述分布式加密（DE）算法。DE算法是一个随机化算法，由任意一个参与方$p_i$执行。参与方$p_i$执行DE时的输入为：密钥$s_i$和明文$M$。DE的输出是一个密文$C$。

Finally, we describe the distributed-decryption (DD) algorithm to be implemented by an interactive protocol among a subset of the $t$ parties $p_1, \ldots, p_t$. The DD algorithm is a randomized algorithm. The inputs to DD are: a subset of secret keys $s = (s_1, \ldots, s_t)$, the threshold parameter $d$, and a ciphertext $C$. In particular, every participating party $p_i$ provides the input $s_i$. The ciphertext $C$ can be provided by any party. The output of DD is: plaintext $M$.

最后，我们描述分布式解密（DD）算法，实现此算法需要构造一个涉及$t$个参与方$p_1, \ldots, p_t$子集交互执行的协议。DD算法是一个随机化算法。DD的输入是：私钥$s = (s_1, \ldots, s_t)$的一个子集，门限参数$d$、密文$C$。特别地，每个参与方$p_i$提供输入$s_i$。密文$C$可以由任意一个参与方提供。DD的输出是明文$M$。

The correctness requirement that the above algorithms should satisfy is as follows. If at least $d$ of the parties correctly follow the prescribed interactive protocol that implements the DD decryption algorithm, then the output of the decryption algorithm will be correct. The security requirement is for semantic security to hold as long as fewer than $d$ parties collude adversarially.

方案正确性要求上述算法满足下述性质。如果至少$d$个参与方正确执行由上述交互式协议实现的DD解密算法，则解密算法的输出应该是正确的。方案安全性要求只要小于$d$个参与方合谋攻击，方案就满足语义安全性。

An example usage application for (DKG,DE,DD) is for two hospitals, $t = 2$ and $d = 2$ with sensitive data sets $M_1$ and $M_2$ (respectively) who want to compute some analytics $F$ on the joint data set without revealing anything about $M_1$ and $M_2$ except for what is revealed by $F(M_1, M_2)$.

使用(DKG, DE, DD)的实际例子是两家医院，$t = 2$和$d = 2$，分别持有敏感数据集$M_1$和$M_2$。两家意愿希望联合计算某个统计分析结果$F$，但除$F(M_1, M_2)$外不泄露其他任何与$M_1$和$M_2$相关的信息。

In such a case the two hospitals execute the interactive protocol for DKG and obtain their respective secret keys $s_1$ and $s_2$ and the evaluation key $EK$. They each use DE on secret key $s_i$ and data $M_i$ to produce ciphertext $C_i$. The evaluation algorithms on $C_1, C_2$ and the evaluation key $EK$ allow the computation of a ciphertext $C$ which is an encryption of $F(M_1, M_2)$. Now, the hospitals execute the interactive protocol DD using their secret keys and ciphertext $C$ to obtain $F(M_1, M_2)$.

在上述场景中，两家医院执行DKG对应的交互式协议，分别得到密钥$s_1$、$s_2$以及求值密钥$EK$。他们分别应用私钥$s_i$和数据$M_i$执行DE算法，生成密文$C_i$。在$C_1, C_2$和求值密钥$EK$上执行求值算法，就可以在密文$C$上执行运算，得到$F(M_1, M_2)$的密文。现在，医院用私钥和密文$C$执行交互式协议$D$，得到$F(M_1, M_2)$。

b. Active Attacks

One can consider stronger security requirements beyond semantic security. For example, consider an attack on a client that holds data $M$ and wishes to compute $F(M)$ for a specified algorithm $F$, and wants to outsource the computation of $F(M)$ to a cloud, while maintaining the privacy of $M$. The client encrypts $M$ into ciphertext $C$ and hands $C$ to the cloud server. The server is supposed to use the evaluation algorithms to compute a ciphertext $C'$ which is an encryption of $F(M)$ and return this to the client for decryption.

我们可以考虑比语义安全性更强的安全要求。考虑这样一个攻击场景：客户端持有数据$M$并希望在$M$上执行一个特定的算法$F$，即计算$F(M)$。同时，客户端希望将$F(M)$的计算过程外包给云平台，但要保护$M$的隐私性。客户端将$M$加密为密文$C$，并将$C$交给云服务商。云服务商需要应用求值算法计算得到$F(M)$所对应的密文$C'$，并将$C'$返回给客户端解密。

Suppose that instead the cloud computes some other $C''$ which is the encryption of $G(M)$ for some other function $G$. This may be problematic to the client as it would introduce errors of potentially significant consequences. This is an example of an active attack which is not ruled out by semantic security.

假设云服务商计算得到了另一个密文$C''$，这是另一个函数$G$处理结果$G(M)$所对应的密文。如果出现这种情况，客户端在后续数据处理过程中可能会引入一系列的错误。这是主动攻击的一个例子，此攻击无法被语义安全性覆盖。

Another, possibly even more severe attack, is the situation where the adversary somehow gains the ability to decrypt certain ciphertexts, or glean some information about their content (perhaps by watching the external behavior of the client after decrypting them). This may make it possible to the attacker to mount (perhaps limited) chosen-ciphertext attacks, which may make it possible to compromise the security of encrypted data. Such attacks are not addressed by the semantic security guarantee, countering them requires additional measures beyond the use of homomorphic encryption.

另一个可能更加严重的攻击方法是攻击者能得到解密一部分密文的能力，或者通过外部手段获得一部分明文的信息（例如通过观察客户端解密密文后的行为）。这种类型的攻击使得攻击者具有（可能是受限的）选择密文攻击能力，可能破坏加密数据的安全性。此类攻击无法被语义安全性涵盖，抵御此类攻击需要在使用同态加密的基础上进一步增加其他安全机制。

c. 求值隐私性（Evaluation Privacy）

A desirable additional security property beyond semantic security would be that the ciphertext $C$ hides which computations were performed homomorphically to obtain $C$. We call this security requirement *Evaluation Privacy*.

另一个比语义安全性更高且可能会用到的安全特性是密文$C$本身隐藏了获得$C$的同态处理过程。我们称此安全特性为*求值隐私性*。

For example, suppose a cloud service offers a service in the form of computing a proprietary machine learning algorithm $F$ on the client's sensitive data. As before, the client encrypts its data $M$ to obtain $C$ and sends the cloud $C$ and the evaluation key $EK$. The cloud now computes $C'$ which is an encryption of $F(M)$ to hand back to the client. Evaluation privacy will guarantee that $C'$ does not reveal anything about the algorithm $F$ which is not derivable from the pair $(M, F(M))$. Here we can also distinguish between semi-honest and malicious evaluation privacy depending on whether the ciphertext $C$ is generated correctly according to the Encrypt algorithm.

例如，假设一个云服务商提供了一个在客户敏感数据上执行适当机器学习算法$F$的服务。与之前相同，客户加密数据$M$，得到密文$C$，并将$C$和求值密钥$EK$发送给云服务商。云服务商计算$F(M)$的密文$C$，并将结果返回给客户。求值隐私性要保证$C'$不会泄露除根据$(M, F(M))$可推断得到的信息外与算法$F$相关的任何信息。我们仍然可以根据$C$是否必须有加密算法正确生成的这一攻击假设，将求值隐私性分为半诚实/恶意求值隐私性。

A weaker requirement would be to require evaluation privacy only with respect to an adversary who does not know the secret decryption key. This may be relevant for an adversary who intercepts encrypted network traffic.

一个弱化的安全要求是，满足求值隐私性要求攻击者无法知道解密密钥。这相当于攻击者可以窃听加密通信网络的密文，从而根据密文获取求值算法的计算过程。

d. 密钥演化（Key Evolution）

Say that a corpus of ciphertexts encrypted under a secret key $SK$ is held by a server, and the client who owns $SK$ realizes that $SK$ may have been compromised.

假定服务端持有一系列用私钥$SK$加密的密文，客户端持有$SK$。客户端现在意识到$SK$可能被泄露了。

It is desirable for an encryption scheme to have the following *key evolution property*. Allow the client to generate a new secret key $SK'$ which replaces $SK$, a new evaluation key $EK'$, and a transformation key $TK$ such that: the server, given only $TK$ and $EK'$, may convert all ciphertexts in the corpus to new ciphertexts which (1) can be decrypted using $SK'$ and (2) satisfy semantic security even for an adversary who holds $SK$.

此时，我们期望加密方案满足下述*密钥演化特性*。允许客户端生成一个代替$SK$的新私钥$SK'$，一个新的求值密钥$EK'$，一个转换密钥$TK$，使得仅给定$TK$和$EK'$，服务端可以将所有密文转换为新的密文，并满足：（1）新密文可以由$SK'$解密；（2）即使攻击者持有$SK$，新密文也满足语义安全性。

Any sufficiently homomorphic encryption scheme satisfies the key evolution property as follows. Let $TK$ be the encryption of $SK$ under $SK'$. Namely, $TK$ is a ciphertext which when decrypted using secret key $SK'$ yields $SK$. A server given $TK$ and $EK'$, can convert a ciphertext $C$ in the corpus into $C'$ by homomorphically evaluating the decryption process. Security follows from semantic security of the original homomorphic encryption scheme.

任意足够完备的同态加密方案均满足密钥演化特性。令$TK$为$SK$在$SK'$下的加密结果。也就是说，$TK$是一个密文，用$SK'$解密$TK$得到的明文是$SK$。给定$TK$和$EK'$，服务端可以通过同态运算执行解密步骤，从而将密文$C$转换为$C'$。此方案的安全性依赖于原始同态加密方案的语义安全性。

e. 侧信道攻击（Side Channel Attacks）

Side channel attacks consider adversaries who can obtain partial information about the secret key of an encryption scheme, for example by running timing attacks during the execution of the decryption algorithm. A desirable security requirement from an encryption scheme is resiliency against such attacks, often referred to as *leakage resiliency*. That is, it should be impossible to violate semantic security even in presence of side channel attacks. Naturally, leakage resilience can hold only against limited information leakage about the secret key.

侧信道攻击考虑的问题是，攻击者可以获得某个加密方案中私钥的部分信息，例如攻击者在执行解密算法的过程中发起攻击。如果期望加密算法能抵御此种类型的攻击，这称此加密方案满足*抗泄漏性*。也就是说，即使通过侧信道攻击，也无法破坏方案的语义安全性。一般来说，抗泄漏性只能抵御有限量的密钥信息泄露。

An attractive feature of encryption schemes based on intractability of integer lattice problems, and in particular known HE schemes based on intractability of integer lattice problems, is that they satisfy leakage resilience to a great extent. This is in contrast to public-key cryptosystems such as RSA.

已有同态加密方案都依赖于整数格问题，而基于整数格问题的加密方案具有一个非常有吸引力的特性：方案在很大程度上可以满足抗泄露性。这与RSA等公钥密码学系统有很大的不同。

f. 基于身份加密（Identity-Based Encryption）

In an Identity-Based Encryption scheme it is possible to send encrypted messages to users without knowing either a public key or a secret key, but only the identity of the recipient where the identity can be a legal name or an email address.

基于身份加密可以在不知道用户公钥和私钥，只知道接收方身份的条件下向此用户发送加密消息，而接收方身份可以为合法姓名或电子邮件地址。

This is possible as long as there exists a trusted party (TP) that publishes some public parameters $PP$ and holds a master secret key $MSK$. A user with identity $X$ upon authenticating herself to the TP (e.g. by showing a government issued ID), will receive a secret key $SK_X$ that the user can use to decrypt any ciphertext that was sent to the identity $X$. To encrypt message $M$ to identity $X$, one needs only to know the public parameters $PP$ and $X$.

只要存在一个可信参与方（TP）公开一些公开参数$PP$并持有主私钥$MSK$，基于身份加就是可构造的。身份为$X$的用户经过TP授权后（可以通过初始政府发布的ID来完成授权），将收到一个私钥$SK_X$。用户可以使用此私钥解密发送给身份$X$的任意密文。只需要知道公开参数$PP$和身份$X$，就可以给身份$X$加密消息。

Identity-Based Homomorphic Encryption is a variant of public key homomorphic encryption which may be desirable.

基于身份同态加密是公钥同态加密的一个变种，在实际中也有相应的应用场景。对GSW进行适当修改，就可以把GSW协议修改为基于身份同态加密。

**Remark**: A modification of GSW supports Identity-Based Homomorphic Encryption.

同态加密标准附录：期望扩展的内容（Homomorphic Encryption Standard Appendix: Anticipated Extensions to this Document）

This document is only a first step in standardizing various aspects of homomorphic encryption, and we expect many other aspects to be standardized in future documents. Some aspects that were not specified here and we expect to be specified in future versions include the following:

• The homomorphic encryption scheme for approximate numbers by Cheon, Kim, Kim and Song \[CKKS17\], which is mentioned in Section 1.1.5.
• Homomorphic encryption based on Module LWE, mentioned in Section 2.1.1.
• Concrete parameters and sampling methods for non-power-of-two cyclotomic rings, as discussed in Section 2.1.3.
• Parameter choices when using sparse secret key, as mentioned in Section 2.1.3.