该系列第一篇将介绍Brakerski/Fan-Vercauteren方案（BFV）^{Bra12 FV12}，一个基于Ring-Learning with Errors（RLWE）的密码系统。随后会继续学习Brakerski-Gentry-Vaikuntanathan（BGV）方案^BGV14和Cheon-Kim-Kim-Song（CKKS）方案^CKKS17。

接下来是BFV全同态加密算法的一个简单介绍，它是第二代全同态加密算法^LPR13。本文主要是对Introduction to the BFV encryption scheme的翻译和个人总结。

 

BFV Primitives

以下参数定义来自同态加密定义标准^ACC+18

• $\textsf{ParamGen}(\lambda) \to \textsf{Params}$

  参数生成器，其中$\lambda$代表安全强度，以概率1成功攻击该算法的穷举复杂度为$2^\lambda$，[ACC+18]中可选取值为80，128，256，目前80已经弃用。

• $\textsf{KeyGen}(\textsf{Params}) \to {\textsf{SK}, \textsf{PK}, \textsf{EK}}$

  密钥生成（KeyGen）将加密参数作为输入，并返回一组密钥。1）秘密密钥（SK），主要用于解密（也可用于对称加密，即SK用于加密和解密）；2）公开密钥（PK），用于加密；3）评估密钥（EK），用于评估密码文的同态操作，我们将在后面看到。SK应该由用户（敏感数据所有者）保密，但PK和EK可以公开共享而不影响方案的安全性。

• $\textsf{Encrypt}(\textsf{PK}, \textsf{M}) \to \textsf{C}$

  加密将明文空间$P$中的明文信息M和PK作为输入，并从密文空间$C$中返回一个有效的密文C。

• $\textsf{Decrypt}(\textsf{SK}, \textsf{C}) \to \textsf{M}$

  将SK和$C$中密文C作为输入，解密得到$P$中的信息M。

• $\textsf{EvalAdd}(\textsf{Params}, \textsf{EK}, \textsf{C}^{(1)}, \textsf{C}^{(2)}) \to \textsf{C}^{(3)}$

  同态加法，通过加密参数和评估密钥，对加密了$\textsf{M}^{(1)}$的密文$\textsf{C}^{(1)}$和对加密了$\textsf{M}^{(2)}$的密文$\textsf{C}^{(2)}$进行同态加得到密文$\textsf{C}^{(3)}$，其对应的明文为$\textsf{M}^{(1)} + \textsf{M}^{(2)}$。

• $\textsf{EvalAddConst}(\textsf{Params}, \textsf{EK}, \textsf{C}^{(1)}, \textsf{M}^{(2)}) \to \textsf{C}^{(3)}$

  类似$\textsf{EvalAdd}$，此时其中一个输入为明文。对加密了$\textsf{M}^{(1)}$的密文$\textsf{C}^{(1)}$和明文$\textsf{M}^{(2)}$同态加得到密文$\textsf{C}^{(3)}$，其对应的明文为$\textsf{M}^{(1)} + \textsf{M}^{(2)}$。

• $\textsf{EvalMult}(\textsf{Params}, \textsf{EK}, \textsf{C}^{(1)}, \textsf{C}^{(2)}) \to \textsf{C}^{(3)}$

  同态乘法，通过加密参数和评估密钥，对加密了$\textsf{M}^{(1)}$的密文$\textsf{C}^{(1)}$和对加密了$\textsf{M}^{(2)}$的密文$\textsf{C}^{(2)}$进行同态乘得到密文$\textsf{C}^{(3)}$，其对应的明文为$\textsf{M}^{(1)} \times \textsf{M}^{(2)}$。

• $\textsf{EvalMultConst}(\textsf{Params}, \textsf{EK}, \textsf{C}^{(1)}, \textsf{M}^{(2)}) \to \textsf{C}^{(3)}$

  类似$\textsf{EvalMult}$，此时其中一个输入为明文。对加密了$\textsf{M}^{(1)}$的密文$\textsf{C}^{(1)}$和明文$\textsf{M}^{(2)}$同态乘得到密文$\textsf{C}^{(3)}$，其对应的明文为$\textsf{M}^{(1)} \times \textsf{M}^{(2)}$。

