PEGASUS : Bridging Polynomial and Non-polynomial Evaluations in Homomorphic Encryption

2021/10回顾：
这篇文章写的比较早了，当时关于PEGASUS其实也是一知半解，回过头来看发现这里的除了Linear Transform应该都是现有的技术，这篇文章主要是做了Batched RLWE到多个LWE之间的互相转换做LUT再打包回去。其中LWE执行LUT其实就是Functional Bootstrapping的技术，Extract和KeySwitch应该是出自陈昊的文章。

摘要：

同态加密（HE）被认为是保护隐私应用的最重要的原语之一。然而，在加密数据上评估多项式和非多项式函数的有效方法仍然缺乏，这阻碍了同态加密在现实生活中的应用。为了解决这个问题，我们提出了一个实用框架PEGASUS。PEGASUS可以在打包的CKKS密码文和FHEW密码文之间有效地来回切换，而无需解密，使我们可以在CKKS方面有效地评估算术函数，并在FHEW密码文上评估查找表（也就是非多项式函数）。我们的FHEW → CKKS转换算法比现有方法更实用。我们将计算复杂性从线性提高到亚线性。此外，我们的转换密钥的大小明显更小，例如，从80千兆字节减少到12兆字节。 我们提出了PEGASUS的广泛基准，包括sigmoid/ReLU/min/max/division，排序和最大集合。为了进一步证明PEGASUS的能力，我们又开发了两个应用程序。第一个是私人决策树评估，其通信成本比以前基于HE的方法小两个数量级。第二个是一个安全的K-means聚类，它能够在几分钟内运行在成千上万的加密样本上，比现有的最佳系统要好14×-20倍。据我们所知，这是第一项支持在单服务器环境下使用HE进行实用K-means聚类的工作。

引言：

同态加密（HE）是一种加密系统，能够对加密数据进行同态操作，被认为是保护隐私应用的最重要的构建模块之一。HE的一个潜在应用是安全外包，其中所有的数据来自客户。也就是说，客户使用HE对他/她的数据进行加密，并将密码文本上传到服务器，服务器对加密的数据进行所有的计算。然后，服务器将结果以密码文本的形式返回给客户端，客户端可以解密以获得计算结果。HE的另一个潜在应用是安全的两方计算。与安全外包的区别在于，服务器也持有其私人数据库，而客户向服务器发送加密的查询。许多应用都属于这种设置，例如，私人信息检索和决策树评估算法。

目前的大多数HE方案可以分为逐消息的HE（如BFV、BGV和CKKS）和逐比特的HE（如FHEW和TFHE）。每种类型都有特定的优点和缺点。逐消息的HE支持高效的单指令-多数据（SIMD）风格的同态操作（即加法和乘法），将多个明文打包成一条密码消息。然而，计算非多项式函数，如sigmoid、min/max和除法，在逐消息的HE的密码文本上变得困难。作为一种妥协，现有的逐消息的HE的方法使用低度多项式近似非多项式函数，或简单地避免它们，例如，用平均池化代替最大池化。此外，在K-means聚类等应用中，存在不可避免的非多项式函数（即取最小值和除法），很难通过低度多项式进行近似。

与逐消息的HE相反，逐比特的HE支持以布尔电路形式呈现的任意函数，通过使用其信息空间中的一些代表对明文值的每一位进行加密。然而，逐比特的HE对于加法和乘法电路来说几乎不实用，特别是当布尔电路由成千上万的扇入位和大电路深度组成时。例如，将两个加密的16位整数相乘需要大约半分钟。另外，逐比特的HE的扩展率通常比逐消息的HE大几个数量级，这可能导致更高的通信成本。

当把HE应用于现实世界的应用，如安全的神经网络推断，这个问题甚至更具挑战性。这是因为推理程序要计算许多算术函数的实例，如卷积，以及非多项式函数，如sigmoid和max-pooling。于是，很自然地提出以下问题。

我们能否在加密数据上高效地评估多项式函数和非多项式函数？

不幸的是，实现这一目标的实用方法和框架很少。

贡献：

• 我们的LUT方法接收一个40比特的输入数据，代价是引入了一些近似错误。 这样大的输入域对于许多应用来说是足够的，例如保护隐私的机器学习。我们对这些误差进行了经验和理论分析。

