Linear Decryption: Rate-1 FHE TLP

参考文献：

1. [ILL89] Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-random generation from oneway functions (extended abstracts). In 21st Annual ACM Symposium on Theory of Computing, pages 12–24, Seattle, WA, USA, May 15–17, 1989. ACM Press.

2. [RSW96] Rivest R L, Shamir A, Wagner D A. Time-lock puzzles and timed-release crypto[J]. 1996.

3. [DJ01] Damgård I, Jurik M. A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system[C]//Public Key Cryptography: 4th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2001 Cheju Island, Korea, February 13–15, 2001 Proceedings 4. Springer Berlin Heidelberg, 2001: 119-136.

4. [Mic19] Daniele Micciancio. From linear functions to fully homomorphic encryption. Technical report,2019. https://bacrypto.github.io/presentations/2018.11.30-Micciancio-FHE.pdf.

5. [BDGM19] Brakerski Z, Döttling N, Garg S, et al. Leveraging linear decryption: Rate-1 fully-homomorphic encryption and time-lock puzzles[C]//Theory of Cryptography Conference. Cham: Springer International Publishing, 2019: 407-437.

6. [MT19] Giulio Malavolta and Sri Aravinda Krishnan Thyagarajan. Homomorphic time-lock puzzles and applications. CRYPTO, 2019.

Linear decrypt-and-multiply

from LHE to FHE

[Mic19] 讨论了如何从弱线性同态（Weak Linear Homomorphic）得到全同态（Full Homomorphic）。

基于 LWE 的线性同态加密方案（Linear Homomorphic Encryption, LHE），不考虑细节，

• 对称加密算法 $E_s(m;(A,e)):=(A,As+e+m)(\mathrm{mod}q)$，可以视为 One-time Pad，特别地 $(O,m)=E_s(m;(O,\vec{0}))$
• 对称解密算法 $D_s((A,b)):=b-As=m+e(\mathrm{mod}q)$，这既是 $ct=(A,b)$ 的线性函数，也是 $s^{\prime }=(-s,1)$ 的线性函数

由于解密是带噪的，因此我们往往对 $m$ 做编码；这儿我们先不考虑纠错码。易知，上述的 LHE 满足：
$$\begin{gathered} E_s(m_1;(A,e_1))+E_s(m_1;(A,e_1))=E_s(m_1+m_2;(A,e_1+e_2)) \\ c\cdot E_s(m;(A,e))=c\cdot E_s(c\cdot m;(c\cdot A,c\cdot e)),c\in {\mathbb{Z}}_q \end{gathered}$$

由于数乘运算的噪声为 $c\cdot e$，因此为了解密正确性，标量 $c$ 是个有界范围的数。上述的 LHE 满足（弱）线性同态。为了计算任意标量 $c$ 的数乘，可以定义 Powerof2 的密文：
E s ′ ( m ) = { E s ( m ) , E s ( 2 m ) , ⋯ , E s ( 2 log ⁡ q m ) } E'_s(m) = \{E_s(m),E_s(2m),\cdots,E_s(2^{\log q}m)\} Es′​(m)={Es​(m),Es​(2m),⋯,Es​(2logqm)}

那么对于任意的常数 $c={\sum }_i{2}^i{c}_i\in {\mathbb{Z}}_q$，我们定义运算 $c\ast E^{\prime }(m):={\sum }_i{c}_i\cdot E(2^{i}m)=E(c\cdot m)$，噪声扩张因子仅为 $\log q$ 而非 $q$。为了维持密文格式，可以这么计算：
E s ′ ( c ⋅ m ) = { c ∗ E ′ ( m ) , ( 2 c ) ∗ E ′ ( m ) , ⋯ , ( 2 log ⁡ q c ) ∗ E ′ ( m ) } E_s'(c \cdot m) = \{c*E'(m),(2c)*E'(m),\cdots,(2^{\log q}c)*E'(m)\} Es′​(c⋅m)={c∗E′(m),(2c)∗E′(m),⋯,(2logqc)∗E′(m)}

任意的弱线性同态的对称加密方案，都可以导出公钥方案：令公钥是一组密文 $c{t}_i=E_s(0;(A_i,b_i))$，那么加密方案就是一种同态线性运算
$$\sum _i{r}_i\cdot c{t}_i+(O,\alpha \cdot m)=E_s\left(m;\left(\sum _i{r}_i{A}_i,\sum _i{r}_i{e}_i\right)\right)$$