• $\textsf{Relinearize}(\textsf{Params}, \textsf{EK}, \textsf{C}’) \to \textsf{C}$

  重线性化，将高维(ill-shaped)的密文重新变成低维度(well-shaped)的密文。

 

明文密文空间

模多项式环的次数、明文系数、密文系数：$n,t,q \in Z$，$R_a$中的系数取自$\{\left \lceil{-\frac{a}{2}}\right \rceil, \ldots , \left \lfloor{\frac{a-1}{2}}\right \rfloor\}$

• 明文空间：$P = R_t = Z_t[x]/(x^n+1)$
• 密文空间：$C = R_q \times R_q$，其中$R_q = Z_q[x]/(x^n+1)$

通常来说：$n$是2的次幂，q比t大很多，因此密文空间比明文空间大得多。$R_q,R_t$的阶（群中元素的个数）为：$q^n,t^n$。

$$\begin{array} {rr}\hline \textsf{M}^{(0)} & 1 + 2x + 1x^2 -1x^3\\ \hline \textsf{M}^{(1)} & -1 - 2x -1 x^2 +2x^3\\ \hline \textsf{M}^{(2)} & 1 + 1x + 1x^2 +1x^3\\ \hline \end{array}$$ Table 1: Examples of valid plaintext messages for (n,t) = (4, 5)

 

随机分布参数

BFV用到的随机分布：

• $R_2$：密钥的采样分布，对整数系数为{-1,0,1}的多项式进行采样（系数是对模3环上的均匀采样：$Z_3$）。
• $\mathcal{X}$：随机错误分布，定义为R上参数为μ和σ的离散高斯分布，以某个整数β为界。 根据当前版本的同态加密标准^ACC+18，$(\mu, \sigma, \beta)$ 被设定为$(0, \frac{8}{\sqrt{2\pi}}\approx 3.2, \lfloor 6\cdot \sigma \rceil = 19)$。
• $R_q$：$R_q$上的均匀随机分布。

我们注意到，参数(t,q,n)的选择是针对具体应用的，也是由所需的安全级别驱动的。关于一组可接受的参数，参考同态加密标准^ACC+18中的表1和表2。作为一个经验法则，只要感兴趣的目标应用仍然可以在FHE中实现，就应该选择最小化这些参数。

 

明文编解码

介绍简单的$p$进制编码方案，我们要将明文$m$编码至$R_t$。

1. 将明文表示为2进制： $m = a_{n-1}\cdots a_2 a_1 a_0$
2. $\textsf{M} = a_{n-1}x+\cdots+a_{2}x^2+a_{1}x+a_0$，n通常很大，没用的比特置为0。

由于明文系数的幅度较小，同态评估期间的系数增长通常较慢。请注意，使用这种编码的同态评估可能会导致明文多项式的次数增长。为了确保同态评估的结果与目标计算的预期结果相吻合，我们需要确保明文多项式的次数不超过n，系数不大于t （即最多t进制编码）。

 

密钥生成

私钥$\textsf{SK}$是 random ternary polynomial ，也就是系数取自$R_2 = {-1，0，1}$ 的多项式

公钥$\textsf{PK}$是$R_q$上的多项式，由一对多项式构成：$(\textsf{PK}_1, \textsf{PK}_2)$，定义如下

$$\begin{align} \textsf{PK}_1 &= [-1(a\cdot \textsf{SK}+e)]_q\\ \textsf{PK}_2 &= a \nonumber \end{align} \tag{1}$$

其中$a$是采样自$R_q$上的随机多项式，$e$是采样自$\mathcal{X}$的随机多项式。符号$[\cdot]_q$表示多项式的系数运算以q为模数进行。总之，$a$定义$R_q$上，所有运算都定义在$Z_q$上面模$(x^n+1)$的多项式环。

 

加解密

• 加密：明文$\textsf{M}$，产生三个小的随机多项式，$u \in R_2, e_1,e_2 \in \mathcal{X}$，加密结果$\textsf{C} = (\textsf{C}_1,\textsf{C}_2)$，其中缩放系数$\Delta = \lfloor \frac{q}{t} \rfloor$，用于将明文$M$从$Z_t$扩展到密文的模空间$Z_q$上：

  $$\begin{align} \textsf{C}_1 &= [\textsf{PK}_1\cdot u + e_1 + \Delta \textsf{M}]_q\\ \textsf{C}_2 &= [\textsf{PK}_2\cdot u + e_2]_q \nonumber \end{align} \tag{2}$$