• 我们提出了一种存储高效且快速的重新打包算法。简而言之，我们的重新打包密钥由一个CKKS密码文组成，这比CHIMERA由成千上万的CKKS密码文组成的密钥小得多。

• 我们使用SEAL实现了PEGASUS。与CHIMERA不同的是，我们没有将CKKS输出到环面上。因此，Pegasus可以受益于底层优化的NTT/RNS的效率。https://github.com/Alibaba-Gemini-Lab/OpenPEGASUS。

• 我们提出了广泛的实证结果，包括加密数据的最小/最大、排序、除法、平方根和决策树评估。为了进一步证明Pegasus的潜力，我们还实现了一个可行的应用程序，在几分钟内对成千上万的加密样本运行K-means聚类。据我们所知，我们是第一个在单服务器环境下使用纯HE实现实际安全K-means聚类的人。

前序知识

$R_{n,q}=R_n/q{R}_n\equiv {\mathbb{Z}}_q[X]/\left(X^n+1\right)$

$(b,\mathbf{a})=(m+e-{\mathbf{a}}^T\mathbf{s},\mathbf{a})\in {\text{LWE}}_{\mathbf{s}}^{n,q}(m),m\in Z_q$

$(\hat{b},\hat{a})=(\hat{m}+\hat{e}-\hat{a}\cdot \hat{s},\hat{a})\in {\text{RLWE}}_{\hat{s}}^{n,q}(\hat{m}),\hat{m}\in R_{n,q}$

用一个向量$\mathbf{s}$来表示多项式密钥$\hat{s}$，那么${\text{RLWE}}_{\hat{s}}^{n,q}(\hat{m})$可写为${\text{RLWE}}_{\mathbf{s}}^{n,q}(\hat{m})$

$\mathrm{Ecd}$：$\mathrm{Ecd}(\mathbf{v},\Delta )=\hat{v}\in R_{n,q}$ $(\mathbf{v}\in {\mathbb{R}}^{\ell })$

$\mathrm{Dcd}$：$\mathrm{Dcd}(\hat{v},\Delta ,\ell )=\mathbf{v}\in {\mathbb{R}}^{\ell }$ 将多项式环上的元素逆编码为一个向量。

1. RNS and NTT: A well-known technique to optimize the integer polynomial arithmetic on $R_{n,q}$ is to use a full RNS by taking the modulus $q$ as the product of distinct and machine-word-sized primes, i.e., $q={\prod }_{i\in ⟨L⟩}{q}_i.$ One can achieve up to $L\times$ improvement in polynomial arithmetic according to the ring isomorphism $R_{n,q}\to {\prod }_{i\in ⟨L⟩}{R}_{n,q_i}.$

RNS: Residue Number Systems, NTT: Number Theoretic Transform

核心思路(将RLWE转换为FHEW，执行LUT，再转换回来)

初始有一个RLWE密文$\mathrm{c}\mathrm{t}\in {\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathbf{s}}}^{n,q}(\mathrm{Ecd}(\mathbf{v},\Delta ))$，其中$\mathbf{v}\in {\mathbb{R}}^{\ell }.$ 可以将转化过程分为三步

1. 提取编码向量的元素，得到一组LWE密码文。

$\text{ ct }\to {\mathrm{c}\mathrm{t}}_i\in {\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathbf{s}}}^{\bar{n},q}(\Delta \mathbf{v}[i])\text{ for }i\in ⟨\ell ⟩$

2. 对每个LWE密文进行查找表操作$T(x)$。

${\mathrm{c}\mathrm{t}}_i\to {\mathrm{c}\mathrm{t}}_i^{\prime }\in {\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathbf{s}}}^{\bar{n},q}(\Delta T(\mathbf{v}[i]))\text{ for }i\in ⟨\ell ⟩$

3. 将这些LWE密文重新打包为一个RLWE密文，其中的密文是$T(\mathbf{v})$的编码.

{ c t i ′ } i ∈ ⟨ ℓ ⟩ → c t ′ ′ ∈ RLW ⁡ E s ‾ n ˉ , q ′ ′ ( Ecd ⁡ ( T ( v ) , Δ ) ) \left\{\mathrm{ct}_{i}^{\prime}\right\}_{i \in\langle\ell\rangle} \rightarrow \mathrm{ct}^{\prime \prime} \in \operatorname{RLW} \mathrm{E}_{\overline{\mathrm{s}}}^{\bar{n}, q^{\prime \prime}}(\operatorname{Ecd}(T(\mathrm{v}), \Delta)) {cti′​}i∈⟨ℓ⟩​→ct′′∈RLWEsnˉ,q′′​(Ecd(T(v),Δ))