因为解密算法是关于私钥的线性函数，因此 LHE 可以使用私钥的密文来同态解密：将 $E^{\prime }(s^{\prime })=(E^{\prime }(-s),E^{\prime }(1))$ 作为公钥一部分，给定密文 $E(m)=(A,b)$，
$$E(m)\ast E^{\prime }(s^{\prime })=A\ast E^{\prime }(-s)+b\ast E^{\prime }(1)=E(b-As)=E(m)$$

也就是我们把左操作数视为常数矩阵，右操作数视为 LHE 密文列向量，计算对应的线性函数（同态加法、任意标量的同态数乘）。如果我们以 $E^{\prime }(\alpha \cdot s^{\prime })$ 作为公钥一部分，那么就可以计算出 $E(m)\ast E^{\prime }(\alpha \cdot s^{\prime })=E(\alpha \cdot m)$，这里的 $\alpha \in {\mathbb{Z}}_q$ 是任意常数。

比如原本应当解密出 $(q+1)/2\cdot m+e\in {\mathbb{Z}}_q$，我们选取 $2=((q+1)/2{)}^{-1}\in {\mathbb{Z}}_q$，那么就会解密出 $m+2e\in {\mathbb{Z}}_q$，这就完成了 MSB 和 LSB 之间的编码转换。即，我们可以将 $E^{\prime }(s^{\prime })$ 作为公钥一部分，然后对于任意常数 $\alpha$ 可计算同态数乘 $E^{\prime }(\alpha s^{\prime })$，再用它同态解密 $E^{\prime }(m)$ 得到形如 $\alpha m+e$ 的 “带噪的数乘的明文” 的密文。

对 LHE 做同态的 “decrypt and multiply（解密+数乘）”，就可以实现 FHE：我们定义加密算法为 $E^{\prime \prime }(m):=E^{\prime }(m\cdot s^{\prime })$，明文 $m\in {\mathbb{Z}}_q$ 是标量，那么
E ′ ′ ( m 1 ) ∗ E ′ ′ ( m 2 ) = { E ( m 1 ⋅ 2 i s ′ ) ∗ E ′ ( m 2 ⋅ s ′ ) } i = { E ( m 1 ⋅ 2 i s ′ ⋅ m 2 ) } i = E ′ ( m 1 m 2 ⋅ s ′ ) = E ′ ′ ( m 1 m 2 ) \begin{aligned} E''(m_1) * E''(m_2) &= \{E(m_1 \cdot 2^is')*E'(m_2 \cdot s')\}_i\\ &= \{E(m_1 \cdot 2^is' \cdot m_2)\}_i\\ &= E'(m_1m_2 \cdot s')\\ &= E''(m_1m_2)\\ \end{aligned} E′′(m1​)∗E′′(m2​)​={E(m1​⋅2is′)∗E′(m2​⋅s′)}i​={E(m1​⋅2is′⋅m2​)}i​=E′(m1​m2​⋅s′)=E′′(m1​m2​)​

[GSW13] 的矩阵密文和它的近似本征矢，密文 $C=(A,b)+\mu G$ 满足 $s^{t}C=(\mu s^t)G+e$（加密的是消息 $\mu s^t$ 的纠错码；在解密时 $G$ 用于纠错，乘法时 $G^{-1}$ 用于降低范数），其实这就是上述的 $E_s^{\prime \prime }(m)$（需要循环安全假设），所以它的同态乘法不会导致如 BGV/BFV 那样的密文规模扩张。而 [AP14] 中的 GSW 快速自举算法，用 GSW 做出累加器来实现 LWE 的自举，其实就是 $LW{E}_s(m;e_1)\ast E_s^{\prime \prime }(s)=LW{E}_s(m;e_2)$（也需要循环安全），使得 $\Vert e_1\Vert <\Vert e_2\Vert$ 即可成功。之后的 FHEW 中的 Multiplication via addition，基于布尔输入在 ${\mathbb{Z}}_4$ 中的特性 $m_1+m_2=2⟺m_1\cdot m_2=1$ （全加器的 $s=m_1\oplus m_2$ 和 $c=m_1\cdot m_2$），使用加法取代乘法 $m_1\cdot m_2=\frac{m_1+m_2}{2}\in {\mathbb{Z}}_2$，最后自举恢复到 ${\mathbb{Z}}_4$ 上。

Linear Function

利用上述的 Linear decrypt-and-multiply，我们可以实现一个线性函数加密。

