Large-Precision Sign using PBS

参考文献：

1. [CLOT21] Chillotti I, Ligier D, Orfila J B, et al. Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE[C]//Advances in Cryptology–ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part III 27. Springer International Publishing, 2021: 670-699.
2. [LMP22] Liu Z, Micciancio D, Polyakov Y. Large-precision homomorphic sign evaluation using FHEW/TFHE bootstrapping[C]//International Conference on the Theory and Application of Cryptology and Information Security. Cham: Springer Nature Switzerland, 2022: 130-160.

[CLOT21] 提出了 WoP-PBS，它基于事实 $(?1)?(?m)=m$，先将 $m$ 扩展为 $\beta \Vert m$，然后使用 GenPBS 分别计算出 $(?1{)}^{\beta }?f(m)$ 和 $(?1{)}^{\beta }$，最后使用 FV-like 同态乘法，将它们组合成 $f(m)$。这需要底层的 LWE 同时支持加法和乘法，并且同态乘法导致了噪声增长。因此，模数（正确性）和维度（安全性）都会相应的变大，导致它比一般的 FHEW/TFHE 的效率更至少一倍。

[LMP22] 也是将 $m$ 扩展到 $\beta \Vert m$，单它首先将 $\beta$ 消除掉使之成为 $0\Vert m$，接着使用原始的 PBS 就可以计算出正确的 $f(m)$。在这个过程中，并不需要使用同态乘法，因此它的噪声就是 PBS 本身的噪声，常规的参数就足够使用。

Homomorphic Floor Function

首先，[LMP22] 研究了如何对于高精度 LWE 密文执行自举。这里的 “精度” 指的是 MSD 编码的消息的比特长度。我们先给出一些参数定义：

• LWE：
  • 维度 $n$，不需要是二的幂
  • 模数 $Q$，是二的幂，用于 LWE 同态运算
  • 模数 $q$，是二的幂，用于 PBS 自举
  • 缩放因子 $\alpha$，是二的幂，用于纠错
  • 噪声界 $\beta$，是二的幂
• ACC：
  • 多项式长度 $N$，是二的幂
  • RLWE 密文模数 $Q^{\prime }$，是满足 $2N\mid Q^{\prime }?1$ 的素数
  • 输入 LWE 密文模数 $q\mid 2N$
  • 输出 LWE 密文模数 $Q$

FHEW/TFHE 要求 LWE 的密文模数满足 $Q\mid 2N$，随着明文精度的增加（$k$ 比特），多项式长度 $N$ 指数级增加（$2^k$ 倍）。对于通常的参数集 $N=1024/2048$，只能支持至多 $3,4$ 比特的明文精度。[LMP22] 为了计算高精度的 Sign 函数，通过不断移除 LSD（保持 MSB 不变），直到密文模数 $Q$ 倍缩减到 $q$ 规模，从而可以使用常规参数集执行 PBS。

这个过程中，一个关键步骤是同态 Floor 函数。假设 LWE 密文 $(c,d)\in {\mathbb{Z}}_Q^{n+1}$ 的相位是：
$$\psi =\alpha ?m+e(\mathrm{mod}Q)$$
其中 $|e|\le \beta ?q$，$m\in {\mathbb{Z}}_{Q/\alpha }$，根据不同的场景 $\alpha$ 选取不同的值。

注意到 $Q>q>\alpha$ 都是二的幂次。如果我们将 LWE 密文模掉 $q$，获得的 $(a,b)\in {\mathbb{Z}}_q^{n+1}$：
$$[m^{\prime }{]}_q=\alpha ?[m{]}_{q/\alpha }+e(\mathrm{mod}q)$$
使用 PBS 将它提升回 $(a^{\prime },b^{\prime })\in {\mathbb{Z}}_Q^{n+1}$，并从原始密文中把它减掉，就清除了 $m$ 的最低 $\log q/\alpha$ 比特。密文 $(c^{\prime },d^{\prime })$ 的相位是：
$${\psi }^{\prime }=\alpha ?\left(?\frac{\alpha }{q}m??\frac{q}{\alpha }\right)+e^{\prime }(\mathrm{mod}Q)$$
现在，我们可以把 $\alpha ,Q$ 同时缩小 $q/\alpha$ 倍，得到的密文 $(c^{\prime \prime },d^{\prime \prime })\in {\mathbb{Z}}_{(\alpha /q)?Q}^{n+1}$ 相位的 MSB 保持和 $(c,d)\in {\mathbb{Z}}_Q^{n+1}$ 的一样。

