全同态加密中的多数据编码技术革新

### 全同态加密中的多数据编码技术革新 #### 1. 引言 全同态加密（FHE）自Gentry首次实现以来，取得了显著的进展。目前，广泛使用的主要有四种方案：Brakerski - Gentry - Vaikunathan（BGV）、Brakerski - Fan - Vercauteren（BFV）、Cheon - Kim - Kim - Song（CKKS）以及FHEW/TFHE。前两种方案支持有限域操作，CKKS方案支持数字的近似算术，而FHEW/TFHE家族则适用于位或低精度数字。 多数FHE实现，如SEAL、PALISADE和Lattigo，主要关注BGV和BFV使用2的幂次分圆多项式模的情况。这些参数借助负循环快速傅里叶变换（FFT）实现了高效的算术运算。然而，像t = 3、5、7、11这样的小素数在这些情况下并不适用，因为明文空间分解为有限数量的槽，且槽代数对应于高扩展度的有限域。因此，BGV和BFV的应用主要集中在字长同态加密，使用32位或更多位的大素数、整数和分数编码，以及用于高精度整数算术的替代“多项式模”。 虽然已经有许多关于使用低到中等扩展度（≤64）的有限扩展域进行同态计算的研究，但仍缺乏解锁高扩展度域用于同态计算的技术。而高扩展度域的应用有望通过负循环FFT实现的更快算术运算，改善小素数算术电路的性能。 #### 2. 主要贡献 - **引入字段指令多数据（FIMD）**：FIMD通过利用单指令多数据（SIMD）中扩展域明文结构的固有向量，将更多数据编码到FHE密文中。它在FHE中增加了一层数据打包，将基/中间域元素向量嵌入到SIMD明文的每个槽中，使得可以对编码向量进行同态操作。字段加法、乘法和线性化多项式求值分别对应于加密向量上的逐分量加法、乘法和线性映射。 - **应用反向乘法友好嵌入（RMFE）**：将Cascudo等人定义的RMFE应用于FHE。RMFE允许将长度为k的小域元素向量（F）k编码为更大扩展域E/F的单个元素。这些扩展域元素的乘积对应于底层向量的逐分量乘法。但此过程并非同态，因此不能支持任意数量的乘法。为解决这一限制，Cascudo等人定义了重编码协议ReEncode，在每次多方计算（MPC）乘法后一次性解码并重新编码域元素，以便用于后续乘法。 - **RMFE在FHE中的应用关键**：编码、解码和重编码操作是（F）k和E之间的F线性映射，这些映射可以用线性化多项式表示，并使用低噪声Frobenius自同构在FHE中进行求值。此外，通过将重编码操作修改为解码、线性变换M和编码的组合，可以免费实现加密向量的旋转、移位和任意线性变换M。这使得FIMD在明文空间上的线性变换开销方面比SIMD更具灵活性，但FIMD在乘法后需要重编码操作。重要的是，FHE中的重编码操作是非交互式的，无需任何预处理。 - **提出r - 折叠RMFE**：为了分摊同态RMFE重编码操作的开销，提出了r - 折叠RMFE，代价是降低了打包效率。r - 折叠RMFE允许在解码之前将最多2r个向量的编码相乘。在满足一定条件下，它还可以在解码之前计算最高次数为2r的多元多项式。 - **引入三阶段重编码过程**：对于由两个组件RMFE组成的RMFE，引入了三阶段重编码过程。利用这种RMFE基于域扩展塔F ⊂ E1 ⊂ E2的特点，应用三个线性映射ψout : E2 → (E1)kout、φout : (E1)kout → E2和π′in : (E1)kout → (E1)kout，每个映射的次数都低于重编码映射π : E2 → E2。与标准重编码过程相比，这种方法减少了所需的Frobenius自同构数量。 - **实验验证**：通过实验比较了本文引入的各种RMFE变体与标准FHE乘法的效率。结果表明，FIMD提高了小明文模下FHE的性能，不仅实现了超过2倍的乘法加速，还在整个过程中减少了多达k/2倍的密文使用。 #### 3. 相关工作 - **有限域在同态计算中的应用**：Kim等人首次考虑利用有限域进行同态计算，他们展示了如何使用费马小定理高效计算两个加密整数的相等性。J¨aschke和Armknecht探索了使用扩展域中的加法和乘法来计算整数加法，但效果不佳。Tan等人利用扩展域的向量空间性质，提出了提取然后计算的方法来比较加密整数。Illiashenko和Zucca利用比较多项式的性质，在同态比较中达到了与基于THFE的方法相当的效率。 - **整数和定点数的编码**：Dowlin等人考虑将整数和分数分解为二进制表示，然后将其编码为多项式以实现快速算术运算。Costache等人证明了Dowlin等人的两种方法是同构的，并推导了支持同态计算的表示的下界。Castryck等人进一步将其扩展到基于Laurent多项式的更灵活编码，并对具有复合明文模的FHE明文空间进行更细粒度的分解。Chen等人提出用X - b替换明文模t，得到明文空间Z/(bn + 1)Z，实现高精度算术。Bootland等人将其推广到支持复值数据，考虑形式为Xm + b的多项式。 - **RMFE在多方计算中的应用**：Cascudo等人使用RMFE提高了MPC协议的通信复杂度，以牺牲域的大小为代价。Block等人将其应用于二进制域上的MPC，实现了更高效的批量乘法。此后，RMFE被推广到支持Galois环上的MPC，以及用于评估更复杂电路的电路摊销友好嵌入。对于基于HE的Z2k上的MPC，还开发了Overdrive2k和MHz2k协议，用于将Z2k消息打包到多项式中，支持深度为1的同态对应。 #### 4. 预备知识 ##### 4.1 全同态加密 分层全同态加密（FHE）方案是一种支持评估深度最多为L的电路的同态加密方案，其中L是预定义的非负整数。消息m的加密表示为m，用P表示FHE方案可能消息的空间。 FHE方案包含以下主要算法： | 算法 | 输入 | 输出 | 说明 | | --- | --- | --- | --- | | KeyGen(1λ, 1L) | 安全参数λ和级别参数L | 公钥pk、秘密密钥sk和评估密钥evk | 生成加密所需的各种密钥 | | Enc(pk, m) | 公钥pk和消息m ∈ P | 密文c = m | 对消息进行加密 | | Dec(sk, c) | 秘密密钥sk和密文c | 消息m′ ∈ P | 对密文进行解密 | | Eval(evk, f, m1, ..., mn) | 评估密钥evk、函数f : Pn → P和密文m1, ..., mn | 密文c′ | 对加密数据进行函数求值，满足Dec(sk, c′) = f(m1, ..., mn) | Eval算法通常使用的子例程包括： - **EvalAdd(evk, m1, m2)**：输入评估密钥evk和两个密文m1、m2，输出密文c+ = m1 + m2，加密输入消息的和。 - **EvalMul(evk, m1, m2)**：输入评估密钥evk和两个密文m1、m2，输出密文c× = m1 × m2，加密输入消息的乘积。 对于所有已知的基于（环）学习错误（(R)LWE）问题的（分层）FHE方案，密文是其底层明文的有噪声加密。这意味着在密文中的噪声超过数据之前，只能进行有限数量的计算。 SIMD是FHE中的一种技术，