第一部分 —— 密文类型

文章目录

1. Abstract
- 1.1 Some Conceptions
2. TFHE Ciphertexts
3. GLWE
- 3.1 Trivial GLWE ciphertexts
- 3.2 LWE 和 RLWE
- 3.3 Public key encryption
4. GLev
- 4.1 Lev and RLev
5. GGSW
- 5.1 GSW and RGSW

1. Abstract

TFHE 指的是 全同态加密策略。意思是，允许对密文进行运算，等价于对明文进行运算。TFHE 最初是作为 FHEW 方案的改进而提出的，然后开始向更广泛的方向发展。
该方案的 安全性 基于一个称为 带错误学习 (LWE) 的 困难格问题，及其变体，如 Ring LWE (RLWE)。事实上，目前使用的大多数 FHE 方案 都是 基于LWE 的，并且 使用有噪声的密文。
然而，TFHE 与其他方法的区别在于，它提出了一种 特殊的自举 (bootstrapping)，这种自举 速度非常快，能够在 降低噪声的同时评估函数。

在我们详细讨论 bootstrapping 之前，有必要写几篇博文，所以现在不要急于理解它是如何工作的。让我们从头开始描述 TFHE 中使用的密文。

1.1 Some Conceptions

$R = Z[X] / (X^N + 1)$ ：表示 整数多项式环 (ring of integer polynomials) 模圆分多项式 (cyclotomic polynomial) $X^N+1$ ，N 是 2 的幂。实际上，它包含 一个 N-1 阶的整数多项式。
$R_q = (Z / qZ) [X] / (X^N + 1)$ ：和上面相同的 整数环 R，但是这次 系数是模 q。注意，我们通常将 $Z / qZ$ 记为 $Z_q$ 。
我们的 模数约简 以零为中心。例如，当对 8 进行 模数约简 时，我们使用 同余类 ${-4,-3,-2,-1,0,1,2,3\}$ ，即 $[- q /2, q /2)$ 。
$\chi_{\mu,\sigma}$ ：是一个 均值 (mean) 为 $\mu$ 标准差为 $\sigma$ 高斯概率分布。如果 $\mu = 0$ ，则简记为 $\chi_\sigma$ 。
用 小写字母 表示 整数 (模) (a, b, m, s, …)，使用 大写字母 表示 多项式 (A, B, M, S, …)。
MSB 表示 最高有效位，LSB 表示 最低有效位。
$\lfloor\rceil$ ：表示舍入取整到最近的整数。

2. TFHE Ciphertexts

在 TFHE 中，我们主要使用三种类型的密文：LWE、RLWE、RGSW 密文。
为什么需要分为三类密文，原因是它们都 具有不同的属性，这些属性将在我们将在以下博客文章中描述的同态运算中有用。它们都具有 依赖于 LWE 问题或其变体的安全性。要了解有关 LWE 安全性的更多信息，请查看此博客文章。

这些密文不仅用于 TFHE，也用于其他基于 LWE 的 FHE 方案。

GLWE (General LWE) - LWE 和 RLWE 密文的概括
GGSW (General GSW) - RGSW 密文的概括
GLev - 一种 中间密文类型，对于更好地理解 GGSW 密文非常有用，并且我们将在后续的博客文章中大量使用它

3. GLWE

在本节中，我们将使用包含 LWE 和 RLWE 密文的概括，称为 General LWE，或简称 GLWE。
要生成任何类型的密文，我们首先需要一个密钥。对于 GLWE 密文，密钥是 R 中 k 个随机多项式 的列表 (每个 Si 都是一个 随机多项式)：
$\overrightarrow{S} = (S_0,...,S_{k-1}) \in R^k$ 具体地，R 元素的系数可以从均匀二元分布、均匀三元分布、高斯分布或均匀分布中采样。
在本系列博客文章中，与原始 TFHE 描述一样，我们将假设我们的密钥是从 均匀二进制分布 中采样的。

现在看看如何 加密消息。令 q 和 p 为两个正整数，且 p <= q，并定义 $\Delta = q/p$ 。在 TFHE 中，q 和 p 通常被选为 2 的幂：如果不是，则应在 消息编码时 进行 四舍五入。
我们将 q 称为 密文模数，p 称为 明文模数， $\Delta$ 称为 缩放因子。让我们考虑一条 消息 $\in R$ 。使用 密钥 $\overrightarrow{S}$ 加密 消息 M 的 GLWE 密文 是一个 元组 (tuple)：
$(A_0,...,A_{k-1},B) \in GLWE_{\overrightarrow{S},\sigma}(\Delta M)\subseteq R_{q}^{k+1}$ 其中，A_i 是从 R_q 中 均匀随机抽样 出来的 (A_i 是一个 N次多项式，系数 模 q，这个在第一部分 “一些概念” 中有提到)。并且 $\sum_{i=0}^{k-1}{A_i * S_i} + \Delta M + E \in R_q$ ，且 $\in R_q$ 的参数是从 高斯分布 $\chi_{\sigma}$ 中采样出来的。