• 解密：解密过程如下，最后并将加密时应用的缩放系数倒置：

  $$\begin{equation} \textsf{M} = \bigg[ \bigg\lfloor \dfrac{t[\textsf{C}_1+\textsf{C}_2\cdot \textsf{SK}]_q}{q} \bigg\rceil \bigg]_t \end{equation} \tag{3}$$

• 解密过程验证：

  $$\begin{align} \textsf{C}_1+\textsf{C}_2\cdot\textsf{SK} &= \textsf{PK}_1\cdot u + e_1 + \Delta \textsf{M} + (\textsf{PK}_2\cdot u + e_2)\cdot \textsf{SK}\\ &= -(a\cdot \textsf{SK}+e)\cdot u+e_1+\Delta \textsf{M} + a\cdot u \cdot \textsf{SK} + e_2\cdot \textsf{SK} \nonumber\\ &= {-a\cdot u \cdot \textsf{SK}} - e\cdot u+e_1+\Delta \textsf{M} + {a\cdot u \cdot \textsf{SK}} + e_2\cdot \textsf{SK} \nonumber\\ &= \Delta \textsf{M} - e\cdot u + e_1 + e_2\cdot\textsf{SK} \nonumber\\ &= \Delta \textsf{M} + v \nonumber \end{align} v \tag{4}$$

  注意到最后的误差多项式$v$的无穷范数，即多项式中的绝对值最大的系数，记为$\left| v \right|$，是很小的。因为$e, e_1, e_2,u,\textsf{SK}$都是小系数的多项式。更具体地说，考虑到这些小的多项式是由参数$\beta$约束的，可以得到该范数的一个上界：$\left| v \right| \leq n \beta^2 + \beta + n \beta^2 = 2n \beta^2 + \beta$。

  我们带入解密过程中的模q，将$(4)$展开看：

  $$\begin{align} [\textsf{C}_1+\textsf{C}_2\cdot\textsf{SK}]_q &= \Delta \textsf{M} + v + q\cdot r \end{align} \tag{5}$$

  其中$r$是一个小的多项式，再对$(5)$乘以修正系数$\frac{t}{q}$，得到：

  $$\frac{t}{q}[\textsf{C}_1+\textsf{C}_2\cdot\textsf{SK}]_q =\textsf{M} +\frac{t}{q}\cdot v+t\cdot r \tag{6}$$

  因此，解密中的四舍五入（rounding）取整可以去除$\frac{t}{q}\cdot v$，最后模t运算去除$t\cdot r$并恢复得到$\textsf{M}$。要保证解密成功，必须保证：$\frac{t}{q}\cdot \left| v \right| < \frac{1}{2}$。

 

同态性质

在这一节中，我们将解释同态过程是如何工作的。本节的大部分内容是基于BFV ^FV12的论文中的正确性分析。

 

$\textsf{EvalAdd}$

同态加，我们只需要将对应的多项式相加即可。

$$\begin{equation} \textsf{EvalAdd}(\textsf{C}^{(1)}, \textsf{C}^{(2)}) = ([\textsf{C}^{(1)}_1 + \textsf{C}^{(2)}_1]_q, [\textsf{C}^{(1)}_2 + \textsf{C}^{(2)}_2]_q) = ( \textsf{C}^{(3)}_1, \textsf{C}^{(3)}_2) = \textsf{C}^{(3)} \end{equation} \tag{7}$$

为了说明上述同态性质，我们可以把等式写开，假设$\textsf{C}^{(1)}$和$\textsf{C}^{(1)}$是$\textsf{M}^{(1)}$和$\textsf{M}^{(2)}$的纯净加密（2维）：