令 $g=(1,2,4,\cdots ,2^k)$ 是 Gadget 行矢，$k$ 是明文比特长度，对应的 $g^{-1}(\cdot )$ 是二进制分解（列矢）。将 $g$ 排列为 Gadget 矩阵 $G\in {\mathbb{Z}}_q^{l\times lk}$，那么 $\vec{m}G=(m_{1}g,m_{2}g,\cdots ,m_{l}g)$ 就是各个分量 powerof2 组成的行矢，容易对应构造 $G^{-1}(\cdot )$ 是各个分量的二进制分解组成的列矢。于是 $\vec{m}G\cdot G^{-1}(\vec{f})=\vec{m}\cdot \vec{f}$ 计算了 $l$ 变元线性函数 $f(m)$

我们令 $\Delta \in \mathbb{Z}$ 是纠错能力，密文模数 $q\ge \Delta (2^k{)}^2$（使得 $\Delta m_i{2}^k<q$ 不溢出），$(A,B)\in {\mathbb{Z}}_q^{n\times m}\times {\mathbb{Z}}_q^{n\times lk}$ 是公钥，$S=[-S^{\prime },I{]}^T\in {\mathbb{Z}}_q^{(m+lk)\times lk}$，易知 $(A,B)\cdot S=B-A{S}^{\prime }=E\in {\mathbb{Z}}_q^{n\times lk}$，

1. 我们加密行矢 $\vec{m}G\in {\mathbb{Z}}_q^{lk}$，随机数 $r\in {\mathbb{Z}}_q^n$，得到密文 $C=(rA,rB+\Delta \vec{m}G+e)\in {\mathbb{Z}}_q^{m+lk}$（行矢）

2. 使用函数秘钥 $S{G}^{-1}(\vec{f})\in {\mathbb{Z}}_q^{m+lk}$（列矢），线性解密得到
   $$\begin{array}{rl}CS\cdot G^{-1}(\vec{f})& =(\Delta \vec{m}G+e+rE)\cdot G^{-1}(\vec{f})\\ & =\Delta f(m)+(e+rE)\cdot G^{-1}(\vec{f})\in {\mathbb{Z}}_q\end{array}$$

3. 纠错后提取出函数值 $f(m)=\vec{m}\cdot \vec{f}\in [0,2^k]$

Rate-1 FHE

正如 [Mic19] 所描述的，许多基于 LWE/SIS 的加密方案，其解密函数是关于私钥的线性函数，它满足
$$L_{\alpha ,c}(s)=\alpha \cdot m+e,|e|<B$$

其中的 $\alpha$ 并非被协议固定，而是可以任意选取的。这个计算过程叫做 “linear decrypt-and-multiply”，它可以在 LHE 下同态计算。

我们定义 Linear Decrypt-and-Multiply FHE，

我们可以利用 $L_{\alpha ,c}$ 线性函数，对于不同的密文 $c_i$ 选取不同的标量 ${\alpha }_i$，将多个 FHE 密文（明文空间 { 0 , 1 } \{0,1\} {0,1}）打包到单个 LHE 密文（明文空间 ${\mathbb{Z}}_q$）中：
$$L^{\ast }(s):=\sum _{i=1}^l{L}_{2^{i+1},c_i}(s)=\sum _{i=1}^l{2}^{t+i}{m}_i+\sum _{i=1}^l{e}_i$$

其中 $e$ 是 $lB$-bounded 的噪声项，只要满足 $2^t>|e|$ 则噪声不干扰消息 $m_i$ 所占据的高位比特。由于 LHE 明文空间是 ${\mathbb{Z}}_q$，噪声占据了低位的 $\log (lB)$ 比特，我们设置参数 $ϵ>0$ 使得模数 $q\approx (lB{)}^{1/ϵ}$，那么消息 $m_i$ 的空间占比至多为
$$\frac{\log (q)-\log (lB)}{\log (q)}\approx 1-ϵ$$

我们定义 FHE 方案的码率（Rate），

只要 LHE 本身是 Rate-1 的，那么将 $l$ 个 FHE 密文的消息编码到单个 LHE 密文中，这也是 Rate-1 的。在需要进行同态计算时，类似自举，将 LHE 转化回 FHE 即可；而计算结束后，重新把 FHE 密文打包到 LHE 密文中，以降低存储开销。