完整协议

协议大纲

$\mathrm{i}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}:{\mathrm{c}\mathrm{t}}_{in}={\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathbf{s}}}^{\overline{n},Q_l}(\mathrm{E}\mathrm{c}\mathrm{d}(\mathbf{v},\mathrm{\Delta }))(l>1),\text{a look up table }T(x):\mathbb{R}\to \mathbb{R}$

$\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}:{\mathrm{c}\mathrm{t}}_{out}\in {\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathrm{s}}}^{\overline{n},Q_{L^{\prime }}}(\mathrm{E}\mathrm{c}\mathrm{d}(T(\mathbf{v}),\Delta ))$

$Q_l={\prod }_{l\in ⟨i⟩}{q}_l(1\le i\le L)$ ,it requires $l>1$ since S2C itself might consume 1 or 2 ciphertext moduli. The computational costs of the following LUT evaluation and repacking depends on the modulus size of the LWE ciphertexts. To lighten the computation, PEGASUS drops all RLWE moduli but keeps the first one $q_0$ before Step 3.

$\mathrm{R}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{k}:\overline{\mathbf{s}}\to \overline{n},\mathbf{s}\to n,\underline{\mathbf{s}}\to \underline{n},0<\Delta ,{\Delta }_r,{\Delta }_r^{\prime }<q_0$

1: ${\mathrm{c}\mathrm{t}}^{\prime }=\mathrm{S}2\mathrm{C}\left({\mathrm{c}\mathrm{t}}_{\mathrm{i}\mathrm{n}}\right)$

$▹{\mathrm{c}\mathrm{t}}^{\prime }\in {\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathbf{s}}}^{\overline{n},q_0}(\Delta \hat{v}),v_i=\mathbf{v}[i]$

S2C算法将$ct$的slot中的值转为多项式系数(coefficient)上的值

2: 提取多项式系数.for each $i\in ⟨\ell ⟩$. ${\mathrm{c}\mathrm{t}}_i={\mathrm{E}\mathrm{x}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{t}}^i\left({\mathrm{c}\mathrm{t}}^{\prime }\right)$

$▹{\mathrm{c}\mathrm{t}}_i\in {\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathbf{s}}}^{\bar{n},q_0}(\Delta \mathbf{v}[i])$

Extract算法将$c{t}^{\prime }$的每项多项式系数分别提取到一个LWE的密文中

3: for $i\in ⟨\ell ⟩$ do $▹$ parallel

4: ${\dot{\mathrm{c}\mathrm{t}}}_i=\mathrm{P}\mathrm{E}\mathrm{G}\mathrm{A}\mathrm{S}\mathrm{U}\mathrm{S}.\mathrm{K}\mathrm{S}\left({\mathrm{c}\mathrm{t}}_i,{\mathrm{S}\mathrm{w}\mathrm{K}}_{\overline{\mathbf{s}}\to \underline{\mathbf{s}}}\right)$.

​ $▹{\dot{\mathrm{c}\mathrm{t}}}_i\in {\mathrm{L}\mathrm{W}\mathrm{E}}_{\underline{\mathbf{s}}}^{\underline{n},q_0}(\Delta \mathrm{v}[i])$

将维数 $\bar{n}$ 换位更小的 $\underline{n}$ ​，因为后一步的LUT会扩大模数。

5: \quad ${\ddot{ct}}_i=\mathrm{P}\mathrm{E}\mathrm{G}\mathrm{A}\mathrm{S}\mathrm{U}\mathrm{S}.\mathrm{L}\mathrm{U}\mathrm{T}\left({\dot{ct}}_i,EK,T(x)\right)$.

​ $▹{\ddot{\mathrm{c}\mathrm{t}}}_i\in {\mathrm{L}\mathrm{W}\mathrm{E}}_{\mathbf{s}}^{n,q_0}(\Delta T(\mathbf{v}[i]))$

执行查找表(lookup table).