$$\begin{align} \textsf{C}^{(1)} &= ([\textsf{PK}_1\cdot u^{(1)} + e_1^{(1)} + \Delta \textsf{M}^{(1)}]_q, [\textsf{PK}_2 \cdot u^{(1)} + e_2^{(1)}]_q)\\ \textsf{C}^{(2)} &= ([\textsf{PK}_1\cdot u^{(2)} + e_1^{(2)} + \Delta \textsf{M}^{(2)}]_q, [\textsf{PK}_2 \cdot u^{(2)} + e_2^{(2)}]_q) \nonumber \end{align} \tag{8}$$

将$(8)$带入到$(7)$中可得到：

$$\begin{align} \textsf{C}^{(3)} ={}& ( \textsf{C}^{(3)}_1, \textsf{C}^{(3)}_2)\\ ={}& ( [\textsf{PK}_1\cdot(u^{(1)}+u^{(2)})+(e_1^{(1)}+e_1^{(2)})+ \Delta(\textsf{M}^{(1)}+\textsf{M}^{(2)})]_q, \nonumber \\ {}&~[\textsf{PK}_2\cdot(u^{(1)}+u^{(2)})+(e_2^{(1)}+e_2^{(2)})]_q ) \nonumber \\ ={}& ( [\textsf{PK}_1\cdot u^{(3)}+e_1^{(3)}+ \Delta(\textsf{M}^{(1)}+\textsf{M}^{(2)})]_q, [\textsf{PK}_2 \cdot u^{(3)}+e_2^{(3)}]_q ) \end{align} \tag{9}$$

上述式子也就是明文相加后得到的一个标准密文$\textsf{M}^{(3)} = \textsf{M}^{(1)} + \textsf{M}^{(2)}$。注意到这里随机误差相加，最坏情况是误差都增长一倍（概率很小），但是一般来说，这两个误差不会累加增大。

同样的，$\textsf{EvalAddPlain}$只需要用公钥加密一个明文进行操作即可，此时可以选择0误差$e_1=e_2=0$。（因为这是云端在同态计算时嵌入的消息，可以尽量减少误差的累计）

 

$\textsf{EvalMult}$

同态乘，同态乘过程很复杂。首先类似解密过程中的推导，我们把$C^{(1)}$写成用$\textsf{SK}$评估后明文加误差的形式：

$$\begin{align} \textsf{C}^{(1)}(\textsf{SK}) &= \Delta \textsf{M}^{(1)}+v_1+q \cdot r_1\\ \textsf{C}^{(2)}(\textsf{SK}) &= \Delta \textsf{M}^{(2)}+v_2+q \cdot r_2 \nonumber \end{align} \tag{10}$$

此时如果我们对上面中间过程的密文进行乘法得到：

$$\begin{equation} \begin{split} (\textsf{C}^{(1)} \cdot \textsf{C}^{(2)})(\textsf{SK}) = &\Delta^2 \textsf{M}^{(1)}\cdot \textsf{M}^{(2)} + \Delta(\textsf{M}^{(1)}\cdot v_2+\textsf{M}^{(2)}\cdot v_1)+\\ &q(v_1\cdot r_2 + v_2\cdot r_1) + q\cdot \Delta(\textsf{M}^{(1)}\cdot r_2 + \textsf{M}^{(2)} \cdot r_1)+\\ &v_1 \cdot v_2 + q^2 \cdot r_1 \cdot r_2 \end{split} \end{equation} \tag{11}$$

可以看到上述乘积有些类似我们想要得到的项：$\Delta \cdot[\textsf{M}^{(1)} \cdot \textsf{M}^{(2)}]_t$，通过对$(11)$同时乘以$\frac{1}{\Delta}$，那么第一项就是我们想要得到的项，后面跟着一些随机误差。但是最后一项$q^2 \cdot r_1 \cdot r_2$会产生很大的噪声，因为$q^2$并不整除$\Delta$。因此我们在两边同乘以$\frac{t}{q}$，我们重新表示$\textsf{M}^{(1)}\cdot \textsf{M}^{(2)} = [\textsf{M}^{(1)}\cdot \textsf{M}^{(2)}]_t + t\cdot r_M$，以及$v_1\cdot v_2 = [v_1 \cdot v_2]_{\Delta} + \Delta \cdot r_v$，带入$(11)$并且同乘以$\frac{t}{q}$