上述的消息打包方案可以写作 $(2^{t+1},\cdots ,2^{t+l})\cdot (m_1,\cdots ,m_l)$，更一般的编码形式为 $T\cdot m,T\in {\mathbb{Z}}_q^{k\times l}$，它支持从 $Tm+e$ 中纠错解码出消息 $\vec{m}$。对于 Regev 方案，编码矩阵为 $T=\frac{q}{2}I$。

密文收缩的 Regev

[BDGM19] 通过对 Regev-like 方案的密文做 “收缩（记为 Shrink，与 Compress 做区分）”，从而得到 Rate-1 LHE。

除了原始 Regev 方案的 $(KeyGen,Enc,Dec,Eval)$，我们额外添加两个功能：

1. $\bar{c}\leftarrow Shrink(pk,c)$：将 LHE 密文收缩为一个 shrunk ciphertext
2. $m\leftarrow ShrinkDec(sk,\bar{c})$：对 shrunk ciphertext 解密

[BDGM19] 将 LHE 的解密函数中的纠错码解码（舍入、取模）分离出来，使得 $Dec(\cdot )$ 仅仅是一个线性函数。令编码矩阵 $T\in {\mathbb{Z}}_q^{k\times l}$ 指定了消息 m ∈ { 0 , 1 } l m \in \{0,1\}^l m∈{0,1}l 如何编码到空间 ${\mathbb{Z}}_q^k$ 中，

假设私钥 $S\in {\mathbb{Z}}_q^{k\times n}$，密文形如 $(c_1,c_2)$，解密算法写作
$$De{c}_S(c_1,c_2)=F(c_2)-S\cdot H(c_1)$$

其中 $F,H$ 是公开函数，于是解密函数就是关于 $S$ 的线性函数，常数是 $F(c_2)\in {\mathbb{Z}}_q^k,H(c_1)\in {\mathbb{Z}}_q^n$

假设噪声规模为 $B$，编码矩阵为 $T=\frac{q}{2}I,k=l$，那么危险区是 $[q/4-B,q/4+B]$ 以及 $[-q/4-B,-q/4+B]$。只要 $qm/2$ 不落在危险区内，解码时就不会出现错误。

密文收缩算法如下：

• $Shrink(pk,(c_1,c_2))$：计算 $F(c_2)$ 得到 $(y_1,\cdots ,y_l)\in {\mathbb{Z}}_q^l$，定义区域
  $$U=\bigcup _{i=1}^l[q/4-B-y_i,q/4+B-y_i]\cup [-q/4-B-y_i,-q/4+B-y_i]$$

  我们任意选取 $r\in {\mathbb{Z}}_q-U$（只要 $q$ 足够大，总会存在），计算 $w_i=\lceil y_i+r{\rfloor }_2$，输出收缩的密文 $\bar{c}=(r,c_1,w_1,\cdots ,w_l)$

• $ShrinkDec(S,\bar{c})$：计算 $S\cdot H(c_1)$ 得到 $(v_1,\cdots ,v_l)\in {\mathbb{Z}}_q^l$，然后计算 $m_i=w_i-\lceil v_i+r{\rfloor }_2(\mathrm{mod}2)$，输出消息 $m=(m_1.\cdots ,m_l)$

因为 $r\notin U$，因此 $\forall y_i,y_i+r\notin [q/4-B,q/4+B]\cup [-q/4-B,-q/4+B]$。根据解密函数等式 $y_i-v_i=q{m}_i/2+e_i$，得到
$$w_i=\lceil y_i+r{\rfloor }_2=\lceil y_i+r-e_i{\rfloor }_2=\lceil q{m}_i/2+v_i+r{\rfloor }_2=\lceil v_i+r{\rfloor }_2+m_i(\mathrm{mod}2)$$

因为共有 $l$ 个危险区 $[q/4-B-y_i,q/4+B-y_i]\cup [-q/4-B-y_i,-q/4+B-y_i]$，每个危险区长度为 $4B$，因此只要模数 $q>4lB$，就可以找到 $r\notin U$。上述密文收缩过程，把密文分量 $c_2$ 压缩到了 $\log q+l$ 比特（$r$ 和 $w_i$），而消息长度为 $l$ 比特。接下来，我们让多个 LHE 密文共用分量 $c_1$，于是均摊之后将得到 rate-1 的 LHE 方案。

令 $k=\log q$，设 $g=(1,2,\cdots ,2^k)$ 是 Gadget 行矢，那么 $y=gx\in {\mathbb{Z}}_q$ 就是二进制合成，而对应的 $g^{-1}(y)$ 就是二进制分解。我们记 $G_i\in {\mathbb{Z}}_q^{l\times k}$ 是除了第 $i$ 行是 $g$ 其他的位置都是零的矩阵。

