消除 TFHE 的限制：WoP-GenPBS

参考文献：

1. [CIM19] Carpov S, Izabachène M, Mollimard V. New techniques for multi-value input homomorphic evaluation and applications[C]//Topics in Cryptology–CT-RSA 2019: The Cryptographers’ Track at the RSA Conference 2019, San Francisco, CA, USA, March 4–8, 2019, Proceedings. Springer International Publishing, 2019: 106-126.
2. [CGGI20] Chillotti I, Gama N, Georgieva M, et al. TFHE: fast fully homomorphic encryption over the torus[J]. Journal of Cryptology, 2020, 33(1): 34-91.
3. [GBA21] Guimar?es A, Borin E, Aranha D F. Revisiting the functional bootstrap in TFHE[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021: 229-253.
4. [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.

[CLOT21] 优化 TFHE 方案，添加了额外的运算和特性，

1. FHEW/TFHE 中的 LWE 仅支持线性同态，[CLOT21] 添加了 FV-like 同态乘法，以及 LWE 打包在 RLWE 系数上做批处理
2. FHEW/TFHE 的自举是关于 MSB 的，[CLOT21] 使用模切换构造两个小窗口，推广为了 GenPBS
3. FHEW/TFHE 只能处理反循环函数，[CLOT21] 通过组合 2、3 个 GenPBS，获得了 WoP-PBS
4. [CIM19] 的 Multi-value PBS 采取 ACC 乘以不同的 Test Vector 来同时执行多个 PBS，但这增大了噪声（可能需要提升多项式长度以容错）。[CLOT21] 利用模切换构造出无噪声的小窗口，直接在 LUT 中写入多个函数（本身就需要够长的多项式）做批处理，因此噪声和 GenPBS 是一样的。
5. [CLOT21] 利用 GenPBS 的小窗口，对消息的特定区块自举，给出了整数运算的同态进位，从而可以搭建出高精度整数的运算
6. [CLOT21] 还提出同态数字分解，这可以和 [GBA21] 的 Tree-PBS 联合使用（它需要将高精度明文用多个 LWE 加密）

Building Blocks

GLWE & GLev & GGSW

方便起见，[CLOT21] 描述了三种密文（对称加密）。TFHE 使用 ${\mathbb{Z}}_q?\frac{1}{q}\mathbb{Z}/\mathbb{Z}$ 来模拟实数环面，模数 $q$ 总是二的幂次。

GLWE 密文：私钥 $S=(S_1,?,S_k)\in R_q^k$，
$$GLW{E}_S(\Delta M):=\left(A_1,?,A_k,B=\sum _i{A}_i{S}_i+?\Delta M?+E\right)\in R_q^{k+1}$$
其中 $A_i\in R_q$ 是均匀的，$S_i,E\in R_q$ 是短噪声。

GLev 密文：数字分解基底 $B\in {\mathbb{N}}^{+}$，$l=?{\log }_{B}q?$，
$$Gle{v}_S(M):={\left\{GLW{E}_S\left(M?\frac{q}{B^i}\right)\right\}}_{i=1,?,l}\in R_q^{(k+1)\times l}$$
数字分解算法满足
$$?de{c}^{B,l}(a),(\frac{q}{B^1},?,\frac{q}{B^l})?=?a?\frac{B^l}{q}??\frac{q}{B^l}\in R_q,?a\in R_q$$
GGSW 密文：设置 $S_{k+1}=?1$，
G G S W S ( M ) : = { G L e v S ( ? S i M ) } i = 1 , ? ? , k + 1 ∈ R q ( k + 1 ) × l ( k + 1 ) GGSW_S(M) := \left\{GLev_S\left(-S_iM\right)\right\}_{i=1,\cdots,k+1} \in R_q^{(k+1) \times l(k+1)} GGSWS?(M):={GLevS?(?Si?M)}i=1,?,k+1?∈Rq(k+1)×l(k+1)?
TFHE 中的不同部件采取不同的密文类型：

• 加密消息：使用 LWE 密文，秘钥 $S=(S_1,?,S_k,?1)$，加密单个整数值 $m\in {\mathbb{Z}}_t$
• 秘钥切换：
  • PrivKS：秘密的线性态射 $f$，使用 GLev 密文，加密 $f(0,?,S_i,?,0)$
  • PubKS：公开的线性态射 $f$，使用 GLev 密文，加密 $S_i$
  • PackingKS：就是 PubKS，其中的线性态射是一个置换
• 盲旋转：
  • ACC：使用 GLWE 密文，加密多项式 $P_f$，它编码了非线性函数 $f$ 的 redundant LUT（冗余重复 $r$ 次）
  • Selector：使用 GGSW 密文，加密 $S_i$（GINX 版本的自举，CMux-Based BDD）

在原始 FHEW/TFHE 中，LWE 密文仅支持同态线性运算。因为噪声比率很大，所以 LWE 的模数和维度都很小，从而具有高效的自举程序。

LWE 密文的模数需要满足 $q\mid 2N$。为了盲旋转的效率，GLWE 密文的维度 $N$ 规模大约是 $1024$。因此 LWE 的噪声比率较大，无法支持同态乘法。但是 ACC 的模数 $Q?q$ 很大，自举结果（模切换 $Q\to q$ 之前）的噪声可以降低到很低的水平。[CLOT21] 使用一个较大的 LWE 密文模数 $q?2N$，从而足够支持 LWE 同态乘法；在自举之前，将 LWE 密文模数从 $q$ 切换到 $2N$ 小模数。

LWE-Mult

[CLOT21] 首先回顾了 GLWE 密文的 FV-like 同态乘法（tensor product + relinearization），输入 $GLWE(M_1{\Delta }_1)$ 和 $GLWE(M_2{\Delta }_2)$，输出 $GLWE(M_1{M}_2?{\Delta }^{\prime })$，

接着 [CLOT21] 使用 PackingKS 过程，将单个 LWE 密文加密的消息，转化到某个 GLWE 密文的常数项。因此，GLWE 密文之间的 FV-like 同态乘法，其常数项就是原始 LWE 消息的乘积。最后从 GLWE 提取出常数项的 LWE 即可。

在后续的算法中，LWEMult 是关键的部件，被用于组合多个 PBS 的结果，搭建出 WoP-PBS（不需要 Pading 成为半环）

Packed-Mult

为了更高效地计算多个 LWE 密文的同态乘法，[CLOT21] 将它们的消息编码到 GLWE 所加密的多项式不同系数上。

多个独立的乘积：将两组 LWE 密文打包为两个 GLWE 密文，
f 1 ( X ) = ∑ j i ∈ { 0 , 1 , ? ? , α ? 1 } m i ( 1 ) X j i f 2 ( X ) = ∑ j i ∈ { 0 , α , ? ? , ( α ? 1 ) α } m i ( 2 ) X j i \begin{aligned} f_1(X) &= \sum_{j_i \in \{0,1,\cdots,\alpha-1\}} m_i^{(1)}X^{j_i}\\ f_2(X) &= \sum_{j_i \in \{0,\alpha,\cdots,(\alpha-1)\alpha\}} m_i^{(2)}X^{j_i}\\ \end{aligned} f1?(X)f2?(X)?=ji?∈{0,1,?,α?1}∑?mi(1)?Xji?=ji?∈{0,α,?,(α?1)α}∑?mi(2)?Xji??
容易看出，$f_1?f_2$ 的项 $X^{i?\alpha +i}$ 的系数恰为 $m_i^{(1)}{m}_i^{(2)}$，提取它们为 LWE 密文

多个乘积的加和：将两组 LWE 密文打包为两个 GLWE 密文，
f 1 ( X ) = ∑ j i ∈ { 0 , 1 , ? ? , α ? 1 } m i ( 1 ) X j i f 2 ( X ) = ∑ j i ∈ { α ? 1 , α ? 2 , ? ? , 0 } m i ( 2 ) X j i \begin{aligned} f_1(X) &= \sum_{j_i \in \{0,1,\cdots,\alpha-1\}} m_i^{(1)}X^{j_i}\\ f_2(X) &= \sum_{j_i \in \{\alpha-1,\alpha-2,\cdots,0\}} m_i^{(2)}X^{j_i}\\ \end{aligned} f1?(X)f2?(X)?=ji?∈{0,1,?,α?1}∑?mi(1)?Xji?=ji?∈{α?1,α?2,?,0}∑?mi(2)?Xji??
容易看出，$f_1?f_2$ 的项 $X^{\alpha ?1}$ 的系数恰为 ${\sum }_i{m}_i^{(1)}{m}_i^{(2)}$，提取它为 LWE 密文

对于多个独立的平方、多个平方的加和，也有类似的算法。很简单，详见 [CLOT21]，略。

注意 [CLOT21] 是将 LWE 的整数采取 Coeff Packing 编码在 GLWE 的多项式上，多项式乘积的系数包含了大量的无用结果，为了不发生回绕多项式的长度 $N$，支持的并行数 $\alpha \le O(\sqrt{N})$ 是很受限的。而在 BGV/BFV 中是 SIMD 编码的，因此可以支持 $N$ 路并行。

Generalized PBS

Module-Switch

下面的所有参数都是二的幂次（这很关键）。[CLOT21] 使用一种特殊的模切换过程，在 LWE 密文上构造了两个小窗口：

将 $LWE(\Delta m)\in {\mathbb{Z}}_q^{k+1}$ 缩放到 $LWE({\Delta }^{\prime }m)\in {\mathbb{Z}}_{2N}^{k+1}$，

• 缩放前的相位中，长度 $\mu$ 比特的 MSB（消息的高位）被截掉
• 缩放后的相位中，长度 $\nu$ 比特的 LSB（噪声的低位）被置零

假设 $LWE(\Delta m)=(a_1,?,a_k,a_{k+1}=b)$，密文模数 $q$，明文模数 $t=q/\Delta$。模切换过程为：
$$a_i^{\prime }={\left[?\frac{2N?2^{\mu ?\nu }}{q}?a_i??2^{\nu }\right]}_{2N}$$
简记 $a_i^{\prime \prime }=\frac{2N?2^{\mu ?\nu }}{q}?a_i$，假设 $?\frac{2N?2^{\mu ?\nu }}{q}?a_i?=a_i^{\prime \prime }+{?}_i$，舍入噪声为 ${?}_i\in [?0.5,0.5)$，那么 $a_i^{\prime }=[(a_i^{\prime \prime }+{?}_i)?2^{\nu }{]}_{2N}$，它的最低 $\nu$ 比特是零。

对于 $s=(s_1,?,s_k,s_{k+1}=?1)$，解密为：
$$\begin{array}{rl}?a^{\prime },s?& =[?(a^{\prime \prime }+?)?2^{\nu },s?{]}_{2N}\\ & ={\left[\frac{2N?2^{\mu }}{q}??a,s?+2^{\nu }???,s?\right]}_{2N}\\ & ={\left[\frac{2N?2^{\mu }}{q}?(\Delta m+e+Iq)+2^{\nu }???,s?\right]}_{2N}\\ & ={\left[\left(\frac{\Delta ?2N?2^{\mu }}{q}?m+2N?2^{\mu }?I\right)+2^{\nu }?\left(\frac{2N?2^{\mu ?\nu }}{q}?e+??,s?\right)\right]}_{2N}\end{array}$$

其中的 $I$ 是 $?a,s?\in \mathbb{Z}$ 的 $2N$-Overflow，可以视为范围有界的随机数。其中的噪声项的最低 $\nu$ 比特是零。密文模数是 $2N$，缩放因子是 ${\Delta }^{\prime }=\frac{\Delta ?2N?2^{\mu }}{q}$，明文模数是 $t^{\prime }=\frac{q}{\Delta ?2^{\mu }}=t/2^{\mu }$

• 当 $\mu \ge 0$ 时 $t^{\prime }\le t$，相位 $[{\Delta }^{\prime }m+2N?2^{\mu }?k+e^{\prime }{]}_{2N}$ 的高位存放的是 $[m{]}_{q^{\prime }}$，原始 $m$ 的最高 $\mu$ 比特被截掉（上图中的 $\bar{m}$）。
  • 由于 FHEW/TFHE 的反循环限制，我们将 $[m{]}_{t^{\prime }}$ 的 MSB 记为 $\beta =[[m{]}_{t^{\prime }}\ge t^{\prime }/2]$，其余部分记为 $m^{\prime }=[m{]}_{t^{\prime }/2}$
• 当 $\mu <0$ 时 $t^{\prime }>t$，相位 $[{\Delta }^{\prime }m+2N?2^{\mu }?I+e^{\prime }{]}_{2N}$ 的高位存放的是 $[m+t?I{]}_{t^{\prime }}$，原始 $m$ 完全保留在它的低位，它的最高 $?\mu$ 比特存放的是 $I$ 的最低 $?\mu$ 比特。
  • 特别地，当 $\mu =?1$ 时，最高位 $\beta =[k{]}_2$ 是随机数，其余部分恰好是 $m^{\prime }=m$

GenPBS

利用上述的模切换过程，在执行 TFHE 的盲旋转之前，首先将 $R_q^{k+1}$ 上的 LWE 密文缩放到 $R_{2N}^{k+1}$ 上，它加密的明文是 $(\beta \Vert m^{\prime })$，其中 $m^{\prime }$ 用于查表，$\beta$ 用于判定 $m^{\prime }$ 位于哪个半环，计算结果为 $(?1{)}^{\beta }?f(m^{\prime })$

推广的 PBS 过程：

这么做的好处，

1. 假如 $m$ 的最高 $\mu$ 比特对于 $f$ 的计算没有影响，我们将它截掉，仅把其余部分缩放到在相位高位上，那么即使是较小的多项式长度 $N$， 它编码的 LUT 也有足够的冗余。
2. 缩放后相位的噪声最低 $\nu$ 比特都是零，因此盲旋转的距离总是 $2^{\nu }$ 倍数，从而相邻的 $2^{\nu }$ 个系数完全可以编码多个函数的 LUT，从而实现 PBS 的批处理。

WoP-PBS

对于原始的 FHEW/TFHE 自举，它仅能处理反循环的函数。为了计算任意函数，我们将 $m$ 的高位添加 Pading Bit（置为零），这使得 $(0\Vert m)$ 都落在半环内，因此将 $f$ 编码到多项式 $P_f$（它编码了半环的 LUT）即可计算出正确的 $f(m)$

然而这个技巧使得明文空间扩大了 $1$ 比特，为了足够的纠错冗余，也许会导致多项式长度 $N$ 翻倍（二的幂）。并且 LWE 执行同态线性计算后，总是需要保持 Padding Bit 是零（通过自举来实现）。[CLOT21] 利用上述的 GenPBS 和 LWEMult，实现了不需要 Pading Bit 的自举。

V1

第一个版本的 WoP-PBS，它使用两次 GenPBS：

1. 将影响 $f$ 的消息 $m^{\prime }$ 截下来，同时在 $m^{\prime }$ 高位补上一个无用的 $\beta$，
   1. 根据 $\beta \Vert m^{\prime }$，计算出 $(?1{)}^{\beta }?f(m^{\prime })$
   2. 根据 $\beta \Vert m^{\prime }$，计算出 $(?1{)}^{\beta }$
2. 使用 LWEMult，计算出 $f(m^{\prime })$

原始消息 $m$ 是直接放在 LWE 的最高比特上的，并没有 Padding Bit。我们用 $\mu ?1\ge 0$ 作为模切换的窗口（作用是在 $m^{\prime }$ 高位补 $\beta$），

• 对于 $\mu \ge 1$，因此 $\beta$ 就是 $m^{\prime }$ 更高一位的值（无用的）
• 对于 $\mu =0$，因此 $\beta$ 就是 $I$ 的最低一位的值（随机数）

算法如下：

因为消息 $m$ 填满 LWE 相位的最高位，因此 ${\mathbb{Z}}_t$ 上的同态运算是自然的，并不需要维持 Padding Bit 是零（必须用自举）。因此利用 LWEMult，我们可以将 TFHE 作为一个 Level FHE（同态加法、同态乘法），仅当噪声累积到临界时才执行 WoP-PBS 减少噪声。

V2

然而，上述算法事实上是将 $m$ 扩大为了 $\beta \Vert m$，因此依旧可能使得多项式长度 $N$ 扩大。[CLOT21] 提出另一种方法，类似于 [GBA21] 的 LUT 分块，令 $m=\beta \Vert m^{\prime }$，将任意函数 $f$ 分割为两个反循环函数 $f_0(m^{\prime })=f(0\Vert m^{\prime }),f_1(m^{\prime })=f(1\Vert m^{\prime })$，最后根据 $\beta =0/1$ 挑选出正确的半环 $f_{\beta }(m^{\prime })=f(m)$

算法如下：

分别计算 $f_0,f_1$ 需要 $2$ 个 GenPBS，提取 $\beta$ 也需要 $1$ 个 GenPBS，共计需要三个 GenPBS。假如采用 V1 会导致长度 $N$ 翻倍（两个 $O(2N\log 2N)$ 的 PBS），那么采用 V2 将会更快（三个 $O(N\log N)$ 的 PBS）。另外，采用 [CIM19] 的 Multi-value PBS 或者下面的 Multi-output PBS，这些 GenPBS 可以被批量处理，因此 V2 可能会更具优势。

Multi-output PBS

在 GenPBS 中，LWE 密文执行窗口为 $\mu ,\nu$ 的模切换之后，相位形如 $?=\Delta (\beta \Vert m^{\prime })+e?2^{\nu }\in {\mathbb{Z}}_{2N}$，因此盲旋转的距离 $X^{?}$ 总是 $2^{\nu }$ 倍数。换句话说，多项式 $P_f$ 中连续的 $2^{\nu }$ 个系数，只有一个系数被真的用于 LUT 查表。

[CLOT21] 选择将至多 $2^{\nu }$ 个函数的 LUT 同时写入到 $P_f$ 中，简记 $p=\frac{q}{\Delta ?2^{\mu +1}}$ 是不同取值的个数，冗余 LUT 形如：

在盲旋转（仅一次）的结果中，最低的那 $2^{\nu }$ 个系数，就编码了 $f_1(\beta \Vert m^{\prime }),?,f_{2^{\nu }}(\beta \Vert m^{\prime })$，可以提取出它们的 LWE 密文。

对比 [CIM19] 的 Multi-value PBS，它需要把 ACC 乘以各个函数的 Test Vector（FHEW-like），这导致了依赖于各个函数的噪声增长。上述的 PBS-manyLUT 直接把这些 LUT 写在了初始的 ACC 内（TFHE-like），噪声和原始的 GenPBS 完全相同。只不过在模切换中的噪声也被乘以 $2^{\nu }$，因此它可能需要够大的 $N$

我们可以将 WoP-PBS 和 PBS-manyLUT 组合起来：

• 使用 PBS-manyLUT 加强 WoP-PBS：将其中的 2、3 个 GenPBS 使用单个 PBS-manyLUT 来实现。开销是一个 PBS-manyLUT，效果是一个 WoP-PBS。
• 使用 WoP-PBS 加强 PBS-manyLUT：它本质上就是一个 GenPBS（仅仅是 $P_f$ 和 Extract 特殊），容易将它修改为 WoP-PBS 版本。开销是 2、3 个 PBS-manyLUT，效果是一个 WoP-PBS-manyLUT。

Faster Integer Arithmetic

Boolean

在原始的 FHEW/TFHE 中，LWE 密文包含 Padding Bit（总是置为零）。计算逻辑门的时候，拆分为线性部分和非线性部分，

1. 执行线性同态，利用 Padding Bit 存储线性部分的结果
2. 执行自举，对于 Padding Bit 的内容计算非线性部分，同时降低密文的噪声，以及将 Padding Bit 重新置为零

[CLOT21] 将消息直接加密在 LWE 密文的 MSB 上（没有 Padding Bit），作为 Level FHE 执行，

当噪声累积到临界值，我们执行 PBS 提取出 MSB 的低噪声密文。注意到提取 MSB 就是 Sign 函数，它可以被偏移为一个反循环函数（$0??0.5,1?0.5$），因此使用 GenPBS 就足够了。

Modular Power of 2

现在，我们从布尔逻辑 ${\mathbb{Z}}_2$ 扩展到整数算术 ${\mathbb{Z}}_{2^p}$

1. 同态加法 $Ad{d}_{2^p}$：密文的加法，$(c_1,c_2)?c_1+c_2$
2. 同态乘法 $Mu{l}_{2^p}$：使用 LWEMult 算法
3. 同态取反 $Op{p}_{2^p}$：密文的取反，$c??c$

由于 $p>1$，因此函数 $m?m$ 无法写成反循环形式，因此必须使用 WoP-PBS

假设函数 $m?m$ 可以写成某个反循环函数，$f(1\Vert m^{\prime })=?f(0\Vert m^{\prime })$，希望它经过偏移后计算出 $m$，也就是：对于任意的 $m^{\prime }\in [0,2^{p?1})$，都有
$$\begin{array}{rl}{m}^{\prime }& =f(0\Vert m^{\prime })+\beta \\ m^{\prime }+2^{p?1}& =f(1\Vert m^{\prime })+\beta \end{array}$$
这推出了 $2m^{\prime }=2\beta ?2^{p?1},?m^{\prime }\in [2^{p?1}]$，这是不可能的（除非 $p=1$）

Exact Integer

为了支持任意精度的整数算术，把整数分为几个精度 $2^p$ 的小块（Schoolbook Add/Mult），我们需要将给出同态的进位算法。

整数加法的进位，
$$Ad{d}_{2^p}^{MSB}(m_1,m_2):=?\frac{m_1+m_2}{2^p}?$$
整数乘法的进位，
$$Mu{l}_{2^p}^{MSB}(m_1,m_2):=?\frac{m_1?m_2}{2^p}?$$
[CLOT21] 的方法是，

1. 首先使用 PBS，将 $m_1,m_2$ 的空间放大 $p$ 比特，
2. 然后我们在空间 ${\mathbb{Z}}_{(2^p{)}^2}$ 上可以正确地模拟 $\mathbb{Z}$ 上的算术加法/乘法，它的高 $p$ 比特就存储了进位信息
3. 利用模切换技术，提取出 $m_1+m_2,m_1?m_2$ 的低 $p$ 位，进而可以用减法把这些无用数据清零

Faster Circuit Bootstrapping

GGSW 密文是由 $k+1$ 个 GLev 密文组成的，每个 GLev 密文包含 $l$ 个 GLWE 密文。确切地说，GGSW 的秘钥为 $S=(S_1,?,S_k,S_{k+1}=?1)$，那么
$$GGS{W}_S(m)={\left\{GLW{E}_S\left(?S_i?m?\frac{q}{B^j}\right)\right\}}_{i,j}$$
[CGGI17] 给出的电路自举（Circuit Bootstrapping），它将 LWE 密文（加密了数据）转换为 GGSW 密文（作为控制位），从而可以支持和 GLWE 密文的外积（搭建 Level FHE 自动机）。简单来说，

1. 输入 L W E K , q ( μ ) , μ ∈ { 0 , 1 } LWE_{K,q}(\mu),\mu \in \{0,1\} LWEK,q?(μ),μ∈{0,1}，使用 LWE-to-LWE PubKS 将它切换到 $LW{E}_{\underline{K},2N}(\mu )$
2. 使用 $l$ 次独立的 LWE-to-LWE PBS（Gate Bootstrapping），构建出 $LW{E}_{\overline{K},Q}\left(\mu ?\frac{Q}{B^j}\right),j=1,?,l$
3. 利用 $l(k+1)$ 次独立的 LWE-to-GLWE PrivKS，计算出 $GLW{E}_{K,q}\left(?K_i?\mu ?\frac{q}{B^j}\right),i=1,?,k+1,j=1,?,l$
4. 这些 GLWE 密文拼成了 $GGS{W}_{K,q}(\mu )$，可以和其他的 $GLW{E}_{K,q}({\mu }^{\prime })$ 做外积

具体算法为：

[CLOT21] 使用 PBS-manyLUT 批处理上述的 $l$ 个 PBS，从而减小电路自举的复杂度。各个函数为 $f_j:\mu ?\mu ?\frac{q}{B^j}$，分别扭曲为反循环形式，使用 GenPBS 计算它们。

Large Precision PBS

Homomorphically Decompose

利用带窗口的模切换技术，容易将加密了高精度数据 $\Delta m$ 的单个 LWE 密文，分解为若干个分别加密低精度分块 ${\Delta }_i{m}_i$ 的 LWE 密文，使得满足 $\Delta m={\sum }_i{\Delta }_i{m}_i$。注意这里的分解，是将 $m_i$ 之外的其他分块对应位置置为零，$m_i$ 依旧被放在原始的位置上（并非存放在最高位）。

我们依次提取出 LSB 部分，然后将它从整体中移除，剩下 MSB 部分。具体算法如下：

Tree-WoP-PBS

最后，我们可以将这个分解技术，和 [GBA21] 的 Tree-PBS（它要求输入数据被分块加密）组合使用。