我们将这个长度 $\log (q/\alpha )$ 的小块明文称为 LSD，我们的目标是将它清零。然而，函数 $f:m\in {\mathbb{Z}}_{q/\alpha }?m\in {\mathbb{Z}}_{Q/\alpha }$ 并非反循环的，导致了原始的 PBS 无法实现从 $(a,b)$ 到 $(a^{\prime },b^{\prime })$ 的自举过程。[LMP22] 给出了两种实现，通过 $2,3$ 次 PBS 来实现它。用到的三个函数为：

为了构造 LUT 的方便，下面的推导中总是使得 PBS 输入的密文噪声是正整数，范围是 $[0,2\beta )$。这可通过 $(c,d)\to (c,d+\beta )$ 来实现。只要满足 $\alpha \ge 2\beta$，就可以准确解密。FHEW/TFHE 中的 LWE 私钥 s ∈ { 0 , ± 1 } n s \in \{0,\pm1\}^n s∈{0,±1}n 服从三元分布。

Using 2 PBS

[LMP22] 的第一个方法：使用两次 PBS，但是对于噪声的约束较强，$\alpha \ge 4\beta$

基本思路：分别提取 $([c{]}_q,[d{]}_q)$ 相位（加密了 LSD）的 MSB 和其他位置，

1. 先提取 $([c{]}_q,[d{]}_q)$ 的 MSB，将它从 $(c,d)\in {\mathbb{Z}}_Q^{n+1}$ 中移除。现在 $([c^{\prime }{]}_q,[d^{\prime }{]}_q)$ 的相位只位于半个环面上。
2. 再提取 $([c^{\prime }{]}_q,[d^{\prime }{]}_q)$ 的消息，将它从 $(c^{\prime },d^{\prime })\in {\mathbb{Z}}_Q^{n+1}$ 中移除。现在 $([c^{\prime \prime }{]}_q,[d^{\prime \prime }{]}_q)$ 的相位是零。
3. 将 $(c^{\prime \prime },d^{\prime \prime })$ 缩放 $q/\alpha$，降低密文模数。

假定 PBS 输出的噪声界是 $\beta$，初始输入 ($c,d)$ 的噪声上界也是 $\beta$，

• HomFloor：
  • 输入噪声范围 $(?\beta ,\beta )$，执行 step 2 噪声范围 $(0,2\beta )$，
  • 执行 step 4,5，噪声范围是 $(0,4\beta )$，这里需要 $\alpha \ge 4\beta$，使得这个噪声不会影响到我们刚刚消除掉的 MSB，从而此时的 $(c,d)$ 相位是 $\tilde{m}q+x$，其中 $x\in [0,q/2)$ 包含了 LSD 以及噪声
  • 执行 step 6 和 step 7，获得相位 $x+e$ 的密文，从 $(c,d)$ 中减掉后，返回的相位是 $\tilde{m}q+e$（注意函数 $f_1:x\in {\mathbb{Z}}_{q/2}?x\in {\mathbb{Z}}_{q/2}$，整个 $x$ 都被清零，包括本来的噪声），满足 $|e|<\beta$
• HomSign：
  • 输入噪声范围 $(?\beta ,\beta )$，执行 HomFloor 输出的噪声范围也是 $(?\beta ,\beta )$，
  • 执行 step 13 的模切换，噪声规模是 $\alpha /q?\beta +(\Vert s{\Vert }_1+1)/2$，
  • 假如满足 $\Vert s{\Vert }_1=O(n)\le \beta$，并且假设 $q\ge 4\alpha$ 以及 $\beta \ge 2$，那么就有 $\alpha /q?\beta +(\Vert s{\Vert }_1+1)/2<\beta$，因此可以正确地执行 HomFloor
  • 执行 step 17 虽然噪声规模可能超过 $\alpha$，但是并不会影响 MSB 的值，因此可以正确地执行 Boot，最终的噪声范围是 $(?\beta ,\beta )$