由于 Regev 方案仅仅是加法同态的，为了支持任意标量的数乘，使用 $g,g^{-1}$ 将消息 $m_i$ 扩展为向量。我们定义 Packed Regev Encryption 线性同态加密方案，

只要 $m>(n+l)\log q+w(\log \lambda )$，那么根据 Leftover-Hash Lamma [ILL89] 可知密文 $(C_1,C_2)$ 统计接近均匀分布。经过 $Eval$ 后，噪声为 $e=E\cdot {\sum }_i{R}_i\cdot g^{-1}(f_i)$，规模 $\Vert e{\Vert }_{\infty }\le tkmB$。因此我们选取 $q\approx 4ltkmB$，使得存在 $r$ 来收缩密文得到 $(r,c_1,w_1,\cdots ,w_l)$，密文规模为 $(n+1)\log q+l$，码率为
$$\rho =\frac{l}{(n+1)\log q+l}\ge 1-\frac{(n+1)\log q}{l}$$

对于 $q=poly(\lambda )$，可界定 $\log q\le (\log \lambda {)}^2$，选取充分大的 $l\ge n\lambda (\log \lambda {)}^2$ 可以使得 $\rho \ge 1-1/\lambda$。这就得到了 Rate-1 LHE。

扩展的 Paillier

[DJ01] 扩展了 Paillier 算法，将群 ${\mathbb{Z}}_{n^2}^{\ast }$ 推广到了 ${\mathbb{Z}}_{n^{s+1}}^{\ast },\forall s\ge 1$，使得码率接近于 $1$。而 Paillier 本身是一个 LHE，这是另一种 Rate-1 LHE，好处是计算无噪声，但是安全性基于数论假设而非格上困难问题。

令 $p,q$ 是安全素数，$n=pq$ 是个 RSA 模数。对于 $\forall s<p,q$，可以证明乘法群 ${\mathbb{Z}}_{n^{s+1}}^{\ast }\cong G\times H$，其中 $G$ 是 $n^s$ 阶循环群，且 $H\cong {\mathbb{Z}}_n^{\ast }$。可以证明在 ${\mathbb{Z}}_{n^{s+1}}^{\ast }$ 中有 $ord(n+1)=n^s$，于是 $\bar{G}:={\mathbb{Z}}_{n^{s+1}}^{\ast }/H=⟨(n+1)H⟩$ 是循环群，陪集 $(n+1{)}^{i}H\subseteq {\mathbb{Z}}_{n^{s+1}}^{\ast }$ 可以用自然数编号。

循环群 $\bar{G}$ 上的 DL 问题是简单的。定义函数 $L(b)=(b-1)/n$（这儿就是整数除法，并非求逆元），那么
$$L((n+1{)}^i(\mathrm{mod}{n}^{s+1}))=(\genfrac{}{}{0ex}{}{i}{1})+(\genfrac{}{}{0ex}{}{i}{2})n+\cdots +(\genfrac{}{}{0ex}{}{i}{s})n^{s-1}(\mathrm{mod}{n}^s)$$

为了提取出 $(n+1{)}^i(\mathrm{mod}{n}^{s+1})$ 的指数 $i$，我们依次计算 $i_j:=i(\mathrm{mod}{n}^{j+1})$，易知
$$i_1=L((n+1{)}^i(\mathrm{mod}{n}^2))=i(\mathrm{mod}n)$$

假设已知 $i_{j-1}$，我们计算 $i_j=i_{j-1}+k\cdot n^{j-1}$，
$$\begin{array}{rl}L((n+1{)}^i(\mathrm{mod}{n}^{j+1}))& =\left(\genfrac{}{}{0ex}{}{i_j}{1}\right)+\left(\genfrac{}{}{0ex}{}{i_j}{2}\right)n+\cdots +\left(\genfrac{}{}{0ex}{}{i_j}{j}\right)n^{j-1}(\mathrm{mod}{n}^j)\\ & =(i_{j-1}+k\cdot n^{j-1})+\left(\genfrac{}{}{0ex}{}{i_{j-1}}{2}\right)n+\cdots +\left(\genfrac{}{}{0ex}{}{i_{j-1}}{j}\right)n^{j-1}(\mathrm{mod}{n}^j)\end{array}$$