6: $\ddot{{\mathrm{c}\mathrm{t}}_i}=\left(b_i,{\mathbf{a}}_i\right)=\mathrm{P}\mathrm{E}\mathrm{G}\mathrm{A}\mathrm{S}\mathrm{U}\mathrm{S}.\mathrm{K}\mathrm{S}({\ddot{\mathrm{c}\mathrm{t}}}_i,{\mathrm{S}\mathrm{w}\mathrm{K}}_{\mathbf{s}\to \underline{\mathbf{s}}})$.

​ $▹{\ddot{\mathrm{c}\mathrm{t}}}_i\in {\mathrm{LWE}}_{\underline{\mathbf{s}}}^{\underline{n},q_0}(\Delta T(\mathbf{v}[i]))$

将维数$n$ 再次缩减到 $\underline{n} $.

7: end for

8: 令$\mathbf{b}=\left[b_0,\cdots ,b_{\ell -1}\right]$， $\mathbf{A}\in {\mathbb{Z}}_{q_0}^{\ell \times \underline{n}}$ $\mathbf{A}$ 的第$i$行是 $ \mathbf{a}_{i} $

$▹\mathbf{A}\mathbf{s}+\mathbf{b}\mathrm{m}\mathrm{o}\mathrm{d}{q}_0=\mathrm{Ecd}(T(\mathbf{v}),\Delta )$

9: 对RK进行线性变换 $\widetilde{ct}=\mathrm{P}\mathrm{E}\mathrm{G}\mathrm{A}\mathrm{S}\mathrm{U}\mathrm{S}.\mathrm{L}\mathrm{T}\left(\mathrm{R}\mathrm{K},\mathrm{RotK},{\Delta }_r^{\prime },\mathbf{A},\mathbf{b}\right).$

$▹\widetilde{ct}\in {\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathbf{s}}}^{\bar{n},Q_{L-1}}\left(\mathrm{Ecd}\left(\mathbf{A}\mathbf{s}+\mathbf{b},{\Delta }_r^{\prime }\right)\right)$

$\text{ Repacking key }\mathrm{R}\mathrm{K}\in {\mathrm{RLWE}}_{\overline{\mathrm{s}}}^{\bar{n},Q_L}\left(\mathrm{Ecd}\left(\underline{\mathbf{s}},{\Delta }_r\right)\right)$

10: 调用${\mathcal{F}}_{\text{mod }}$ 将 $\widetilde{ct}$中的余数$q_0$消去得到${\mathrm{c}\mathrm{t}}_{\text{out }}$.

${\mathrm{c}\mathrm{t}}_{\mathrm{o}\mathrm{u}\mathrm{t}}\in {\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathbf{s}}}^{\bar{n},Q_{L^{\prime }}}(\mathrm{Ecd}(T(\mathbf{v}),\Delta ))$

S2C & Extract

$\mathrm{S}2\mathrm{C}$相当于同态地运行了一个$\mathrm{D}\mathrm{c}\mathrm{d}$函数。

Given the RLWE ciphertext ct which encrypts $\mathrm{Ecd}(\mathbf{v},\Delta )$, the operation $\mathrm{S}2\mathrm{C}(\mathrm{c}\mathrm{t})$ results in an RLWE ciphertext that encrypts a ring element $\hat{v}$ whose coefficients are $v_i=\Delta \mathbf{v}[i]$ for all possible positions.

${\mathrm{E}\mathrm{x}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{t}}^i$将$\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}$中的系数每一项提取成一个$\mathrm{L}\mathrm{W}\mathrm{E}$密文。

Coefficients Extraction. Given the ciphertext $\mathrm{c}\mathrm{t}={\mathrm{RLWE}}_{\mathbf{s}}^{n,p}(\hat{m})$, and an integer $k\in ⟨n⟩$, the operation Extract ${}^k(\mathrm{c}\mathrm{t})$ results in ${\mathrm{L}\mathrm{W}\mathrm{E}}_{\mathbf{s}}^{n,p}\left(m_k\right)$, i.e., an LWE encryption of the $k$ -th coefficient of $\hat{m}$ under the same secret key.

PEGASUS uses the combination of S2C and Extract to convert an RLWE ciphertext of an encoded vector to a set of LWE ciphertexts of the vector elements.