当然，上述的分析是最坏情况的。如果使用平均情况，那么 $\Vert s{\Vert }_2=O(\sqrt{n})$，独立密文的加和噪声界 $\sqrt{2}\beta$，可以将 $\beta$ 和 $\alpha$ 都降低一些。

Using 3 PBS

为了给出通用的算法（尤其是 CKKS 的噪声和明文混合在一起），[LMP22] 给出了第二个方法：使用三次 PBS，支持任意的噪声，$\alpha \ge 2\beta$

基本思路：

1. 首先消除 $([c{]}_q,[d{]}_q)$ 相位的第二高比特。现在（正的）噪声向上传播时，遇到被清零的第二高比特后，不再继续向 MSB 传递影响。
2. 利用上一小节的算法，清理掉 LSD，然后模切换。

假定 PBS 输出的噪声界是 $\beta$，初始输入 ($c,d)$ 的噪声上界也是 $\beta$，

• HomFloorAlt：
  • 输入噪声范围 $(?\beta ,\beta )$，相位是 $\tilde{m}q+bq/4+x$，其中 b ∈ { 0 , 1 , 2 , 3 } , x ∈ [ 0 , q / 4 ) b \in \{0,1,2,3\},x \in [0,q/4) b∈{0,1,2,3},x∈[0,q/4)，这里的 $x$ 包含了噪声项
  • 执行 step 3,4 将 LSD 的第二高比特置为零，相位形如 $\tilde{m}q+\tilde{b}q/2+x+e$，其中 b ~ ∈ { 0 , 1 } \tilde b \in \{0,1\} b~∈{0,1}，噪声为 $e\in [0,2\beta )$
  • 假设满足 $q\ge 8\beta$，那么 $x+e<q/4+2\beta \le q/2$，它们不会改变 $b$ 的值，因此并不会继续向更高的 $\tilde{m}$ 传播影响
  • 执行 step 6,7 清理掉 $b$ 的值，现在的相位是 $\tilde{m}q+x+e+e^{\prime }$，它的 LSD 是 $x+e+e^{\prime }$，其中 $e^{\prime }\in [0,2\beta )$
  • 进一步假设 $q\ge 16\beta$，那么满足 $x+e+e^{\prime }<q/4+4\beta \le q/2$，它落在了半环内
  • 执行 step 9 清理掉它们，新的噪声是 $e^{\prime \prime }\in (?\beta ,\beta )$
• HomSign：
  • 简单使用 HomFloorAlt 作为子例程，分析是一样的

PBS of Arbitrary Function

利用上述 HomFloor 的计算思路，为了利用 PBS 计算任意函数，我们可以将 $m\in {\mathbb{Z}}_{q/\alpha }$ 扩展到 b ∥ m ∈ { m , m + q / α } ? Z 2 q / α b\|m\in\{m,m+q/\alpha\} \subseteq \mathbb Z_{2q/\alpha} b∥m∈{m,m+q/α}?Z2q/α?（随机的 b ∈ { 0 , 1 } b\in \{0,1\} b∈{0,1}），然后提取 sign 消除为 $(0\Vert m{)}_2=m$，接着使用半环上的函数执行 PBS 即可。

现在我们假定输入的 LWE 密文模数是 $q$，满足 $2q\mid 2N$ 可以被原始 PBS 支持。这导致相较于 HomFloor 中的 PBS，这里的 $q$ 更小，明文精度丢失了 $1$ 比特。

Homomorphic Digit Decomposition

为了执行 [GBA21] 的 Tree-based PBS（包括高精度 LWE 密文的自举），我们需要同态数字分解算法。因为 HomFloor 事实上就是在计算各个 Digit，并将它们从高精度 LWE 密文中减去的过程，因此仅需追踪此过程中产生的 $([c{]}_q,[d{]}_q)$ 即可。

输入 LWE 密文的相位 $\alpha ?m+e$，输出 $k=\log (Q/\alpha )/\log (q/\alpha )$ 个密文，它们的相位是 $\alpha ?m_i+e_i$，满足 $m={\sum }_{i=0}^{k?1}{m}_i?(q/\alpha {)}^i$

Parameter Selection

略。。。