于是重写为迭代公式：
$$\begin{array}{rl}{i}_j& =i_{j-1}+k\cdot n^{j-1}\\ & =L((n+1{)}^i(\mathrm{mod}{n}^{j+1}))-(\genfrac{}{}{0ex}{}{i_{j-1}}{2})n-\cdots -(\genfrac{}{}{0ex}{}{i_{j-1}}{j})n^{j-1}(\mathrm{mod}{n}^j)\end{array}$$

从 $i_1$ 开始，迭代到 $i_s$ 结束，输出指数 $i=i_s\in {\mathbb{Z}}_{n^s}$

[DJ01] 给出的加密算法如下：

消息空间 ${\mathbb{Z}}_{n^s}$，密文空间 ${\mathbb{Z}}_{n^{s+1}}^{\ast }$，因此码率为
$$\rho =\frac{\log (n^s)}{\log (n^{s+1})}$$

当选取足够大的 $s$，就得到了 Rate-1 LHE。我们使用 $T=(2^{\log B},2^{\log B+1},\cdots ,2^{\lceil s\log n\rceil })$ 作为编码矩阵，抵御 $B$-bounded 的噪声。

Rate-1 FHE Construction

现在我们给出 Rate-1 FHE 的构造。除了原始 FHE 方案的 $(KeyGen,Enc,Dec,Eval)$，我们额外添加两个功能：

1. $c^{\ast }\leftarrow Compress(pk,c_1,\cdots ,c_l)$：将多个FHE 密文压缩为一个 compressed ciphertext
2. $(m_1,\cdots ,m_l)\leftarrow CompressDec(sk,c^{\ast })$：对 compressed ciphertext 解密得到多个消息

基于 FHE 以及 Rate-1 LHE，我们构造 Rate-1 FHE：

FH-TLP

Time-lock puzzles

时间锁谜题（Time-lock puzzles）最早在 [RSW96] 中作为一种 “时间依赖的密码” 被提出。谜题是基于困难问题的，并且被设置为无法并行加速，为了得到秘密，人们不得不持续运行求解器。[RSW96] 给出了一种基于 RSA 问题的 TLP，

1. Alice 生成一对安全素数 $p,q$，计算 $n=pq$，$\varphi (n)=(p-1)(q-1)$
2. Alice 生成对称秘钥 $K$，加密消息 $M$ 为 $C_M=En{c}_K(M)$
3. Alice 随机生成 $a\in [n]$，加密秘钥 $K$ 为 $C_K=K+a^{2^t}$，其中 $t$ 是预设的延迟时间。由于 Alice 持有 $\varphi (n)$，因此 $e=2^t(\mathrm{mod}\varphi (n))$ 是容易计算的。
4. Alice 发布 $(C_M,C_K,n,a,t)$ 作为谜题。由于 Bob 不知道 $\varphi (n)$，因此他只能串行计算一系列的模平方 $e^2,e^4,\cdots ,e^{2^t}$，花费的时间是 $t$

想要更快的完成 $t$ 次模平方，除非 Bob 拥有 IPS 特别高的 CPU，别无他法。

Rate-1 FH-TLP

同态的时间锁谜题，他可以对加密在多个时间锁谜题中的消息做同态计算，得到一个新的时间锁谜题，而无需爆破每一个谜题。定义如下：

在 [MT19] 中提出了一种线性同态的时间锁谜题：公钥 $(N=pq,g\in {\mathbb{Z}}_N^{\ast },h=g^{2^T})$，秘密 $s\in {\mathbb{Z}}_N$，谜题为 $\left(g^r(\mathrm{mod}N),h^{rN}(N+1{)}^s(\mathrm{mod}{N}^2)\right)$，其中 $r{\leftarrow }_R{\mathbb{Z}}_{N^2}$ 是随机数。Alice 知道 $r$，因此可以用快速幂算法计算 $h^{rN}(\mathrm{mod}{N}^2)$；而 Bob 只知道 $g^r(\mathrm{mod}N)$，只能串行计算 $T$ 次模平方，恢复出 $(N+1{)}^s(\mathrm{mod}{N}^2)$ 则指数 $s$ 容易计算。它是线性同态的，类似于 [DJ01] 可以获得 Rate-1 LH-TLP。

因为全同态 TLP 的各个谜题可能来自多个用户，我们需要用到 MK-FHE，使用上面的技术可以做到 Rate-1 的。基于 MK-FHE 和 LH-TLP，可以得到 Rate-1 FH-TLP：