PEGASUS 中 S2C算法来自 K. Han, M. Hhan, and J. H. Cheon, “Improved homomorphic discrete fourier transforms and FHE bootstrapping,” IEEE Access, vol. 7, pp. 57 361–57 370, 2019.

Extract算法我在文章中没有找到出处。

KeySwitching

概述

KeySwitching方法将一个由$\overline{\mathbf{s}}$加密的LWE密文转换为由$\underline{\mathbf{s}}$加密的LWE密文。需要一个转换密钥。目的是为了减少维数更大的向量在运算中带来的更大的噪声。

算法

正确性

LookUp Table

概述

在PEGASUS的LUT方法中，他们采用的技术是将每个LUT计算结果$T(i)$作为一个多项式中第$i$项的系数，通过一个算法将第$m$项的次数变为0，然后通过提取多项式中次数为0的项来得到$T(m)$。

例子

算法

lookup table算法的最终要达到的效果是得一个密文是执行了$T(m)$的LWE密文，

正确性：

正确性一：如果最后得到的${\mathrm{A}\mathrm{C}}_{\underline{n}}\in {\mathrm{RLWE}}_{\mathrm{s}}\left(\hat{f}\cdot X^{\tilde{b}+{\tilde{\mathbf{a}}}^{\top }\underline{\mathbf{s}}\mathrm{m}\mathrm{o}\mathrm{d}n}\right)$，则输出为${\mathrm{L}\mathrm{W}\mathrm{E}}_{\mathbf{s}}^{n,q}(\lceil \Delta T(m)\rfloor +e)$

$\tilde{b}+{\tilde{\mathbf{a}}}^{\top }\underline{\mathbf{s}}\mathrm{m}\mathrm{o}\mathrm{d}n\approx \frac{2n}{q}\lceil \Delta m\rfloor +2ϵn$ , let $\delta =\tilde{b}+{\tilde{\mathbf{a}}}^{\top }\underline{\mathbf{s}},$

Then the 0 -th coefficient of $\hat{f}\cdot X^{\hat{b}+{\tilde{\mathbf{a}}}^{\top }\underline{\mathbf{s}}}\mathrm{m}\mathrm{o}\mathrm{d}n$ is
$$\{\begin{array}{l}{f}_{|\delta |}{X}^{|\delta |}\cdot -X^{n-|\delta |}=\lceil \Delta T\left(-{\eta }_{|\delta |}\right)\rfloor \text{ for }\delta \le 0\\ -f_{n-\delta }{X}^{n-\delta }\cdot X^{\delta }=\lceil \Delta T\left({\eta }_{\delta }\right)\rfloor \text{ for }\delta >0\end{array}$$
By definition
$${\eta }_{\delta }=\frac{\lceil \frac{2n}{q_0}\lceil \Delta m\rfloor \rfloor q_0}{2n\Delta }\approx m$$

**正确性二：**最后得到的${\mathrm{A}\mathrm{C}}_{\underline{n}}$确实满足上述的格式。

$\underline{\mathbf{s}}[j]=1$时，${\mathrm{E}\mathrm{K}}_{j,0}\in {\mathrm{RGSW}}_{\mathrm{s}}^{n,q}\left(1)\right),{\mathrm{E}\mathrm{K}}_{j,1}\in {\mathrm{RGSW}}_{\mathrm{s}}^{n,q}\left(0\right)$

$\underline{\mathbf{s}}[j]=0$时，${\mathrm{E}\mathrm{K}}_{j,0}\in {\mathrm{RGSW}}_{\mathrm{s}}^{n,q}\left(1)\right),{\mathrm{E}\mathrm{K}}_{j,1}\in {\mathrm{RGSW}}_{\mathrm{s}}^{n,q}\left(1\right)$

$\underline{\mathbf{s}}[j]=-1$时，${\mathrm{E}\mathrm{K}}_{j,0}\in {\mathrm{RGSW}}_{\mathrm{s}}^{n,q}\left(0)\right),{\mathrm{E}\mathrm{K}}_{j,1}\in {\mathrm{RGSW}}_{\mathrm{s}}^{n,q}\left(1\right)$