$$\begin{equation} \begin{split} \frac{t}{q}(\textsf{C}^{(1)} \cdot \textsf{C}^{(2)})(\textsf{SK}) = &\Delta [\textsf{M}^{(1)}\cdot \textsf{M}^{(2)}]_t+(\textsf{M}^{(1)}\cdot v_2+\textsf{M}^{(2)}\cdot v_1)+\\ &t(v_1\cdot r_2 + v_2\cdot r_1) + r_v + (q-[q]_t)\cdot(r_M+\textsf{M}^{(1)}\cdot r_2+\textsf{M}^{(2)}\cdot r_1)+\\ &q\cdot t\cdot r_1 \cdot r_2 +\frac{t}{q}[v_1\cdot v_2]_\Delta -\\ &\frac{[q]_t}{q} ( \Delta \textsf{M}^{(1)} \cdot \textsf{M}^{(2)} + \textsf{M}^{(1)} \cdot v_2 + \textsf{M}^{(2)} \cdot v_1 + r_v ) \end{split} \end{equation} \tag{12}$$

最后一步就是对式子$(12)$模q，得到：

$$\begin{equation} \begin{split} \frac{t}{q}(\textsf{C}^{(1)} \cdot \textsf{C}^{(2)})(\textsf{SK}) = &\Delta [\textsf{M}^{(1)}\cdot \textsf{M}^{(2)}]_t+(\textsf{M}^{(1)}\cdot v_2+\textsf{M}^{(2)}\cdot v_1)+\\ &t(v_1\cdot r_2 + v_2\cdot r_1) + r_v -\\ &[q]_t (r_M+\textsf{M}^{(1)}\cdot r_2+\textsf{M}^{(2)}\cdot r_1) + r_e \end{split} \end{equation}$$

其中$r_e$是$(12)$中的最后两项。其中误差的增长是一个线性因子，大约为$2\cdot t \cdot n^2 \cdot \left\| SK \right\|$，同态乘法之后得到的误差增长为： $\left\| v_{p} \right\| = \left\| v_i \right\| \cdot 2\cdot t \cdot n^2 \cdot \left\| SK \right\|$，其中$v_p$是输出的噪声，$v_i$是输入噪声。

由于上述解密过程用的是$\textsf{C}^{(1)} \cdot \textsf{C}^{(2)})(\textsf{SK})$，也就是我们要计算 $( \textsf{C}_1^{(1)}+\textsf{C}_2^{(1)}\cdot\textsf{SK}) \cdot ( \textsf{C}_1^{(2)}+\textsf{C}_2^{(2)}\cdot\textsf{SK})$，因此如果想要用$\textsf{SK}$进行解密，我们需要保留三项中间结果，即密文维度扩展了一维。并且解密算法也需要相应发生改变。总的同态乘法计算如下：

$$\begin{equation} \begin{split} \textsf{EvalMult}(\textsf{C}^{(1)}, \textsf{C}^{(2)}) = \bigg(& \bigg[ \bigg\lfloor \dfrac{t(\textsf{C}^{(1)}_1\cdot\textsf{C}^{(2)}_1)}{q} \bigg\rceil \bigg]_q, \bigg[ \bigg\lfloor \dfrac{t(\textsf{C}^{(1)}_1 \cdot \textsf{C}^{(2)}_2 + \textsf{C}^{(1)}_2 \cdot \textsf{C}^{(2)}_1 )}{q} \bigg\rceil \bigg]_q, \\& \bigg[ \bigg\lfloor \dfrac{t(\textsf{C}^{(1)}_2 \cdot \textsf{C}^{(2)}_2)}{q} \bigg\rceil \bigg]_q \bigg) \end{split} \end{equation} \tag{13}$$

由此导致了一个严重的问题，同态乘法进行多次后会使得计算复杂度、密文冗余快速增大，也就是有限次数的同态加密。为了做到全同态加密，BFV方案给出了一个安全并且有效的解决方案：利用额外的评估密钥$\textsf{EK}$进行Relinearization，既可以降维度，又可以减少误差的累积，从而达到全同态加密的效果。

 

线性重构（Relinearization）