多项式乘法 A_i * S_i 记得模 (Xⁿ+1)。
上面 $\Delta$ 和 E 都是数，等价于常数多项式
M 被编码到一个多项式中
E 就是噪声，即 noise error

我们通常称 $A_0,...,A_{k-1})$ 为 mask，称 B 为 body。多项式 $\Delta M$ 就是常说的 M 的编码。
注意，为了计算 $\Delta M$ ，我们将 消息 M 编码到 R_q 中 (作为多项式)。而且，每次我们加密一条消息，都采用 新的随机性 (mask 和 noise error)。
在 密钥 S 下，具有 标准差 为 $\sigma$ 的 高斯噪声 的 相同编码 $\Delta M$ 的 GLWE 加密集，将被记为 $GLWE_{\overrightarrow{S},\sigma}(\Delta M)$ 在这里插入图片描述
现在，如果我们有一个 密文 $(A_0,...,A_{k-1},B) \in GLWE_{\overrightarrow{S},\sigma}(\Delta M)\subseteq R_{q}^{k+1}$ ，密钥为 $\overrightarrow{S} = (S_0,S_1,...,S_{k-1}) \in R^k$ ，然后我们便可以进行解密：

$\sum_{i=0}^{k-1} A_i * S_i = \Delta M + E \in R_q$
$\lfloor (\Delta M + E)/\Delta \rceil$
观察到 消息 M 位于 $\Delta M+E$ 的 MSB 部分 (由于乘以 $\Delta$ )，而 E 位于 LSB 部分。
如果 $\Delta / 2$ (如果 E 的每个系数 e_i 都有 $|e_i| < \Delta / 2$ )，则解密的第二部如期返回 M。如果 error 不符合条件，则解密不正确。在下图中，我们表示 $\Delta M + E$ 的第 i 个系数。

可以看示例：博文中的 Toy example 部分

3.1 Trivial GLWE ciphertexts

在下一篇博文中，我们有时会使用所谓的 Trivial GLWE ciphertexts。这些密文不是真正的加密，因为它们隐藏了信息，但必须更多地将其视为 占位符：它们实际上 具有 GLWE 密文的形状，但 消息是明文。一个 Trivial GLWE ciphertexts 将所有的 A_i 设为 0，B 设为 $\Delta M$ 。
$(0,0,...,0,\Delta M) \in R_{q}^{k+1}$ 这些密文不是用来加密敏感信息的！在下一篇文章中，将展示如何使用它们在 同态计算 中注入 公开已知的数据。

3.2 LWE 和 RLWE

现在讨论如何从 GLWE 密文 中获取 LWE 密文 和 RLWE 密文。

当使用 $\in Z 和 N = 1$ (k 表示密钥 S 包括 k 个 N 阶多项式，N 表示多项式的次数) 实例化 GLWE 时，我们将获得 LWE。可以观察到，当 N = 1 时，R_q 就是 Z_q。在这里插入图片描述
当使用 $k = 1 和 N = 2^r$ 实例化 GLWE 时，我们获得 RLWE。

3.3 Public key encryption

上面使用私钥进行加密的，也可以使用公钥进行加密，详细内容在该论文中。

4. GLev

Glev 的主要作用是，识别 GLWE 和 GGSW 密文 之间的 中间密文类型，同时使 GGSW 密文 更易于理解。GLev 可以看作是 BGV 中使用的众所周知的 2 的幂加密 的泛化。

一个 Glev 密文包含冗余：它由一组使用 不同的、非常精密的缩放因子 $\Delta$ 加密 相同消息 M 的 GLWE 密文 组成。 $\Delta$ 由两个非常重要的参数来定义：

基数 β，通常是 2 的幂
级数 ℓ

$(GLWE_{\overrightarrow{S}, \sigma}(\frac{q}{\beta ^ 1} M) \times ... \times GLWE_{\overrightarrow{S}, \sigma}(\frac{q}{\beta ^ \ell} M)) = Glev_{\overrightarrow{S},\sigma}^{\beta,\ell}(M) \subseteq R_{q}^{\ell \cdot (k+1)}$ 如果 β 和 q 不是 2 的幂，在编码的时候就应该使用一个 rounding (取整操作)。