1. Suppose $\underline{\mathbf{s}}[j]=0$ then $\tilde{\mathbf{a}}[j]\underline{\mathbf{s}}[j]=0$. We note that ${\mathrm{E}\mathrm{K}}_{j,0}$ and ${\mathrm{E}\mathrm{K}}_{j,1}$ are both GSW encryption of 1 in this case.
   $$\begin{array}{rl}{\mathrm{A}\mathrm{C}}_{j+1}& =\left(\left(X^{-\tilde{\mathbf{a}}[j]}-1\right)\cdot {\mathrm{t}}_j\right)\odot {\mathrm{RGSW}}_{\underline{\underline{s}}}(1)+{\mathrm{t}}_j\\ & =X^{-\tilde{\mathbf{a}}[j]}\cdot {\mathrm{t}}_j=X^{-\tilde{\mathbf{a}}[j]}\cdot X^{\tilde{\mathbf{a}}[j]}\cdot {\mathrm{A}\mathrm{C}}_j={\mathrm{A}\mathrm{C}}_j\end{array}$$
2. Suppose $\underline{\mathbf{s}}[j]=1$ then $\tilde{\mathbf{a}}[j]\underline{\mathbf{s}}[j]=\tilde{\mathbf{a}}[j].$ We note that ${\mathrm{E}\mathrm{K}}_{j,0}$ is a GSW encryption of 1 and ${\mathrm{E}\mathrm{K}}_{j,1}$ is a GSW encryption of 0 in this case.
   $$\begin{array}{rl}{\mathrm{A}\mathrm{C}}_{j+1}& =\left(\left(X^{-\tilde{\mathbf{a}}[j]}-1\right)\cdot {\mathrm{t}}_j\right)\odot {\mathrm{RGSW}}_{\underline{\underline{s}}}(0)+{\mathrm{t}}_j\\ & ={\mathrm{t}}_j=X^{\tilde{\mathbf{a}}[j]}\cdot {\mathrm{A}\mathrm{C}}_j\end{array}$$
3. Suppose $\underline{\mathbf{s}}[j]=-1$ then $\tilde{\mathbf{a}}[j]\underline{\mathbf{s}}[j]=-\tilde{\mathbf{a}}[j].$ We note that ${\mathrm{E}\mathrm{K}}_{j,0}$ is GSW encryption of 0 and ${\mathrm{E}\mathrm{K}}_{j,1}$ is a GSW encryption of 1 in this case.
   $$\begin{array}{rl}{\mathrm{A}\mathrm{C}}_{j+1}& =\left(\left(X^{-\tilde{\mathbf{a}}[j]}-1\right)\cdot {\mathrm{t}}_j\right)\odot {\mathrm{RGSW}}_{\underline{\mathbf{s}}}(1)+{\mathrm{t}}_j\\ & =X^{-\tilde{\mathbf{a}}[j]}\cdot {\mathrm{t}}_j=X^{-\tilde{\mathbf{a}}[j]}\cdot {\mathrm{A}\mathrm{C}}_j\end{array}$$
   then，we have ${\mathrm{A}\mathrm{C}}_j\in {\mathrm{RLWE}}_{\mathbf{s}}\left(\hat{f}\cdot X^{\tilde{b}+{\sum }_{l\in ⟨j⟩}\tilde{\mathbf{a}}[j]\underline{\mathbf{s}}[j]}\mathrm{m}\mathrm{o}\mathrm{d}n\right)$, which means ${\mathrm{A}\mathrm{C}}_{\underline{n}}\in {\mathrm{RLWE}}_{\mathrm{s}}\left(\hat{f}\cdot X^{\tilde{b}+{\tilde{\mathbf{a}}}^{\top }\underline{\mathbf{s}}\mathrm{m}\mathrm{o}\mathrm{d}n}\right)$

Linear Transform

概述

线性变换是将输入的${\mathrm{c}\mathrm{t}}_{\mathrm{i}\mathrm{n}}\in {\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathrm{s}}}^{\bar{n},q}\left(\mathrm{Ecd}\left(\mathbf{z},{\Delta }_r\right)\right)$以及明文矩阵$\mathbf{M}$，明文向量$\mathbf{t}$，得到${\mathrm{c}\mathrm{t}}_{\mathrm{o}\mathrm{u}\mathrm{t}}\in {\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathrm{s}}}^{\bar{n},q/{\Delta }_r}\left(\mathrm{Ecd}\left(\mathbf{M}\mathbf{z}+\mathbf{t},{\Delta }_r\right)\right)$