这是BFV全同态加密的一个重要部分。这个部分的主要目的是将同态乘积得到的3维密文空间，即从$\textsf{EvalMult}$产生的那些密文，减少到2维。该维度规约问题可以形式化地描述如下：$\textsf{C}^{*} = \{\textsf{C}^{*}_1, \textsf{C}^{*}_2, \textsf{C}^{*}_3\}$，我们需要找到$\hat{\textsf{C}}^{*} = \{\hat{\textsf{C}}^{*}_1, \hat{\textsf{C}}^{*}_2\}$使得：

$$\begin{equation} [\textsf{C}^{*}_1 + \textsf{C}^{*}_2\cdot \textsf{SK} + \textsf{C}^{*}_3 \cdot \textsf{SK}^2]_q \approx [\hat{\textsf{C}}^{*}_1 + \hat{\textsf{C}}^{*}_2 \cdot \textsf{SK} + r]_q \end{equation} \tag{14}$$

线性重构，也就是为了消去$(14)$中二次项的影响，因此我们需要一定的$\textsf{SK}^2$私钥的信息，这个信息也同样通过LWE保护起来，从而保证私钥的安全性。具体形式是额外给出评估密钥$\textsf{EK} = (\textsf{EK}_1 , \textsf{EK}_2) = (-(a\cdot \textsf{SK} + e) + \textsf{SK}^2, a)$，这就是一个私钥平方$\textsf{SK}^2$加入掩码进行保护，注意到$\textsf{EK}_1 + \textsf{EK}_2 \cdot \textsf{SK} = \textsf{SK}^2 - e$，因此我们可以通过如下方法得到$\hat{\textsf{C}^{*}}$：

$$\begin{align}\label{eq:relin} \hat{\textsf{C}}^{*}_1 &= [\textsf{C}^*_1 + \textsf{EK}_1\cdot \textsf{C}^*_3]_q\\ \hat{\textsf{C}}^{*}_2 &= [\textsf{C}^*_2 + \textsf{EK}_2\cdot \textsf{C}^*_3]_q \nonumber \end{align} \tag{15}$$

如果我们对$(14)$引用解密公式，就可以得到：

$$\begin{align} \hat{\textsf{C}}^{*}_1 + \hat{\textsf{C}}^{*}_2 \cdot \textsf{SK} &= \textsf{C}^*_1 + \textsf{EK}_1\cdot \textsf{C}^*_3 + \textsf{SK}\cdot (\textsf{C}^*_2 + \textsf{EK}_2\cdot \textsf{C}^*_3)\\ &= \textsf{C}^*_1 + \textsf{C}^*_2 \cdot \textsf{SK} + \textsf{C}^*_3\cdot(\textsf{EK}_1 + \textsf{EK2} \cdot \textsf{SK} )\nonumber\\ &= \textsf{C}^*_1 + \textsf{C}^*_2 \cdot \textsf{SK} + \textsf{C}^*_3 \cdot \textsf{SK}^2 + \textsf{C}^*_3 \cdot e \nonumber \end{align} \tag{16}$$

因此，这就是我们之前得到的同态乘法对应的正确解密结果加一个误差值，值得注意的是，最后一个误差项$\textsf{C}^*_3 \cdot e$可能很大，因为$\textsf{C}^*_3$的系数定义在$Z_q$上，更多技术细节参考论文^FV12。

 

安全性分析

分析BFV方案的安全性是相当复杂的，超出了本文的范围。选择最佳的BFV参数，使性能最大化，并尊重安全和功能限制，是一门艺术，由专家密码学家来实践。对于BFV（和其他FHE方案）的简要安全分析和一组推荐参数，读者可以参考同态加密标准^ACC+18。

 

参考文献

^ACC+18. Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Toronto, Canada, November 2018. ↩

^Bra12. Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical gapsvp. In Annual Cryptology Conference, pages 868–886. Springer, 2012. ↩

^BGV14. Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical gapsvp. In Annual Cryptology Conference, pages 868–886. Springer, 2012. ↩

^CKKS17. Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security, pages 409–437. Springer, 2017. ↩

^FV12. Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. 2012. https://eprint.iacr.org/2012/144. ↩

^LPR13. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. Journal of the ACM (JACM), 60(6):1–35, 2013 ↩