看到总体的框架中，由于LUT执行的结果是$i\in\langle l \rangle, (b_i,\mathbf{a}i)=\mathrm{LWE}{\mathbf{s}}^{n,q}(\lceil\Delta T(m_i)\rfloor +e) $，其中$\Delta T(m_i)+e = \mathbf{a}_i \mathbf{s}+b_i \bmod q$

对于对于由${\mathbf{a}}_i$构成所有行的矩阵$\mathbf{A}$，由$b_i$构成每一个元素的向量$\mathbf{b}$，$\mathbf{A}\mathbf{s}+\mathbf{b}\mathrm{m}\mathrm{o}\mathrm{d}q=\Delta T(m)$。

所以在拥有一个${\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathrm{s}}}^{\bar{n},q}\left(\mathrm{Ecd}\left(\mathbf{s},{\Delta }_r\right)\right)$时，可以通过线性变换计算得到${\mathrm{c}\mathrm{t}}_{\mathrm{o}\mathrm{u}\mathrm{t}}\in {\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathrm{s}}}^{\bar{n},q/{\Delta }_r}\left(\mathrm{Ecd}\left(\mathbf{A}\mathbf{s}+\mathbf{b},{\Delta }_r\right)\right)$

例子

算法

正确性

先来看例子中的情况，当$\ell >\underline{n}$时，特别地，当$\ell =4,\underline{n}=2$时。

1. Tiling and Diagonals.

   $\ddot{n}=4,\tilde{n}=2$，有两个向量${\tilde{\mathbf{m}}}_0,{\tilde{\mathbf{m}}}_1$.

   ${\tilde{\mathbf{m}}}_0[0]=M[0,0],{\tilde{\mathbf{m}}}_0[1]=M[1,1],{\tilde{\mathbf{m}}}_0[2]=M[2,0],{\tilde{\mathbf{m}}}_0[3]=M[3,1],{\tilde{\mathbf{m}}}_0[4]=M[4,0]$.

   ${\tilde{\mathbf{m}}}_1[0]=M[0,1],{\tilde{\mathbf{m}}}_1[1]=M[1,0],{\tilde{\mathbf{m}}}_1[2]=M[2,1],{\tilde{\mathbf{m}}}_1[3]=M[3,0],{\tilde{\mathbf{m}}}_1[4]=M[4,1]$.

2. Baby-Step.

   $\tilde{g}=2,c_0={\mathrm{R}\mathrm{o}\mathrm{t}\mathrm{L}}^0({\mathrm{c}\mathrm{t}}_{\mathrm{i}\mathrm{n}}),c_1={\mathrm{R}\mathrm{o}\mathrm{t}\mathrm{L}}^1({\mathrm{c}\mathrm{t}}_{\mathrm{i}\mathrm{n}})$.

   ${\mathrm{c}}_0\in {\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathbf{s}}}^{\bar{n},q}\left(\mathrm{Ecd}\left(z[0],z[1],{\Delta }_r\right)\right),{\mathrm{c}}_1\in {\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathbf{s}}}^{\bar{n},q}\left(\mathrm{Ecd}\left(z[1],z[0],{\Delta }_r\right)\right)$

3. Giant-Step.

   $\tilde{b}=1,\widetilde{\mathrm{c}\mathrm{t}}={\mathrm{R}\mathrm{o}\mathrm{t}\mathrm{L}}^0(\mathrm{E}\mathrm{c}\mathrm{d}({\tilde{\mathbf{m}}}_0)\cdot c_0+\mathrm{E}\mathrm{c}\mathrm{d}({\tilde{\mathbf{m}}}_1)\cdot c_1)$

   $\widetilde{\mathrm{c}\mathrm{t}}={\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}}_{\overline{\mathbf{s}}}(\mathrm{E}\mathrm{c}\mathrm{d}(\mathbf{M}\mathbf{z}),{\Delta }_r)$.

文章里的证明：

${\mathcal{F}}_{mod}$

PEGASUS中${\mathcal{F}}_{mod}$算法来自K. Han and D. Ki, “Better bootstrapping for approximate homomorphic encryption,” in Topics in Cryptology - CT-RSA 2020 - The Cryptographers’ Track at the RSA Conference 2020, San Francisco, USA, February 24-28, 2020, Proceedings, pp. 364–390.