1. 论文基本信息
1.1. 标题
Homomorphic Multiple Precision Multiplication for CKKS and Reduced Modulus Consumption
1.2. 作者
Jung Hee Cheon (CryptoLab Inc. & Seoul National University), Wonhee Cho (Seoul National University), Jaehyung Kim (CryptoLab Inc.), Damien Stehlé (CryptoLab Inc.)
1.3. 发表期刊/会议
该论文是一个预印本 (ePrint)。
1.4. 发表年份
2023年
1.5. 摘要
我们提出了一种名为 M u l t 2 Mult^2 M u l t 2 的新方法,用于在 CKKS (Cheon-Kim-Kim-Song) 方案中执行密文乘法,显著降低了模数消耗。该方法通过将密文分解为一对密文来同态地执行一种弱形式的欧几里得除法。这种分解允许同态双精度乘法,其结果近似解密后与标准 CKKS 乘法相同,但模数消耗几乎减半。我们将此方法扩展到任何 t ≥ 2 t \ge 2 t ≥ 2 的 M u l t t Mult^t M u l t t ,其中密文被分解为 t t t 个组件,从而实现同态多精度算术(双精度 CKKS 和元组 CKKS)。
所提出的算法在不增加密文维度或引导操作 (bootstrap) 次数的情况下,允许更深层次的电路评估,或者等效地减少相同电路深度所需的引导操作。它们还可以在不增加参数的情况下提高精度。例如,M u l t 2 Mult^2 M u l t 2 允许在仅有 680 比特密文模数的情况下,执行 8 次连续乘法并保持 100 比特的缩放因子,这对于普通的 CKKS 乘法是无法实现的。实验结果和理论分析都支持我们方案的效率和改进的模数消耗。
1.6. 原文链接
https://eprint.iacr.org/2023/1788.pdf (预印本)
2. 整体概括
2.1. 研究背景与动机
核心问题: 同态加密 (Homomorphic Encryption, HE) 方案,如 BGV、BFV 和 CKKS,在每次执行乘法运算时都会消耗一部分密文模数 (ciphertext modulus)。当模数变得过小,就无法继续执行乘法。
问题重要性: 模数消耗是一个关键瓶颈。解决这个问题的传统方法是引导操作 (bootstrapping),它通过同态评估一个模约减函数的近似值来恢复模数,从而允许计算继续。然而,引导操作本身非常耗时且需要消耗大量的模数资源。因此,减少模数消耗一直是 BGKS、BFV 和 CKKS 等方案中的一个重要研究方向。
现有研究空白与挑战: 许多现有工作侧重于通过使用“小工具分解” (gadget decomposition) 来减少密钥切换 (key switching) 步骤中的模数消耗,或者改进引导操作本身。然而,这些工作往往没有直接针对同态乘法本身的模数消耗进行优化。
本文的切入点/创新思路: 本文提出了一种新颖的技术,旨在直接降低同态乘法过程中的模数消耗。其核心思想是将高精度乘法分解为多个低精度乘法,通过同态欧几里得除法将单个密文分解为多个“分量密文” (component ciphertexts),从而在执行乘法时只处理与所需精度相关的部分,丢弃低位部分,达到节省模数的目的。
2.2. 核心贡献/主要发现
本文的主要贡献在于:
提出 M u l t 2 Mult^2 M u l t 2 方法: 引入了一种新颖的 M u l t 2 Mult^2 M u l t 2 方法,用于 CKKS 方案中的密文乘法。该方法通过将密文分解为一对密文来同态执行弱形式的欧几里得除法,从而实现同态双精度乘法。
显著降低模数消耗: M u l t 2 Mult^2 M u l t 2 在乘法过程中能够将模数消耗几乎减半,而其结果近似解密后与标准 CKKS 乘法结果相同。
泛化到 M u l t t Mult^t M u l t t : 将 M u l t 2 Mult^2 M u l t 2 扩展为 M u l t t Mult^t M u l t t ,其中密文被分解为 t t t 个组件,实现了同态多精度算术(包括双精度 CKKS 和元组 CKKS)。
提高电路深度或减少引导操作: 在密文模数和维度固定的情况下,所提出的算法能够评估更深层次的电路,而无需执行引导操作;或者,对于相同深度的电路,可以显著减少所需的引导操作次数。
在不增加参数的情况下提高精度: 算法可以在不增加环维度 N N N 等参数的前提下,实现更高的计算精度。
实验验证效率: 通过具体实验证明了 M u l t 2 Mult^2 M u l t 2 的效率和模数消耗的改进。例如,M u l t 2 Mult^2 M u l t 2 允许在仅有 680 比特密文模数下执行 8 次连续乘法并保持 100 比特缩放因子,这比传统 CKKS 方案在需要 1000 比特模数和更大的环度 N N N 才能实现同等效果的情况,在计算延迟、密文大小和切换密钥大小方面都有显著优势。
3. 预备知识与相关工作
3.1. 基础概念
同态加密 (Homomorphic Encryption, HE) :一种加密技术,允许在加密数据上执行计算,而无需先解密。这意味着第三方可以在不了解数据内容的情况下处理数据,从而保护数据隐私。
全同态加密 (Fully Homomorphic Encryption, FHE) :支持任意数量的加法和乘法运算的同态加密方案。Gentry 在 2009 年首次提出了一个 FHE 方案。
近似同态加密 (Approximate Homomorphic Encryption) :CKKS 方案是近似同态加密的一种,它支持对实数和复数进行高效的近似计算,通常用于机器学习等需要浮点运算的场景。在每次计算后,噪声会累积,导致解密结果与精确结果之间存在微小误差。
密文模数 (Ciphertext Modulus) :在 CKKS 等 HE 方案中,密文是在一个大的模数 Q Q Q 下定义的环元素。每次同态乘法后,为了控制噪声增长并保持精度,密文模数会降低。
模数消耗 (Modulus Consumption) :同态乘法操作需要将密文的模数从 Q l Q_l Q l 降低到 Q l − 1 Q_{l-1} Q l − 1 ,这个过程被称为模数消耗。当模数降到一定程度,就无法再执行乘法,需要进行引导操作。
引导操作 (Bootstrapping, BTS) :当密文模数变得过小,无法继续同态计算时,通过执行一个复杂的同态函数(包括模约减函数、DFT 等)来“刷新”密文,重新增加其模数,从而允许继续计算。这是一个计算成本高昂的操作。
RNS (Residue Number System, 剩余数系统) :一种高效处理大整数模运算的技术。在 CKKS 方案中,大模数 Q Q Q 通常是多个较小素数的乘积,RNS 允许在这些较小的素数模下并行进行计算,然后通过中国剩余定理 (Chinese Remainder Theorem, CRT) 组合结果,从而显著提高效率。
环 R = Z [ X ] / ( X N + 1 ) R = \mathbb{Z}[X]/(X^N+1) R = Z [ X ] / ( X N + 1 ) : CKKS 方案的底层代数结构。N N N 是一个 2 的幂次,环元素是系数在整数域 Z \mathbb{Z} Z 中的多项式,模多项式 X N + 1 X^N+1 X N + 1 。R q = R / q R R_q = R/qR R q = R / qR 表示在模 q q q 下的环。
规范嵌入 (Canonical Embedding, can) :一个将环 R R R 中的多项式映射到复数向量空间 C N / 2 \mathbb{C}^{N/2} C N /2 的同构映射。它通过在 2N 次单位根处评估多项式来实现。这对于分析误差增长和精度非常有用,因为 can 映射下的乘法是点乘,范数增长行为比多项式乘法更可控。
缩放因子 (Scaling Factor, Δ \Delta Δ ) :CKKS 方案中用于在明文(实数/复数)和明文多项式之间转换的关键参数。在编码时,明文乘以 Δ \Delta Δ 并四舍五入为整数系数多项式;在解码时,明文多项式除以 Δ \Delta Δ 。Δ \Delta Δ 的大小直接影响数值精度。
CKKS 基本操作 :
密钥生成 (Key Generation) :生成秘密密钥 sk、公钥 pk 和切换密钥 swk(包括重线性化密钥 rlk 和旋转密钥 rk)。
加密 (Encryption, Enc) :将明文多项式 m(X) 转换为密文 ct。
解密 (Decryption, Dec) :将密文 ct 恢复为明文多项式 m(X)。
重缩放 (Rescale, R S q ( c t ) RS_q(ct) R S q ( c t ) ) :将密文模数从 Q l Q_l Q l 降低到 Q l − 1 Q_{l-1} Q l − 1 (通过除以 q l = Q l / Q l − 1 q_l = Q_l / Q_{l-1} q l = Q l / Q l − 1 ),并调整底层明文的缩放因子,以控制噪声和维持精度。
加法/减法 (Add/Sub) :同态加法和减法是逐分量进行的,不消耗模数。
CKKS 乘法步骤 :
张量积 (Tensor, c t ⊗ c t ′ ct \otimes ct' c t ⊗ c t ′ ) :将两个密文 ct 和 ct' 组合成一个秩更高的密文 ct_ten。其解密结果是原始明文的乘积。
重线性化 (Relinearization, Relin) :将 Tensor 操作后生成的秩更高的密文(例如,从 R Q 2 R_Q^2 R Q 2 变为 R Q 3 R_Q^3 R Q 3 )转换回标准形式(R Q 2 R_Q^2 R Q 2 ),以便后续操作。这需要重线性化密钥 rlk。
重缩放 (Rescaling, RS) :在 Relin 之后执行,用于降低模数并调整缩放因子。
3.2. 前人工作
Gentry 的 FHE [17] :开创了全同态加密领域,虽然效率较低,但证明了 FHE 的可行性。
CKKS 方案 [12] :由 Cheon、Kim、Kim 和 Song 提出,是目前最流行的近似同态加密方案之一,特别适用于对实数和复数进行计算(例如机器学习)。
CKKS 引导操作 [10] :CKKS 方案的引导操作,其核心是同态评估一个多项式近似的模约减函数。尽管提高了效率,但仍然是计算成本最高的步骤之一。
模数消耗优化 :
小工具分解 (Gadget Decomposition) :用于密钥切换步骤,以避免模数消耗。包括比特分解 (bit decomposition) [5,6]、数字分解 (digit decomposition) [13] 和基于 RNS 的分解 (RNS-based decomposition) [3,20,21]。
局限性: 小工具分解通常会使密钥切换变慢,并按相同因子增加密钥大小。例如 SEAL 库中,对于 N = 2 15 N = 2^{15} N = 2 15 ,切换密钥大小可达 142.6MB。
其他特定操作优化 :一些工作致力于减少线性变换和引导操作中的模数消耗 [2,7,8,21,24,31-33]。
局限性: 这些研究主要关注大规模计算(如引导操作),并未直接改进同态乘法本身。
降低环维度 (Ring Dimension) :
模块-LWE (Module-LWE) 格式 :如 [6] 中提出并在 CKKS 背景下 [39] 进一步研究的模块-CKKS。
与 Double-CKKS 的比较: ModuleCKKS 保持与 CKKS 相同的模数,但密文包含 3 个环元素(而非 CKKS 的 2 个)。Double-CKKS 允许将最大模数比特大小减半,密文包含 4 个环元素。结果是,Double-CKKS 密文的比特大小比秩-2 ModuleCKKS 密文小 33%。此外,Double-CKKS 乘法的重线性化次数为 2,而 ModuleCKKS 为 3,表明 Double-CKKS 在计算成本上也更具优势。对于更大的 t t t 值(Tuple-CKKS),这种优势更为明显。
3.3. 技术演进
FHE 技术的演进路线大致是从理论可行性(Gentry)到实际可用性(CKKS 等方案的提出),再到性能优化。在性能优化方面,降低模数消耗和引导操作的效率一直是核心。早期工作主要通过改进算法、使用 RNS 等技术来提高效率,并尝试通过小工具分解等方法减少密钥切换的模数消耗。本文则代表了另一个方向的进步:直接从同态乘法操作本身入手,通过多精度分解来减少模数消耗,从而在保持精度的前提下,延长同态计算链的深度,或降低整体参数需求,进一步推动 HE 在实际应用中的性能边界。
3.4. 差异化分析
本文 M u l t 2 Mult^2 M u l t 2 /M u l t t Mult^t M u l t t 方法的核心创新点在于:
直接优化同态乘法: 与许多关注密钥切换或引导操作的工作不同,M u l t t Mult^t M u l t t 直接改进了同态乘法本身,通过分解密文来减少其模数消耗。
弱形式的同态欧几里得除法: 引入了 DCP 操作,实现了对密文底层明文的同态欧几里得除法,这是其多精度算术的基础。
多精度算术: 实现了“双精度 CKKS”和“元组 CKKS”,使得一个“高精度”的密文被逻辑上拆分为多个“低精度”的密文分量,在乘法时通过巧妙的组合和截断,达到了模数节省。
模数减半/多倍节省: M u l t 2 Mult^2 M u l t 2 几乎将模数消耗减半,而 M u l t t Mult^t M u l t t 可以将模数消耗减少 t t t 倍,这是通过在 Tensor 步骤中丢弃低位项并设计特殊的 Relin 和 RS 操作实现的。
参数优化潜力: 这种模数节省不仅意味着更深的电路,还可以在相同安全级别下允许更小的环维度 N N N 和切换密钥大小,从而显著降低内存和计算开销,这在其他模数优化方法中并不总是能直接实现的。
与 ModuleCKKS 的对比: 尽管 ModuleCKKS 也能通过改变密文结构来优化,但 Double-CKKS 在密文大小和重线性化次数上都表现出优势,且其模数降低策略更加直接。
4. 方法论
本文的核心是提出了一种名为 M u l t t Mult^t M u l t t 的新型同态乘法方法,它通过将密文分解成多个组件来显著降低模数消耗。这依赖于同态欧几里得除法和对 CKKS 乘法基本步骤(张量积 Tensor、重线性化 Relin 和重缩放 RS)的修改。
4.1. 方法原理:同态欧几里得除法与密文分解
4.1.1. 将大整数乘法分解为小整数乘法
为了降低同态乘法的模数消耗,作者的思路是将大比特数的乘数分解为多个小比特数的乘数进行乘法运算。
考虑两个 2k 比特整数 m 1 m_1 m 1 和 m 2 m_2 m 2 。我们可以将它们分解为两个 k k k 比特的片段:
m i = 2 k ⋅ m ^ i + m ˇ i m_i = 2^k \cdot \hat{m}_i + \check{m}_i m i = 2 k ⋅ m ^ i + m ˇ i ,其中 m ˇ i = ( m i ( m o d 2 k ) ) \check{m}_i = (m_i \pmod{2^k}) m ˇ i = ( m i ( mod 2 k )) 。
它们的乘积为:
m 1 m 2 = 2 2 k m ^ 1 m ^ 2 + 2 k ( m ^ 1 m ˇ 2 + m ˇ 1 m ^ 2 ) + m ˇ 1 m ˇ 2
m_1 m_2 = 2^{2k} {\hat{m}_1} {\hat{m}_2} + 2^k \bigl( {\hat{m}_1} {\check{m}_2} + {\check{m}_1} {\hat{m}_2} \bigr) + {\check{m}_1} {\check{m}_2}
m 1 m 2 = 2 2 k m ^ 1 m ^ 2 + 2 k ( m ^ 1 m ˇ 2 + m ˇ 1 m ^ 2 ) + m ˇ 1 m ˇ 2
这个 2k 比特数的乘法可以分解为四个 k k k 比特数的乘法。在定点数运算中,如果只需要相对精度 ≈ 2 − 2 k \approx 2^{-2k} ≈ 2 − 2 k ,那么最后一项 m ˇ 1 m ˇ 2 \check{m}_1 \check{m}_2 m ˇ 1 m ˇ 2 可以被舍弃,从而将乘法结果的“片段”数量保持不变。
4.1.2. 同态欧几里得除法
尝试 1:先分解后加密(失败)
如果先在明文空间中将一个大比特数的明文 m m m 分解为 m = 2 k m ^ + m ˇ m = 2^k \hat{m} + \check{m} m = 2 k m ^ + m ˇ ,然后分别加密 m ^ \hat{m} m ^ 和 m ˇ \check{m} m ˇ 为 c t ^ \hat{\mathrm{ct}} ct ^ 和 c t ˇ \check{\mathrm{ct}} ct ˇ 。
解密时,我们得到 2 k D e c ( c t ^ ) + D e c ( c t ˇ ) = 2 k ( m ^ + e ^ ) + ( m ˇ + e ˇ ) 2^k \mathsf{Dec}(\hat{\mathrm{ct}}) + \mathsf{Dec}(\check{\mathrm{ct}}) = 2^k (\hat{m} + \hat{e}) + (\check{m} + \check{e}) 2 k Dec ( ct ^ ) + Dec ( ct ˇ ) = 2 k ( m ^ + e ^ ) + ( m ˇ + e ˇ ) 。
尽管噪声 e ^ \hat{e} e ^ 和 e ˇ \check{e} e ˇ 本身很小,但由于 e ^ \hat{e} e ^ 被乘以 2 k 2^k 2 k ,其引入的误差 2 k e ^ 2^k \hat{e} 2 k e ^ 会变得非常大,甚至可能大于 m ˇ \check{m} m ˇ ,导致整体相对精度很低,这种方法失败。
尝试 2:先加密后同态分解(本文方法)
本文提出在密文层面上进行分解。这等价于对明文进行欧几里得除法。
考虑一个 CKKS 密文 c t ∈ R 2 k Q 2 \mathsf{ct} \in R_{2^k Q}^2 ct ∈ R 2 k Q 2 ,其模数 2 k Q 2^k Q 2 k Q 可以被除数 2 k 2^k 2 k 整除。
定义 3.1(密文欧几里得除法)
设 q ∣ Q q|Q q ∣ Q 为两个整数。设 c t = ( b , a ) ∈ R Q 2 \mathsf{ct} = (b, a) \in R_Q^2 ct = ( b , a ) ∈ R Q 2 为一个密文。
密文 c t \mathsf{ct} ct 被 q q q 除的余数定义为:
R e m q ( c t ) = ( [ b ] q , [ a ] q ) ∈ R 2
\mathsf{Rem}_q(\mathsf{ct}) = ([b]_q, [a]_q) \in R^2
Rem q ( ct ) = ([ b ] q , [ a ] q ) ∈ R 2
密文 c t \mathsf{ct} ct 被 q q q 除的商定义为:
Q u o q ( c t ) = R S q ( c t ) = c t − R e m q ( c t ) q ∈ R Q / q 2
\mathsf{Quo}_q(\mathsf{ct}) = \mathsf{RS}_q(\mathsf{ct}) = \frac{\mathsf{ct} - \mathsf{Rem}_q(\mathsf{ct})}{q} \in R_{Q/q}^2
Quo q ( ct ) = RS q ( ct ) = q ct − Rem q ( ct ) ∈ R Q / q 2
其中,R e m q ( c t ) \mathsf{Rem}_q(\mathsf{ct}) Rem q ( ct ) 中的系数取值范围为 ( − q / 2 , q / 2 ] (-q/2, q/2] ( − q /2 , q /2 ] 。Q u o q ( c t ) \mathsf{Quo}_q(\mathsf{ct}) Quo q ( ct ) 在模 Q Q Q 下计算分子,结果属于模数 Q/q 的密文空间。
定理 3.2
设 q ∣ Q q|Q q ∣ Q 为两个整数。设 c t ∈ R Q 2 \mathsf{ct} \in R_Q^2 ct ∈ R Q 2 ,秘密密钥 s k = ( 1 , s ) ∈ R 2 \mathsf{sk} = (1, s) \in R^2 sk = ( 1 , s ) ∈ R 2 的 s s s 具有汉明权重 h h h 。
设 m = [ c t ⋅ s k ] Q ∈ R m = [\mathsf{ct} \cdot \mathsf{sk}]_Q \in R m = [ ct ⋅ sk ] Q ∈ R ,并写 m = m ^ ⋅ q + m ˇ m = \hat{m} \cdot q + \check{m} m = m ^ ⋅ q + m ˇ ,其中 m ˇ = [ m ] q ∈ R \check{m} = [m]_q \in R m ˇ = [ m ] q ∈ R 且 m ^ = ( m − [ m ] q ) / q ∈ R \hat{m} = (m - [m]_q)/q \in R m ^ = ( m − [ m ] q ) / q ∈ R 。
我们有:
Q u o q ( c t ) ⋅ s k = m ^ + I ( m o d Q / q ) , R e m q ( c t ) ⋅ s k = m ˇ − q I ,
\begin{array}{llc}
\mathsf{Quo}_q(\mathsf{ct}) \cdot \mathsf{sk} & = & \hat{m} + I \pmod{Q/q}, \\
\mathsf{Rem}_q(\mathsf{ct}) \cdot \mathsf{sk} & = & \check{m} - qI,
\end{array}
Quo q ( ct ) ⋅ sk Rem q ( ct ) ⋅ sk = = m ^ + I ( mod Q / q ) , m ˇ − q I ,
对于某个满足 ∥ I ∥ ∞ ≤ ( h + 2 ) / 2 \|I\|_{\infty} \leq (h+2)/2 ∥ I ∥ ∞ ≤ ( h + 2 ) /2 的 I ∈ R I \in R I ∈ R 。
解释: 这个定理说明 Q u o q ( c t ) Quo_q(ct) Q u o q ( c t ) 和 R e m q ( c t ) Rem_q(ct) R e m q ( c t ) 在解密后,确实近似于明文的商 m ^ \hat{m} m ^ 和余数 m ˇ \check{m} m ˇ 。误差项 I I I 很小,且 m ˇ − q I \check{m} - qI m ˇ − q I 仍然保持了余数的性质。这意味着即使存在一些小的误差,商仍然很小,从而实现了弱形式的同态欧几里得除法。
4.1.3. 对表示 (Pair Representation)
基于同态欧几里得除法,可以定义密文的对表示。
定义 3.3
设 Q ℓ Q_{\ell} Q ℓ 为模数链中的一个元素(参见 Section 2),设 q d i v ≥ 2 q_{\mathrm{div}} \ge 2 q div ≥ 2 为一个整数。设 c t ∈ R Q ℓ ′ 2 \mathsf{ct} \in R_{Q_{\ell}'}^2 ct ∈ R Q ℓ ′ 2 为一个密文,其中 Q ℓ ′ = Q ℓ ⋅ q d i v Q_{\ell}' = Q_{\ell} \cdot q_{\mathrm{div}} Q ℓ ′ = Q ℓ ⋅ q div 。
c t \mathsf{ct} ct 的分解定义为:
D C P q d i v ( c t ) = ( Q u o q d i v ( c t ) , R e m q d i v ( c t ) ) ∈ R Q ℓ 2 × R Q ℓ 2
\mathsf{DCP}_{q_{\mathrm{div}}}(\mathsf{ct}) = \left(\mathsf{Quo}_{q_{\mathrm{div}}}(\mathsf{ct}), \mathsf{Rem}_{q_{\mathrm{div}}}(\mathsf{ct})\right) \in R_{Q_{\ell}}^2 \times R_{Q_{\ell}}^2
DCP q div ( ct ) = ( Quo q div ( ct ) , Rem q div ( ct ) ) ∈ R Q ℓ 2 × R Q ℓ 2
相反,对于 ( c t ^ , c t ˇ ) ∈ R Q ℓ 2 × R Q ℓ 2 (\hat{\mathrm{ct}}, \check{\mathrm{ct}}) \in R_{Q_{\ell}}^2 \times R_{Q_{\ell}}^2 ( ct ^ , ct ˇ ) ∈ R Q ℓ 2 × R Q ℓ 2 的重组定义为:
R C B q d i v ( c t ^ , c t ˇ ) = q d i v ⋅ c t ^ + c t ˇ ∈ R Q ℓ 2
\mathsf{RCB}_{q_{\mathrm{div}}}(\hat{\mathrm{ct}}, \check{\mathrm{ct}}) = q_{\mathrm{div}} \cdot \hat{\mathrm{ct}} + \check{\mathrm{ct}} \in R_{Q_{\ell}}^2
RCB q div ( ct ^ , ct ˇ ) = q div ⋅ ct ^ + ct ˇ ∈ R Q ℓ 2
解释: DCP(Decomposition of Ciphertext Pair)将一个密文分解为一个商部分 c t ^ \hat{\mathrm{ct}} ct ^ 和一个余数部分 c t ˇ \check{\mathrm{ct}} ct ˇ 。RCB(Recombination of Ciphertext Pair)则将这两个部分重新组合回一个标准密文。这样,一个密文被逻辑上分解为一对,允许进行双精度算术。
引理 3.4
对于一个密文对 ( c t ^ , c t ˇ ) (\hat{\mathrm{ct}}, \check{\mathrm{ct}}) ( ct ^ , ct ˇ ) 和一个秘密密钥 s k ∈ R 2 \mathsf{sk} \in R^2 sk ∈ R 2 ,在模 Q ℓ Q_{\ell} Q ℓ 下,我们有:
R C B q d i v ( c t ^ , c t ˇ ) ⋅ s k = ( c t ^ ⋅ s k ) ⋅ q d i v + ( c t ˇ ⋅ s k )
\mathsf{RCB}_{q_{\mathrm{div}}}(\hat{\mathrm{ct}}, \check{\mathrm{ct}}) \cdot \mathsf{sk} = (\hat{\mathrm{ct}} \cdot \mathsf{sk}) \cdot q_{\mathrm{div}} + (\check{\mathrm{ct}} \cdot \mathsf{sk})
RCB q div ( ct ^ , ct ˇ ) ⋅ sk = ( ct ^ ⋅ sk ) ⋅ q div + ( ct ˇ ⋅ sk )
解释: 这个引理表明,RCB 操作在密文层面的组合,在解密后也对应着明文层面的基于 q d i v q_{\mathrm{div}} q div 的组合。
4.1.4. 元组表示 (Tuple Representation)
对表示可以进一步扩展到元组表示,将密文分解为 t t t 个组件。
定义 3.5
设 t ≥ 2 t \ge 2 t ≥ 2 为元组长度。设 Q ℓ Q_{\ell} Q ℓ 为模数链中的一个元素,设 q d i v ≥ 2 q_{\mathrm{div}} \ge 2 q div ≥ 2 为一个整数,e ≥ 1 e \ge 1 e ≥ 1 。设 c t ∈ R Q ℓ ′ 2 \mathsf{ct} \in R_{Q_{\ell}'}^2 ct ∈ R Q ℓ ′ 2 为一个密文,其中 Q ℓ ′ = Q ℓ ⋅ q d i v e − 1 Q_{\ell}' = Q_{\ell} \cdot q_{\mathrm{div}}^{e-1} Q ℓ ′ = Q ℓ ⋅ q div e − 1 。
定义如下:
( c t ^ 0 , c t ˇ 0 ) = D C P q d i v e − 1 ( c t ) , ( c t ^ i , c t ˇ i ) = D C P q d i v e − i − 1 ( c t ˇ i − 1 ) for 1 ≤ i ≤ e − 2.
\begin{array}{rcl}
(\hat{\mathrm{ct}}_0, \check{\mathrm{ct}}_0) & = & \mathsf{DCP}_{q_{\mathrm{div}}^{e-1}}(\mathsf{ct}), \\
(\hat{\mathrm{ct}}_i, \check{\mathrm{ct}}_i) & = & \mathsf{DCP}_{q_{\mathrm{div}}^{e-i-1}}(\check{\mathrm{ct}}_{i-1}) \quad \text{for } 1 \leq i \leq e-2.
\end{array}
( ct ^ 0 , ct ˇ 0 ) ( ct ^ i , ct ˇ i ) = = DCP q div e − 1 ( ct ) , DCP q div e − i − 1 ( ct ˇ i − 1 ) for 1 ≤ i ≤ e − 2.
为方便起见,定义 c t ^ e − 1 = c t ˇ e − 2 \hat{\mathrm{ct}}_{e-1} = \check{\mathrm{ct}}_{e-2} ct ^ e − 1 = ct ˇ e − 2 。c t \mathsf{ct} ct 的分解为:
D C P q d i v e ( c t ) = ( c t ^ 0 , … , c t ^ e − 2 , c t ^ e − 1 ) ∈ ( R Q ℓ 2 ) e
\mathsf{DCP}_{q_{\mathrm{div}}}^e(\mathsf{ct}) = \left(\hat{\mathrm{ct}}_0, \ldots, \hat{\mathrm{ct}}_{e-2}, \hat{\mathrm{ct}}_{e-1}\right) \in \left(R_{Q_{\ell}}^2\right)^e
DCP q div e ( ct ) = ( ct ^ 0 , … , ct ^ e − 2 , ct ^ e − 1 ) ∈ ( R Q ℓ 2 ) e
相反,( c t ^ 0 , … , c t ^ e − 1 ) ∈ ( R Q ℓ 2 ) e (\hat{\mathrm{ct}}_0, \dots, \hat{\mathrm{ct}}_{e-1}) \in (R_{Q_{\ell}}^2)^e ( ct ^ 0 , … , ct ^ e − 1 ) ∈ ( R Q ℓ 2 ) e 的重组为:
R C B q d i v e ( c t ^ 0 , … , c t ^ e − 2 , c t ^ e − 1 ) = c t ^ 0 ⋅ q d i v e − 1 + … + c t ^ e − 2 ⋅ q d i v + c t ^ e − 1 ∈ R Q ℓ 2 .
\begin{array}{rl}
& \mathsf{RCB}_{q_{\mathrm{div}}}^e(\hat{\mathrm{ct}}_0, \ldots, \hat{\mathrm{ct}}_{e-2}, \hat{\mathrm{ct}}_{e-1}) \\
& \qquad = \hat{\mathrm{ct}}_0 \cdot q_{\mathrm{div}}^{e-1} + \ldots + \hat{\mathrm{ct}}_{e-2} \cdot q_{\mathrm{div}} + \hat{\mathrm{ct}}_{e-1} \in R_{Q_{\ell}}^2.
\end{array}
RCB q div e ( ct ^ 0 , … , ct ^ e − 2 , ct ^ e − 1 ) = ct ^ 0 ⋅ q div e − 1 + … + ct ^ e − 2 ⋅ q div + ct ^ e − 1 ∈ R Q ℓ 2 .
解释: 元组表示将一个密文分解为 e e e 个(文中用 t t t 代表 tuple length)部分,每一部分都是一个标准 CKKS 密文。这使得可以进行更精细的多精度算术。
4.2. 核心方法详解:同态双精度乘法 (M u l t 2 Mult^2 M u l t 2 )
本节将详细描述 M u l t 2 Mult^2 M u l t 2 算法,它是 M u l t t Mult^t M u l t t 中 t = 2 t=2 t = 2 的特例。它通过改造 CKKS 乘法的三个核心步骤(Tensor、Relin 和 RS)来实现。
4.2.1. 张量积 (T e n s o r 2 Tensor^2 T e n so r 2 )
定义 4.1(对张量积)
设 C T 1 = ( c t ^ 1 , c t ˇ 1 ) \mathsf{CT}_1 = (\hat{\mathrm{ct}}_1, \check{\mathrm{ct}}_1) CT 1 = ( ct ^ 1 , ct ˇ 1 ) , C T 2 = ( c t ^ 2 , c t ˇ 2 ) ∈ R Q ℓ 2 × R Q ℓ 2 \mathsf{CT}_2 = (\hat{\mathrm{ct}}_2, \check{\mathrm{ct}}_2) \in R_{Q_{\ell}}^2 \times R_{Q_{\ell}}^2 CT 2 = ( ct ^ 2 , ct ˇ 2 ) ∈ R Q ℓ 2 × R Q ℓ 2 是密文对。
C T 1 \mathsf{CT}_1 CT 1 和 C T 2 \mathsf{CT}_2 CT 2 的张量积定义为:
C T 1 ⊗ 2 C T 2 = ( c t ^ 1 ⊗ c t ^ 2 , c t ^ 1 ⊗ c t ˇ 2 + c t ˇ 1 ⊗ c t ^ 2 ) ∈ R Q ℓ 3 × R Q ℓ 3
\mathsf{CT}_1 \otimes^2 \mathsf{CT}_2 = \left(\hat{\mathrm{ct}}_1 \otimes \hat{\mathrm{ct}}_2, \hat{\mathrm{ct}}_1 \otimes \check{\mathrm{ct}}_2 + \check{\mathrm{ct}}_1 \otimes \hat{\mathrm{ct}}_2\right) \in R_{Q_{\ell}}^3 \times R_{Q_{\ell}}^3
CT 1 ⊗ 2 CT 2 = ( ct ^ 1 ⊗ ct ^ 2 , ct ^ 1 ⊗ ct ˇ 2 + ct ˇ 1 ⊗ ct ^ 2 ) ∈ R Q ℓ 3 × R Q ℓ 3
解释: T e n s o r 2 Tensor^2 T e n so r 2 相当于执行了明文乘法中 m 1 m 2 = 2 2 k m ^ 1 m ^ 2 + 2 k ( m ^ 1 m ˇ 2 + m ˇ 1 m ^ 2 ) + m ˇ 1 m ˇ 2 m_1 m_2 = 2^{2k} \hat{m}_1 \hat{m}_2 + 2^k (\hat{m}_1 \check{m}_2 + \check{m}_1 \hat{m}_2) + \check{m}_1 \check{m}_2 m 1 m 2 = 2 2 k m ^ 1 m ^ 2 + 2 k ( m ^ 1 m ˇ 2 + m ˇ 1 m ^ 2 ) + m ˇ 1 m ˇ 2 的前两项,即 m ^ 1 m ^ 2 \hat{m}_1 \hat{m}_2 m ^ 1 m ^ 2 和 m ^ 1 m ˇ 2 + m ˇ 1 m ^ 2 \hat{m}_1 \check{m}_2 + \check{m}_1 \hat{m}_2 m ^ 1 m ˇ 2 + m ˇ 1 m ^ 2 。它舍弃了 c t ˇ 1 ⊗ c t ˇ 2 \check{\mathrm{ct}}_1 \otimes \check{\mathrm{ct}}_2 ct ˇ 1 ⊗ ct ˇ 2 这一项,因为对于所需的近似精度,这项贡献很小。这是节省模数消耗的关键点,但也引入了新的数值误差。
引理 4.2
设 C T i = ( c t ^ i , c t ˇ i ) ∈ R Q ℓ 2 × R Q ℓ 2 \mathsf{CT}_i = (\hat{\mathrm{ct}}_i, \check{\mathrm{ct}}_i) \in R_{Q_{\ell}}^2 \times R_{Q_{\ell}}^2 CT i = ( ct ^ i , ct ˇ i ) ∈ R Q ℓ 2 × R Q ℓ 2 是密文对,且 R C B q d i v ( C T i ) = c t i \mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{CT}_i) = \mathsf{ct}_i RCB q div ( CT i ) = ct i 对于 i ∈ { 1 , 2 } i \in \{1, 2\} i ∈ { 1 , 2 } 。设 s k = ( 1 , s ) ∈ R 2 \mathsf{sk} = (1, s) \in R^2 sk = ( 1 , s ) ∈ R 2 是一个秘密密钥。那么,在模 Q ℓ Q_{\ell} Q ℓ 下:
( c t 1 ⊗ c t 2 ) ⋅ ( 1 , s , s 2 ) = q d i v ⋅ ( R C B q d i v ( C T 1 ⊗ 2 C T 2 ) ) ⋅ ( 1 , s , s 2 ) + ( c t ˇ 1 ⋅ s k ) ⋅ ( c t ˇ 2 ⋅ s k ) .
(\mathsf{ct}_1 \otimes \mathsf{ct}_2) \cdot (1, s, s^2) = q_{\mathrm{div}} \cdot (\mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{CT}_1 \otimes^2 \mathsf{CT}_2)) \cdot (1, s, s^2) + (\check{\mathrm{ct}}_1 \cdot \mathsf{sk}) \cdot (\check{\mathrm{ct}}_2 \cdot \mathsf{sk}).
( ct 1 ⊗ ct 2 ) ⋅ ( 1 , s , s 2 ) = q div ⋅ ( RCB q div ( CT 1 ⊗ 2 CT 2 )) ⋅ ( 1 , s , s 2 ) + ( ct ˇ 1 ⋅ sk ) ⋅ ( ct ˇ 2 ⋅ sk ) .
现在,假设 ∥ D e c ( c t ^ i ) ∥ ∞ ≤ M ^ \| \mathsf{Dec}(\hat{\mathrm{ct}}_i) \|_{\infty} \leq \hat{M} ∥ Dec ( ct ^ i ) ∥ ∞ ≤ M ^ 且 ∥ D e c ( c t ˇ i ) ∥ ∞ ≤ M ˇ \| \mathsf{Dec}(\check{\mathrm{ct}}_i) \|_{\infty} \leq \check{M} ∥ Dec ( ct ˇ i ) ∥ ∞ ≤ M ˇ 对于所有 i ∈ { 1 , 2 } i \in \{1, 2\} i ∈ { 1 , 2 } 以及某个满足 N ( M ^ q d i v + M ˇ ) 2 < Q ℓ / 2 N(\hat{M}q_{\mathrm{div}} + \check{M})^2 < Q_{\ell}/2 N ( M ^ q div + M ˇ ) 2 < Q ℓ /2 的 M ^ , M ˇ \hat{M}, \check{M} M ^ , M ˇ 。那么我们有:
∥ [ ( R C B q d i v ( C T 1 ⊗ 2 C T 2 ) ) ⋅ ( 1 , s , s 2 ) ] Q ℓ − 1 q d i v [ ( c t 1 ⊗ c t 2 ) ⋅ ( 1 , s , s 2 ) ] Q ℓ ∥ ∞ ≤ N M ˇ 2 q d i v .
\left\| \left[ (\mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{CT}_1 \otimes^2 \mathsf{CT}_2)) \cdot (1, s, s^2) \right]_{Q_{\ell}} - \frac{1}{q_{\mathrm{div}}} \left[ (\mathsf{ct}_1 \otimes \mathsf{ct}_2) \cdot (1, s, s^2) \right]_{Q_{\ell}} \right\|_{\infty} \leq \frac{N\check{M}^2}{q_{\mathrm{div}}}.
[ ( RCB q div ( CT 1 ⊗ 2 CT 2 )) ⋅ ( 1 , s , s 2 ) ] Q ℓ − q div 1 [ ( ct 1 ⊗ ct 2 ) ⋅ ( 1 , s , s 2 ) ] Q ℓ ∞ ≤ q div N M ˇ 2 .
解释: 这个引理量化了 T e n s o r 2 Tensor^2 T e n so r 2 结果的解密值与原始密文张量积解密值之间的关系。它表明 T e n s o r 2 Tensor^2 T e n so r 2 的结果近似于标准张量积除以 q d i v q_{\mathrm{div}} q div 。关键的误差项来源于被舍弃的 c t ˇ 1 ⊗ c t ˇ 2 \check{\mathrm{ct}}_1 \otimes \check{\mathrm{ct}}_2 ct ˇ 1 ⊗ ct ˇ 2 部分,其上界约为 N M ˇ 2 / q d i v N\check{M}^2/q_{\mathrm{div}} N M ˇ 2 / q div 。这表明 T e n s o r 2 Tensor^2 T e n so r 2 间接实现了 q d i v q_{\mathrm{div}} q div 的重缩放,且不消耗模数。
4.2.2. 重线性化 (R e l i n 2 Relin^2 R e l i n 2 )
定义 4.3(对重线性化)
设 C T = ( c t ^ , c t ˇ ) ∈ R Q ℓ 3 × R Q ℓ 3 \mathsf{CT} = (\hat{\mathrm{ct}}, \check{\mathrm{ct}}) \in R_{Q_{\ell}}^3 \times R_{Q_{\ell}}^3 CT = ( ct ^ , ct ˇ ) ∈ R Q ℓ 3 × R Q ℓ 3 是张量积 T e n s o r 2 Tensor^2 T e n so r 2 的输出。
重线性化操作 R e l i n 2 Relin^2 R e l i n 2 定义为:
R e l i n 2 ( C T ) = D C P q d i v ( R e l i n ( q d i v ⋅ c t ^ ) ) + ( 0 , R e l i n ( c t ˇ ) ) .
\mathsf{Relin}^2(\mathsf{CT}) = \mathsf{DCP}_{q_{\mathrm{div}}}(\mathsf{Relin}(q_{\mathrm{div}} \cdot \hat{\mathrm{ct}})) + (0, \mathsf{Relin}(\check{\mathrm{ct}})).
Relin 2 ( CT ) = DCP q div ( Relin ( q div ⋅ ct ^ )) + ( 0 , Relin ( ct ˇ )) .
解释: R e l i n 2 Relin^2 R e l i n 2 避免了对每个组件独立进行重线性化。如果简单地对 c t ^ \hat{\mathrm{ct}} ct ^ 和 c t ˇ \check{\mathrm{ct}} ct ˇ 分别进行 Relin,则 c t ^ \hat{\mathrm{ct}} ct ^ 中的误差会被 q d i v q_{\mathrm{div}} q div 放大,从而破坏精度。相反,它先对 c t ^ \hat{\mathrm{ct}} ct ^ 乘以 q d i v q_{\mathrm{div}} q div (即“提高模数”),然后进行 Relin 并 DCP 分解,再与 c t ˇ \check{\mathrm{ct}} ct ˇ 的 Relin 结果合并。这样,R e l i n 2 Relin^2 R e l i n 2 不会消耗模数。
引理 4.4
设 C T = ( c t ^ , c t ˇ ) ∈ R Q ℓ 3 × R Q ℓ 3 \mathsf{CT} = (\hat{\mathrm{ct}}, \check{\mathrm{ct}}) \in R_{Q_{\ell}}^3 \times R_{Q_{\ell}}^3 CT = ( ct ^ , ct ˇ ) ∈ R Q ℓ 3 × R Q ℓ 3 且 s k = ( 1 , s ) ∈ R 2 \mathsf{sk} = (1, s) \in R^2 sk = ( 1 , s ) ∈ R 2 是一个秘密密钥,其 s s s 具有汉明权重 h h h 。那么数量
[ ( R C B q d i v ( R e l i n 2 ( C T ) ) ) ⋅ ( 1 , s ) − ( R C B q d i v ( C T ) ) ⋅ ( 1 , s , s 2 ) ] Q ℓ
\left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{Relin}^2(\mathsf{CT})) \right) \cdot (1, s) - \left( \mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{CT}) \right) \cdot (1, s, s^2) \right]_{Q_{\ell}}
[ ( RCB q div ( Relin 2 ( CT )) ) ⋅ ( 1 , s ) − ( RCB q div ( CT ) ) ⋅ ( 1 , s , s 2 ) ] Q ℓ
的无限范数 ∥ ⋅ ∥ ∞ ≤ E R e l i n + h \| \cdot \|_{\infty} \leq E_{\mathrm{Relin}} + h ∥ ⋅ ∥ ∞ ≤ E Relin + h 。现在,假设 ∥ [ R C B q d i v ( C T ) ⋅ ( 1 , s , s 2 ) ] Q ℓ ∥ ∞ ≤ M \| [\mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{CT}) \cdot (1, s, s^2)]_{Q_{\ell}} \|_{\infty} \leq M ∥ [ RCB q div ( CT ) ⋅ ( 1 , s , s 2 ) ] Q ℓ ∥ ∞ ≤ M 且满足 2 ( M + E R e l i n + h ) < Q ℓ / 2 2(M + E_{\mathrm{Relin}} + h) < Q_{\ell}/2 2 ( M + E Relin + h ) < Q ℓ /2 。那么数量
[ ( R C B q d i v ( R e l i n 2 ( C T ) ) ) ⋅ ( 1 , s ) ] Q ℓ − [ ( R C B q d i v ( C T ) ) ⋅ ( 1 , s , s 2 ) ] Q ℓ
\left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{Relin}^2(\mathsf{CT})) \right) \cdot (1, s) \right]_{Q_{\ell}} - \left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{CT}) \right) \cdot (1, s, s^2) \right]_{Q_{\ell}}
[ ( RCB q div ( Relin 2 ( CT )) ) ⋅ ( 1 , s ) ] Q ℓ − [ ( RCB q div ( CT ) ) ⋅ ( 1 , s , s 2 ) ] Q ℓ
的无限范数也 ∥ ⋅ ∥ ∞ ≤ E R e l i n + h \| \cdot \|_{\infty} \leq E_{\mathrm{Relin}} + h ∥ ⋅ ∥ ∞ ≤ E Relin + h 。
解释: 这个引理表明 R e l i n 2 Relin^2 R e l i n 2 操作能够正确地将扩展密钥下的密文转换为秘密密钥下的密文,并且引入的误差与标准 Relin 误差 E R e l i n E_{\mathrm{Relin}} E Relin 相当。
4.2.3. 重缩放 (R S 2 RS^2 R S 2 )
定义 4.5(对重缩放)
设 C T = ( c t ^ , c t ˇ ) ∈ R Q ℓ 2 × R Q ℓ 2 \mathsf{CT} = (\hat{\mathrm{ct}}, \check{\mathrm{ct}}) \in R_{Q_{\ell}}^2 \times R_{Q_{\ell}}^2 CT = ( ct ^ , ct ˇ ) ∈ R Q ℓ 2 × R Q ℓ 2 是重线性化 R e l i n 2 Relin^2 R e l i n 2 的输出。设 q ℓ = Q ℓ / Q ℓ − 1 q_{\ell} = Q_{\ell} / Q_{\ell-1} q ℓ = Q ℓ / Q ℓ − 1 。
C T \mathsf{CT} CT 的重缩放 R S 2 RS^2 R S 2 定义为:
R S q ℓ 2 ( C T ) = ( R S q ℓ ( c t ^ ) , R S q ℓ ( q d i v ⋅ c t ^ + c t ˇ ) − q d i v ⋅ R S q ℓ ( c t ^ ) ) .
\mathsf{RS}_{q_{\ell}}^2(\mathsf{CT}) = \left(\mathsf{RS}_{q_{\ell}}(\hat{\mathrm{ct}}), \mathsf{RS}_{q_{\ell}}(q_{\mathrm{div}} \cdot \hat{\mathrm{ct}} + \check{\mathrm{ct}}) - q_{\mathrm{div}} \cdot \mathsf{RS}_{q_{\ell}}(\hat{\mathrm{ct}})\right).
RS q ℓ 2 ( CT ) = ( RS q ℓ ( ct ^ ) , RS q ℓ ( q div ⋅ ct ^ + ct ˇ ) − q div ⋅ RS q ℓ ( ct ^ ) ) .
解释: R S 2 RS^2 R S 2 的设计目标是确保在对密文对进行重缩放时,组合后的明文也能得到正确的重缩放。它利用了等式 R C B q d i v ( R S q ℓ 2 ( C T ) ) = R S q ℓ ( R C B q d i v ( C T ) ) \mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{RS}_{q_{\ell}}^2(\mathsf{CT})) = \mathsf{RS}_{q_{\ell}}(\mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{CT})) RCB q div ( RS q ℓ 2 ( CT )) = RS q ℓ ( RCB q div ( CT )) 。与 R e l i n 2 Relin^2 R e l i n 2 类似,这种设计避免了 D C P ∘ R S ∘ R C B DCP \circ RS \circ RCB D CP ∘ RS ∘ RCB 这种会额外消耗 q d i v q_{\mathrm{div}} q div 模数的“朴素”方法,只消耗了因子 q ℓ q_{\ell} q ℓ 。
引理 4.6
设 C T ∈ ( R Q ℓ 2 ) t \mathsf{CT} \in (R_{Q_{\ell}}^2)^t CT ∈ ( R Q ℓ 2 ) t 是一个密文元组。设 q ℓ = Q ℓ / Q ℓ − 1 q_{\ell} = Q_{\ell}/Q_{\ell-1} q ℓ = Q ℓ / Q ℓ − 1 。设 s k = ( 1 , s ) ∈ R 2 \mathsf{sk} = (1, s) \in R^2 sk = ( 1 , s ) ∈ R 2 是一个秘密密钥,其 s s s 具有汉明权重 h h h 。那么数量
[ ( R C B q d i v ( R S q ℓ 2 ( C T ) ) ) ⋅ ( 1 , s ) ] Q ℓ − 1 − 1 q ℓ [ ( R C B q d i v ( C T ) ) ⋅ ( 1 , s ) ] Q ℓ
\left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{RS}_{q_{\ell}}^2(\mathsf{CT})) \right) \cdot (1, s) \right]_{Q_{\ell-1}} - \frac{1}{q_{\ell}} \left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{CT}) \right) \cdot (1, s) \right]_{Q_{\ell}}
[ ( RCB q div ( RS q ℓ 2 ( CT )) ) ⋅ ( 1 , s ) ] Q ℓ − 1 − q ℓ 1 [ ( RCB q div ( CT ) ) ⋅ ( 1 , s ) ] Q ℓ
的无限范数 ∥ ⋅ ∥ ∞ ≤ ( h + 1 ) / 2 \| \cdot \|_{\infty} \leq (h+1)/2 ∥ ⋅ ∥ ∞ ≤ ( h + 1 ) /2 。
解释: 这个引理确认了 R S 2 RS^2 R S 2 操作在解密层面的正确性,即它能够将组合明文的值近似地除以 q ℓ q_{\ell} q ℓ ,并引入非常小的误差。
4.2.4. 完整的 M u l t 2 Mult^2 M u l t 2 算法
定义 4.7(对乘法)
我们将模 Q ℓ Q_{\ell} Q ℓ 下的密文对乘法定义为 M u l t 2 : = R S q ℓ 2 ∘ R e l i n 2 ∘ T e n s o r 2 Mult^2 := RS_{q_{\ell}}^2 \circ Relin^2 \circ Tensor^2 M u l t 2 := R S q ℓ 2 ∘ R e l i n 2 ∘ T e n so r 2 ,其中 q ℓ = Q ℓ / Q ℓ − 1 q_{\ell} = Q_{\ell} / Q_{\ell-1} q ℓ = Q ℓ / Q ℓ − 1 。结果是一个模 Q ℓ − 1 Q_{\ell-1} Q ℓ − 1 下的密文对。
定理 4.8
设 C T 1 = ( c t ^ 1 , c t ˇ 1 ) , C T 2 = ( c t ^ 2 , c t ˇ 2 ) ∈ R Q ℓ 2 × R Q ℓ 2 \mathsf{CT}_1 = (\hat{\mathrm{ct}}_1, \check{\mathrm{ct}}_1), \mathsf{CT}_2 = (\hat{\mathrm{ct}}_2, \check{\mathrm{ct}}_2) \in R_{Q_{\ell}}^2 \times R_{Q_{\ell}}^2 CT 1 = ( ct ^ 1 , ct ˇ 1 ) , CT 2 = ( ct ^ 2 , ct ˇ 2 ) ∈ R Q ℓ 2 × R Q ℓ 2 是密文对。设 q ℓ = Q ℓ / Q ℓ − 1 q_{\ell} = Q_{\ell} / Q_{\ell-1} q ℓ = Q ℓ / Q ℓ − 1 ,秘密密钥 s k = ( 1 , s ) ∈ R 2 \mathsf{sk} = (1, s) \in R^2 sk = ( 1 , s ) ∈ R 2 的 s s s 具有汉明权重 h h h 。假设 ∥ D e c ( c t ^ i ) ∥ ∞ ≤ M ^ \| \mathsf{Dec}(\hat{\mathrm{ct}}_i) \|_{\infty} \leq \hat{M} ∥ Dec ( ct ^ i ) ∥ ∞ ≤ M ^ 且 ∥ D e c ( c t ˇ i ) ∥ ∞ ≤ M ˇ \| \mathsf{Dec}(\check{\mathrm{ct}}_i) \|_{\infty} \leq \check{M} ∥ Dec ( ct ˇ i ) ∥ ∞ ≤ M ˇ 对于所有 i ∈ { 1 , 2 } i \in \{1, 2\} i ∈ { 1 , 2 } 以及某个满足 N ( M ^ q d i v + M ˇ ) 2 + E R e l i n + h < Q ℓ / 2 N(\hat{M}q_{\mathrm{div}} + \check{M})^2 + E_{\mathrm{Relin}} + h < Q_{\ell}/2 N ( M ^ q div + M ˇ ) 2 + E Relin + h < Q ℓ /2 的 M ^ , M ˇ \hat{M}, \check{M} M ^ , M ˇ 。那么
[ ( R C B q d i v ( M u l t 2 ( C T 1 , C T 2 ) ) ) ⋅ s k ] Q ℓ − 1 − 1 q ℓ [ ( R C B q d i v ( C T 1 ) ⋅ s k ) ⋅ ( R C B q d i v ( C T 2 ) ⋅ s k ) ] Q ℓ
\left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{Mult}^2(\mathsf{CT}_1, \mathsf{CT}_2)) \right) \cdot \mathsf{sk} \right]_{Q_{\ell-1}} - \frac{1}{q_{\ell}} \left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{CT}_1) \cdot \mathsf{sk} \right) \cdot \left( \mathsf{RCB}_{q_{\mathrm{div}}}(\mathsf{CT}_2) \cdot \mathsf{sk} \right) \right]_{Q_{\ell}}
[ ( RCB q div ( Mult 2 ( CT 1 , CT 2 )) ) ⋅ sk ] Q ℓ − 1 − q ℓ 1 [ ( RCB q div ( CT 1 ) ⋅ sk ) ⋅ ( RCB q div ( CT 2 ) ⋅ sk ) ] Q ℓ
的无限范数 ≤ ( N M ˇ 2 / q d i v + E R e l i n + h ) / q ℓ + ( h + 1 ) / 2 \leq (N\check{M}^2/q_{\mathrm{div}} + E_{\mathrm{Relin}} + h)/q_{\ell} + (h+1)/2 ≤ ( N M ˇ 2 / q div + E Relin + h ) / q ℓ + ( h + 1 ) /2 。
解释: 这个定理总结了 M u l t 2 Mult^2 M u l t 2 乘法相对于理想乘法结果的总体误差。误差的主要来源是 T e n s o r 2 Tensor^2 T e n so r 2 中舍弃的低位项(由 N M ˇ 2 / ( q d i v q ℓ ) N\check{M}^2/(q_{\mathrm{div}}q_{\ell}) N M ˇ 2 / ( q div q ℓ ) 项代表),以及重线性化和重缩放的固有误差。这个结果展示了 M u l t 2 Mult^2 M u l t 2 的正确性,并强调了 M ˇ \check{M} M ˇ (低位部分的范数)对误差增长的关键影响。
4.2.5. 效率分析
M u l t 2 Mult^2 M u l t 2 需要调用 3 次 Tensor、2 次 Relin 和 2 次 RS。由于 Relin 和 RS 涉及 NTT (Number Theoretic Transforms),其计算成本远高于 Tensor。虽然看起来 M u l t 2 Mult^2 M u l t 2 的操作次数多于标准 CKKS 乘法(1 Tensor、1 Relin、1 RS),但由于 M u l t 2 Mult^2 M u l t 2 模数消耗更低,这意味着在相同计算深度下可以使用更小的模数,甚至可以降低环维度 N N N (在保持相同安全级别的前提下)。因此,M u l t 2 Mult^2 M u l t 2 的总成本与标准 Mult 相似,甚至在延迟和密文大小方面更优。在切换密钥大小方面,M u l t 2 Mult^2 M u l t 2 可以实现约 2 倍的优势。
4.3. 低位部分 (c h e c k M check_M c h ec k M ) 的边界控制
在 M u l t 2 Mult^2 M u l t 2 中,低位部分 c t ˇ \check{\mathrm{ct}} ct ˇ 的解密值范数 M ˇ \check{M} M ˇ 的增长会显著影响乘法的误差。
定理 4.9(低位部分的增长)
设 C T 1 = ( c t ^ 1 , c t ˇ 1 ) \mathsf{CT}_1 = (\hat{\mathrm{ct}}_1, \check{\mathrm{ct}}_1) CT 1 = ( ct ^ 1 , ct ˇ 1 ) 和 C T 2 = ( c t ^ 2 , c t ˇ 2 ) ∈ R Q ℓ 2 × R Q ℓ 2 \mathsf{CT}_2 = (\hat{\mathrm{ct}}_2, \check{\mathrm{ct}}_2) \in R_{Q_{\ell}}^2 \times R_{Q_{\ell}}^2 CT 2 = ( ct ^ 2 , ct ˇ 2 ) ∈ R Q ℓ 2 × R Q ℓ 2 是密文对。设 q ℓ = Q ℓ / Q ℓ − 1 ≥ 2 q_{\ell} = Q_{\ell} / Q_{\ell-1} \ge 2 q ℓ = Q ℓ / Q ℓ − 1 ≥ 2 ,秘密密钥 s k = ( 1 , s ) ∈ R 2 \mathsf{sk} = (1, s) \in R^2 sk = ( 1 , s ) ∈ R 2 的 s s s 具有汉明权重 h h h 。假设 ∥ c a n ∘ D e c ( c t ^ i ) ∥ ∞ ≤ M ^ \| \mathsf{can} \circ \mathsf{Dec}(\hat{\mathrm{ct}}_i) \|_{\infty} \leq \hat{M} ∥ can ∘ Dec ( ct ^ i ) ∥ ∞ ≤ M ^ 且 ∥ c a n ∘ D e c ( c t ˇ i ) ∥ ∞ < M ˇ \| \mathsf{can} \circ \mathsf{Dec}(\check{\mathrm{ct}}_i) \|_{\infty} < \check{M} ∥ can ∘ Dec ( ct ˇ i ) ∥ ∞ < M ˇ 对于 i ∈ { 1 , 2 } i \in \{1, 2\} i ∈ { 1 , 2 } 以及某些 M ^ , M ˇ \hat{M}, \check{M} M ^ , M ˇ 。设 C T M u l t = M u l t 2 ( C T 1 , C T 2 ) = ( c t ^ M u l t , c t ˇ M u l t ) \mathsf{CT}_{\mathrm{Mult}} = \mathsf{Mult}^2(\mathsf{CT}_1, \mathsf{CT}_2) = (\hat{\mathrm{ct}}_{\mathrm{Mult}}, \check{\mathrm{ct}}_{\mathrm{Mult}}) CT Mult = Mult 2 ( CT 1 , CT 2 ) = ( ct ^ Mult , ct ˇ Mult ) 。那么以下成立:
∥ c a n ∘ D e c ( c t ˇ M u l t ) ∥ ∞ ≤ 2 M ^ M ˇ q ℓ + N ( E R e l i n q ℓ + ( h + 3 ) ( q d i v + 1 ) ) .
\| \mathsf{can} \circ \mathsf{Dec}(\check{\mathrm{ct}}_{\mathrm{Mult}}) \|_{\infty} \leq \frac{2\hat{M}\check{M}}{q_{\ell}} + N \left( \frac{E_{\mathrm{Relin}}}{q_{\ell}} + (h+3)(q_{\mathrm{div}}+1) \right).
∥ can ∘ Dec ( ct ˇ Mult ) ∥ ∞ ≤ q ℓ 2 M ^ M ˇ + N ( q ℓ E Relin + ( h + 3 ) ( q div + 1 ) ) .
解释: 这个定理分析了每次 M u l t 2 Mult^2 M u l t 2 乘法后低位部分 c t ˇ \check{\mathrm{ct}} ct ˇ 的范数增长。上界的主要项是 2 M ^ M ˇ / q ℓ 2\hat{M}\check{M}/q_{\ell} 2 M ^ M ˇ / q ℓ ,它与 M ˇ \check{M} M ˇ 成正比。如果将 M ^ \hat{M} M ^ 设为 Δ / q d i v \Delta/q_{\mathrm{div}} Δ/ q div 且 Δ ≈ q ℓ 2 \Delta \approx q_{\ell}^2 Δ ≈ q ℓ 2 ,那么这个主要项大约是 2 M ˇ 2\check{M} 2 M ˇ 。这意味着低位部分的范数在每次乘法后大约增长 1 比特。为了控制这个增长,可以周期性地执行“重组-分解” (recombine-and-decompose) 操作,即将当前的密文对 ( c t ^ , c t ˇ ) (\hat{\mathrm{ct}}, \check{\mathrm{ct}}) ( ct ^ , ct ˇ ) 通过 RCB 合并回一个普通密文,然后再通过 DCP 重新分解,使得新的 c t ˇ \check{\mathrm{ct}} ct ˇ 回到初始的小范数值。
4.4. 同态多精度乘法 (M u l t t Mult^t M u l t t )
M u l t t Mult^t M u l t t 是 M u l t 2 Mult^2 M u l t 2 的泛化,将密文分解为 t t t 个组件。
4.4.1. 元组张量积 (T e n s o r t Tensor^t T e n so r t )
定义 5.1(元组张量积)
设 C T 1 = ( c t ^ 1 , 0 , ⋯ , c t ^ 1 , t − 1 ) \mathsf{CT}_1 = (\hat{\mathrm{ct}}_{1,0}, \cdots, \hat{\mathrm{ct}}_{1,t-1}) CT 1 = ( ct ^ 1 , 0 , ⋯ , ct ^ 1 , t − 1 ) , C T 2 = ( c t ^ 2 , 0 , ⋯ , c t ^ 2 , t − 1 ) ∈ ( R Q ℓ 2 ) t \mathsf{CT}_2 = (\hat{\mathrm{ct}}_{2,0}, \cdots, \hat{\mathrm{ct}}_{2,t-1}) \in (R_{Q_{\ell}}^2)^t CT 2 = ( ct ^ 2 , 0 , ⋯ , ct ^ 2 , t − 1 ) ∈ ( R Q ℓ 2 ) t 是密文元组。
C T 1 \mathsf{CT}_1 CT 1 和 C T 2 \mathsf{CT}_2 CT 2 的张量积定义为:
c t ^ t e n , i = ∑ j = 0 i c t ^ 1 , j ⊗ c t ^ 2 , i − j , for all i ∈ { 0 , ⋯ , t − 1 }
\hat{\mathrm{ct}}_{\mathrm{ten},i} = \sum_{j=0}^{i} \hat{\mathrm{ct}}_{1,j} \otimes \hat{\mathrm{ct}}_{2,i-j}, \text{ for all } i \in \{0, \cdots, t-1\}
ct ^ ten , i = j = 0 ∑ i ct ^ 1 , j ⊗ ct ^ 2 , i − j , for all i ∈ { 0 , ⋯ , t − 1 }
解释: T e n s o r t Tensor^t T e n so r t 考虑了 t t t 个组件的乘积,并仅保留了前 t t t 个有效项,即舍弃了所有 i ≥ t i \ge t i ≥ t 的高次项。这进一步减少了模数消耗。
引理 5.2
设 C T i = ( c t ^ i , 0 , ⋯ , c t ^ i , t − 1 ) ∈ ( R Q ℓ 2 ) t \mathsf{CT}_i = (\hat{\mathrm{ct}}_{i,0}, \cdots, \hat{\mathrm{ct}}_{i,t-1}) \in (R_{Q_{\ell}}^2)^t CT i = ( ct ^ i , 0 , ⋯ , ct ^ i , t − 1 ) ∈ ( R Q ℓ 2 ) t 是密文元组,满足 R C B q d i v t ( C T i ) = c t i \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{CT}_i) = \mathsf{ct}_i RCB q div t ( CT i ) = ct i 对于 i ∈ { 1 , 2 } i \in \{1, 2\} i ∈ { 1 , 2 } 。设 s k = ( 1 , s ) ∈ R 2 \mathsf{sk} = (1, s) \in R^2 sk = ( 1 , s ) ∈ R 2 是一个秘密密钥。那么,在模 Q ℓ Q_{\ell} Q ℓ 下:
( c t 1 ⊗ c t 2 ) ⋅ ( 1 , s , s 2 ) = q d i v t − 1 ⋅ ( R C B q d i v t ( C T 1 ⊗ t C T 2 ) ) ⋅ ( 1 , s , s 2 ) + ∑ i = 1 t − 1 ∑ j = i t − 1 q d i v t − 1 − i ( c t ^ 1 , j ⋅ s k ) ⋅ ( c t ^ 2 , t − 1 − j ⋅ s k ) .
(\mathsf{ct}_1 \otimes \mathsf{ct}_2) \cdot (1, s, s^2) = q_{\mathrm{div}}^{t-1} \cdot (\mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{CT}_1 \otimes^t \mathsf{CT}_2)) \cdot (1, s, s^2) + \sum_{i=1}^{t-1} \sum_{j=i}^{t-1} q_{\mathrm{div}}^{t-1-i} (\hat{\mathrm{ct}}_{1,j} \cdot \mathsf{sk}) \cdot (\hat{\mathrm{ct}}_{2,t-1-j} \cdot \mathsf{sk}).
( ct 1 ⊗ ct 2 ) ⋅ ( 1 , s , s 2 ) = q div t − 1 ⋅ ( RCB q div t ( CT 1 ⊗ t CT 2 )) ⋅ ( 1 , s , s 2 ) + i = 1 ∑ t − 1 j = i ∑ t − 1 q div t − 1 − i ( ct ^ 1 , j ⋅ sk ) ⋅ ( ct ^ 2 , t − 1 − j ⋅ sk ) .
现在,假设 ∥ D e c ( c t ^ i , 0 ) ∥ ≤ M ^ \| \mathsf{Dec}(\hat{\mathrm{ct}}_{i,0}) \| \leq \hat{M} ∥ Dec ( ct ^ i , 0 ) ∥ ≤ M ^ 且 ∥ D e c ( c t ^ i , j ) ∥ ≤ M ˇ \| \mathsf{Dec}(\hat{\mathrm{ct}}_{i,j}) \| \leq \check{M} ∥ Dec ( ct ^ i , j ) ∥ ≤ M ˇ 对于所有 i ∈ { 1 , 2 } , j ∈ { 1 , ⋯ , t − 1 } i \in \{1, 2\}, j \in \{1, \cdots, t-1\} i ∈ { 1 , 2 } , j ∈ { 1 , ⋯ , t − 1 } 以及某个满足 N ( M ^ q d i v t − 1 + M ˇ q d i v t − 2 + ⋯ + M ˇ ) 2 < Q ℓ / 2 N(\hat{M}q_{\mathrm{div}}^{t-1} + \check{M}q_{\mathrm{div}}^{t-2} + \cdots + \check{M})^2 < Q_{\ell}/2 N ( M ^ q div t − 1 + M ˇ q div t − 2 + ⋯ + M ˇ ) 2 < Q ℓ /2 的 M ^ , M ˇ \hat{M}, \check{M} M ^ , M ˇ 。那么我们有:
∥ [ R C B q d i v t ( C T 1 ⊗ t C T 2 ) ⋅ ( 1 , s , s 2 ) ] Q ℓ − 1 q d i v t − 1 [ ( c t 1 ⊗ c t 2 ) ⋅ ( 1 , s , s 2 ) ] Q ℓ ∥ ∞ ≤ ∑ i = 1 t − 1 ( t − i ) N M ˇ 2 q d i v i .
\left\| \left[ \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{CT}_1 \otimes^t \mathsf{CT}_2) \cdot (1, s, s^2) \right]_{Q_{\ell}} - \frac{1}{q_{\mathrm{div}}^{t-1}} \left[ (\mathsf{ct}_1 \otimes \mathsf{ct}_2) \cdot (1, s, s^2) \right]_{Q_{\ell}} \right\|_{\infty} \leq \sum_{i=1}^{t-1} \frac{(t-i)N\check{M}^2}{q_{\mathrm{div}}^i}.
[ RCB q div t ( CT 1 ⊗ t CT 2 ) ⋅ ( 1 , s , s 2 ) ] Q ℓ − q div t − 1 1 [ ( ct 1 ⊗ ct 2 ) ⋅ ( 1 , s , s 2 ) ] Q ℓ ∞ ≤ i = 1 ∑ t − 1 q div i ( t − i ) N M ˇ 2 .
解释: 这个引理表明 T e n s o r t Tensor^t T e n so r t 的结果近似于标准张量积除以 q d i v t − 1 q_{\mathrm{div}}^{t-1} q div t − 1 。误差项更复杂,但同样与 M ˇ \check{M} M ˇ 和 t t t 相关。
4.4.2. 元组重线性化 (R e l i n t Relin^t R e l i n t )
定义 5.3(元组重线性化)
设 C T = ( c t ^ 0 , ⋯ , c t ^ t − 1 ) ∈ ( R Q ℓ 3 ) t \mathsf{CT} = (\hat{\mathrm{ct}}_0, \cdots, \hat{\mathrm{ct}}_{t-1}) \in (R_{Q_{\ell}}^3)^t CT = ( ct ^ 0 , ⋯ , ct ^ t − 1 ) ∈ ( R Q ℓ 3 ) t 是 T e n s o r t Tensor^t T e n so r t 的输出。R e l i n t Relin^t R e l i n t 递归定义为:
R e l i n t ( C T ) = D C P q d i v t ( R e l i n ( q d i v t − 1 ⋅ c t ^ 0 ) ) + ( 0 , R e l i n t − 1 ( C T ‾ ) ) ,
\mathsf{Relin}^t(\mathsf{CT}) = \mathsf{DCP}_{q_{\mathrm{div}}}^t(\mathsf{Relin}(q_{\mathrm{div}}^{t-1} \cdot \hat{\mathrm{ct}}_0)) + (0, \mathsf{Relin}^{t-1}(\overline{\mathsf{CT}})),
Relin t ( CT ) = DCP q div t ( Relin ( q div t − 1 ⋅ ct ^ 0 )) + ( 0 , Relin t − 1 ( CT )) ,
其中 C T ‾ = ( c t ^ 1 , ⋯ , c t ^ t − 1 ) ∈ ( R Q ℓ 3 ) t − 1 \overline{\mathsf{CT}} = (\hat{\mathrm{ct}}_1, \cdots, \hat{\mathrm{ct}}_{t-1}) \in (R_{Q_{\ell}}^3)^{t-1} CT = ( ct ^ 1 , ⋯ , ct ^ t − 1 ) ∈ ( R Q ℓ 3 ) t − 1 。
解释: R e l i n t Relin^t R e l i n t 同样通过巧妙的分解和重组,确保重线性化过程的正确性,并避免额外的模数消耗。
引理 5.4
设 C T = ( c t ^ 0 , ⋯ , c t ^ t − 1 ) ∈ ( R Q ℓ 3 ) t \mathsf{CT} = (\hat{\mathrm{ct}}_0, \cdots, \hat{\mathrm{ct}}_{t-1}) \in (R_{Q_{\ell}}^3)^t CT = ( ct ^ 0 , ⋯ , ct ^ t − 1 ) ∈ ( R Q ℓ 3 ) t 是 T e n s o r t Tensor^t T e n so r t 的输出。设 s k = ( 1 , s ) ∈ R 2 \mathsf{sk} = (1, s) \in R^2 sk = ( 1 , s ) ∈ R 2 是一个秘密密钥,其 s s s 具有汉明权重 h h h 。那么数量
[ ( R C B q d i v t ( R e l i n t ( C T ) ) ) ⋅ ( 1 , s ) − ( R C B q d i v t ( C T ) ) ⋅ ( 1 , s , s 2 ) ] Q ℓ
\left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{Relin}^t(\mathsf{CT})) \right) \cdot (1, s) - \left( \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{CT}) \right) \cdot (1, s, s^2) \right]_{Q_{\ell}}
[ ( RCB q div t ( Relin t ( CT )) ) ⋅ ( 1 , s ) − ( RCB q div t ( CT ) ) ⋅ ( 1 , s , s 2 ) ] Q ℓ
的无限范数 ∥ ⋅ ∥ ∞ ≤ E R e l i n + t h / 2 \| \cdot \|_{\infty} \leq E_{\mathrm{Relin}} + th/2 ∥ ⋅ ∥ ∞ ≤ E Relin + t h /2 。现在,假设 ∥ [ R C B q d i v t ( C T ) ⋅ ( 1 , s , s 2 ) ] Q ℓ ∥ ∞ ≤ M \| [\mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{CT}) \cdot (1, s, s^2)]_{Q_{\ell}} \|_{\infty} \leq M ∥ [ RCB q div t ( CT ) ⋅ ( 1 , s , s 2 ) ] Q ℓ ∥ ∞ ≤ M 且满足 2 ( M + E R e l i n + t h / 2 ) < Q ℓ / 2 2(M + E_{\mathrm{Relin}} + th/2) < Q_{\ell}/2 2 ( M + E Relin + t h /2 ) < Q ℓ /2 。那么
[ ( R C B q d i v t ( R e l i n t ( C T ) ) ) ⋅ ( 1 , s ) ] Q ℓ − [ ( R C B q d i v t ( C T ) ) ⋅ ( 1 , s , s 2 ) ] Q ℓ
\left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{Relin}^t(\mathsf{CT})) \right) \cdot (1, s) \right]_{Q_{\ell}} - \left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{CT}) \right) \cdot (1, s, s^2) \right]_{Q_{\ell}}
[ ( RCB q div t ( Relin t ( CT )) ) ⋅ ( 1 , s ) ] Q ℓ − [ ( RCB q div t ( CT ) ) ⋅ ( 1 , s , s 2 ) ] Q ℓ
的无限范数也 ∥ ⋅ ∥ ∞ ≤ E R e l i n + t h / 2 \| \cdot \|_{\infty} \leq E_{\mathrm{Relin}} + th/2 ∥ ⋅ ∥ ∞ ≤ E Relin + t h /2 。
4.4.3. 元组重缩放 (R S t RS^t R S t )
定义 5.5(元组重缩放)
设 C T = ( c t ^ 0 , ⋯ , c t ^ t − 1 ) ∈ ( R Q ℓ 2 ) t \mathsf{CT} = (\hat{\mathrm{ct}}_0, \cdots, \hat{\mathrm{ct}}_{t-1}) \in (R_{Q_{\ell}}^2)^t CT = ( ct ^ 0 , ⋯ , ct ^ t − 1 ) ∈ ( R Q ℓ 2 ) t 是一个密文元组。设 q ℓ = Q ℓ / Q ℓ − 1 q_{\ell} = Q_{\ell} / Q_{\ell-1} q ℓ = Q ℓ / Q ℓ − 1 。
C T \mathsf{CT} CT 的重缩放 R S t RS^t R S t 定义为 R S q ℓ t ( C T ) = ( c t ^ r s , 0 , ⋯ , c t ^ r s , t − 1 ) ∈ ( R Q ℓ − 1 2 ) t \mathsf{RS}_{q_{\ell}}^t(\mathsf{CT}) = (\hat{\mathrm{ct}}_{\mathrm{rs},0}, \cdots, \hat{\mathrm{ct}}_{\mathrm{rs},t-1}) \in (R_{Q_{\ell-1}}^2)^t RS q ℓ t ( CT ) = ( ct ^ rs , 0 , ⋯ , ct ^ rs , t − 1 ) ∈ ( R Q ℓ − 1 2 ) t ,其中 c t ^ r s , 0 = R S q ℓ ( c t ^ 0 ) \hat{\mathrm{ct}}_{\mathrm{rs},0} = \mathsf{RS}_{q_{\ell}}(\hat{\mathrm{ct}}_0) ct ^ rs , 0 = RS q ℓ ( ct ^ 0 ) ,并且对于 i ∈ { 1 , 2 , ⋯ , t − 1 } i \in \{1, 2, \cdots, t-1\} i ∈ { 1 , 2 , ⋯ , t − 1 } :
c t ^ r s , i = R S q ℓ ( q d i v i ⋅ c t ^ 0 + q d i v i − 1 ⋅ c t ^ 1 + ⋯ + c t ^ i ) − q d i v ⋅ R S q ℓ ( q d i v i − 1 ⋅ c t ^ 0 + q d i v i − 2 ⋅ c t ^ 1 + ⋯ + c t ^ i − 1 ) .
\begin{array}{rl}
& \hat{\mathrm{ct}}_{\mathrm{rs},i} = \mathsf{RS}_{q_{\ell}}(q_{\mathrm{div}}^i \cdot \hat{\mathrm{ct}}_0 + q_{\mathrm{div}}^{i-1} \cdot \hat{\mathrm{ct}}_1 + \cdots + \hat{\mathrm{ct}}_i) \\
& \qquad - q_{\mathrm{div}} \cdot \mathsf{RS}_{q_{\ell}}(q_{\mathrm{div}}^{i-1} \cdot \hat{\mathrm{ct}}_0 + q_{\mathrm{div}}^{i-2} \cdot \hat{\mathrm{ct}}_1 + \cdots + \hat{\mathrm{ct}}_{i-1}).
\end{array}
ct ^ rs , i = RS q ℓ ( q div i ⋅ ct ^ 0 + q div i − 1 ⋅ ct ^ 1 + ⋯ + ct ^ i ) − q div ⋅ RS q ℓ ( q div i − 1 ⋅ ct ^ 0 + q div i − 2 ⋅ ct ^ 1 + ⋯ + ct ^ i − 1 ) .
解释: R S t RS^t R S t 旨在保持 R C B q d i v t ( R S q ℓ t ( C T ) ) = R S q ℓ ( R C B q d i v t ( C T ) ) \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{RS}_{q_{\ell}}^t(\mathsf{CT})) = \mathsf{RS}_{q_{\ell}}(\mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{CT})) RCB q div t ( RS q ℓ t ( CT )) = RS q ℓ ( RCB q div t ( CT )) 这一关键性质,确保重缩放的正确性。
引理 5.6
设 C T ∈ ( R Q ℓ 2 ) t \mathsf{CT} \in (R_{Q_{\ell}}^2)^t CT ∈ ( R Q ℓ 2 ) t 是一个密文元组。设 s k = ( 1 , s ) ∈ R 2 \mathsf{sk} = (1, s) \in R^2 sk = ( 1 , s ) ∈ R 2 是一个秘密密钥,其 s s s 具有汉明权重 h h h 。那么数量
[ ( R C B q d i v t ( R S q ℓ t ( C T ) ) ) ⋅ ( 1 , s ) ] Q ℓ − 1 − 1 q ℓ [ ( R C B q d i v t ( C T ) ) ⋅ ( 1 , s ) ] Q ℓ
\left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{RS}_{q_{\ell}}^t(\mathsf{CT})) \right) \cdot (1, s) \right]_{Q_{\ell-1}} - \frac{1}{q_{\ell}} \left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{CT}) \right) \cdot (1, s) \right]_{Q_{\ell}}
[ ( RCB q div t ( RS q ℓ t ( CT )) ) ⋅ ( 1 , s ) ] Q ℓ − 1 − q ℓ 1 [ ( RCB q div t ( CT ) ) ⋅ ( 1 , s ) ] Q ℓ
的无限范数 ∥ ⋅ ∥ ∞ ≤ ( h + 1 ) / 2 \| \cdot \|_{\infty} \leq (h+1)/2 ∥ ⋅ ∥ ∞ ≤ ( h + 1 ) /2 。
4.4.4. 完整的 M u l t t Mult^t M u l t t 算法
定义 5.7(元组乘法)
我们将模 Q ℓ Q_{\ell} Q ℓ 下的密文元组乘法定义为 M u l t t : = R S q ℓ t ∘ R e l i n t ∘ T e n s o r t Mult^t := RS_{q_{\ell}}^t \circ Relin^t \circ Tensor^t M u l t t := R S q ℓ t ∘ R e l i n t ∘ T e n so r t ,其中 q ℓ = Q ℓ / Q ℓ − 1 q_{\ell} = Q_{\ell} / Q_{\ell-1} q ℓ = Q ℓ / Q ℓ − 1 。结果是一个模 Q ℓ − 1 Q_{\ell-1} Q ℓ − 1 下的密文元组。
定理 5.8
设 C T i = ( c t ^ i , 0 , ⋯ , c t ^ i , t − 1 ) ∈ ( R Q ℓ 2 ) t \mathsf{CT}_i = (\hat{\mathrm{ct}}_{i,0}, \cdots, \hat{\mathrm{ct}}_{i,t-1}) \in (R_{Q_{\ell}}^2)^t CT i = ( ct ^ i , 0 , ⋯ , ct ^ i , t − 1 ) ∈ ( R Q ℓ 2 ) t 是密文元组,对于 i ∈ { 1 , 2 } i \in \{1, 2\} i ∈ { 1 , 2 } 。设 q ℓ = Q ℓ / Q ℓ − 1 q_{\ell} = Q_{\ell} / Q_{\ell-1} q ℓ = Q ℓ / Q ℓ − 1 ,秘密密钥 s k = ( 1 , s ) ∈ R 2 \mathsf{sk} = (1, s) \in R^2 sk = ( 1 , s ) ∈ R 2 的 s s s 具有汉明权重 h h h 。假设 ∥ D e c ( c t ^ i , 0 ) ∥ ∞ ≤ M ^ \| \mathsf{Dec}(\hat{\mathrm{ct}}_{i,0}) \|_{\infty} \leq \hat{M} ∥ Dec ( ct ^ i , 0 ) ∥ ∞ ≤ M ^ ,∥ D e c ( c t ^ i , j ) ∥ ∞ ≤ M ˇ \| \mathsf{Dec}(\hat{\mathrm{ct}}_{i,j}) \|_{\infty} \leq \check{M} ∥ Dec ( ct ^ i , j ) ∥ ∞ ≤ M ˇ 对于 i ∈ { 1 , 2 } , j ∈ { 1 , ⋯ , t − 1 } i \in \{1, 2\}, j \in \{1, \cdots, t-1\} i ∈ { 1 , 2 } , j ∈ { 1 , ⋯ , t − 1 } 以及满足 N ( M ^ q d i v t − 1 + M ˇ ⋅ q d i v t − 2 + ⋯ + M ˇ ) 2 + E R e l i n + t 2 h < Q ℓ / 2 N(\hat{M}q_{\mathrm{div}}^{t-1} + \check{M} \cdot q_{\mathrm{div}}^{t-2} + \cdots + \check{M})^2 + E_{\mathrm{Relin}} + \frac{t}{2}h < Q_{\ell}/2 N ( M ^ q div t − 1 + M ˇ ⋅ q div t − 2 + ⋯ + M ˇ ) 2 + E Relin + 2 t h < Q ℓ /2 的 M ^ , M ˇ \hat{M}, \check{M} M ^ , M ˇ 。那么
[ ( R C B q d i v t ( M u l t t ( C T 1 , C T 2 ) ) ) ⋅ s k ] Q ℓ − 1 − 1 q ℓ [ ( R C B q d i v t ( C T 1 ) ⋅ s k ) ⋅ ( R C B q d i v t ( C T 2 ) ⋅ s k ) ] Q ℓ
\left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{Mult}^t(\mathsf{CT}_1, \mathsf{CT}_2)) \right) \cdot \mathsf{sk} \right]_{Q_{\ell-1}} - \frac{1}{q_{\ell}} \left[ \left( \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{CT}_1) \cdot \mathsf{sk} \right) \cdot \left( \mathsf{RCB}_{q_{\mathrm{div}}}^t(\mathsf{CT}_2) \cdot \mathsf{sk} \right) \right]_{Q_{\ell}}
[ ( RCB q div t ( Mult t ( CT 1 , CT 2 )) ) ⋅ sk ] Q ℓ − 1 − q ℓ 1 [ ( RCB q div t ( CT 1 ) ⋅ sk ) ⋅ ( RCB q div t ( CT 2 ) ⋅ sk ) ] Q ℓ
的无限范数
≤ ( ∑ i = 1 t − 1 ( t − i ) N M ˇ 2 q d i v i + E R e l i n + t 2 h ) ⋅ 1 q ℓ + h + 1 2 .
\leq \left( \sum_{i=1}^{t-1} \frac{(t-i)N\check{M}^2}{q_{\mathrm{div}}^i} + E_{\mathrm{Relin}} + \frac{t}{2}h \right) \cdot \frac{1}{q_{\ell}} + \frac{h+1}{2}.
≤ ( i = 1 ∑ t − 1 q div i ( t − i ) N M ˇ 2 + E Relin + 2 t h ) ⋅ q ℓ 1 + 2 h + 1 .
解释: M u l t t Mult^t M u l t t 的误差分析显示,其主要误差项与 t t t 呈正相关,为 ( t − 1 ) N M ˇ 2 / ( q d i v q ℓ ) (t-1)N\check{M}^2/(q_{\mathrm{div}}q_{\ell}) ( t − 1 ) N M ˇ 2 / ( q div q ℓ ) 。这意味着随着 t t t 的增加,需要更仔细地管理 M ˇ \check{M} M ˇ 的增长。通过设置 Δ ≈ q ℓ t \Delta \approx q_{\ell}^t Δ ≈ q ℓ t 且 q ℓ q_{\ell} q ℓ 略大于 q d i v q_{\mathrm{div}} q div ,M u l t t Mult^t M u l t t 可以在相同模数消耗下实现 t t t 倍精度的计算。
4.4.5. 效率分析
M u l t t Mult^t M u l t t 需要调用 t ( t + 1 ) / 2 t(t+1)/2 t ( t + 1 ) /2 次 Tensor、 t t t 次 Relin 和 t t t 次 RS。当 t t t 较小时(如 t ≤ o ( log N ) t \le o(\log N) t ≤ o ( log N ) ),Tensor 的贡献可以忽略。因此,乘法时间大致与 t t t 成比例。同样,由于 M u l t t Mult^t M u l t t 需要的模数更小(t t t 倍),它也可以使用更小的环维度 N N N ,从而在延迟和切换密钥大小方面获得优势。切换密钥大小可比标准 Mult 减少约 t t t 倍。
4.4.6. 低位部分 (c h e c k M check_M c h ec k M ) 的边界控制
定理 5.9(低位部分的增长)
设 C T i = ( c t ^ i , 0 , ⋯ , c t ^ i , t − 1 ) ∈ ( R Q ℓ 2 ) t \mathsf{CT}_i = (\hat{\mathrm{ct}}_{i,0}, \cdots, \hat{\mathrm{ct}}_{i,t-1}) \in (R_{Q_{\ell}}^2)^t CT i = ( ct ^ i , 0 , ⋯ , ct ^ i , t − 1 ) ∈ ( R Q ℓ 2 ) t 是密文元组,对于 i ∈ { 1 , 2 } i \in \{1, 2\} i ∈ { 1 , 2 } 。设 q ℓ = Q ℓ / Q ℓ − 1 q_{\ell} = Q_{\ell} / Q_{\ell-1} q ℓ = Q ℓ / Q ℓ − 1 ,秘密密钥 s k = ( 1 , s ) ∈ R 2 \mathsf{sk} = (1, s) \in R^2 sk = ( 1 , s ) ∈ R 2 的 s s s 具有汉明权重 h h h 。假设 ∥ c a n ∘ D e c ( c t ^ i , 0 ) ∥ ∞ ≤ M ^ \| \mathsf{can} \circ \mathsf{Dec}(\hat{\mathrm{ct}}_{i,0}) \|_{\infty} \leq \hat{M} ∥ can ∘ Dec ( ct ^ i , 0 ) ∥ ∞ ≤ M ^ 且 ∥ c a n ∘ D e c ( c t ^ i , j ) ∥ ∞ < M ˇ \| \mathsf{can} \circ \mathsf{Dec}(\hat{\mathrm{ct}}_{i,j}) \|_{\infty} < \check{M} ∥ can ∘ Dec ( ct ^ i , j ) ∥ ∞ < M ˇ 对于 i ∈ { 1 , 2 } , j ∈ { 1 , ⋯ , t − 1 } i \in \{1, 2\}, j \in \{1, \cdots, t-1\} i ∈ { 1 , 2 } , j ∈ { 1 , ⋯ , t − 1 } 以及某些 M ^ , M ˇ \hat{M}, \check{M} M ^ , M ˇ 。设 C T M u l t = M u l t t ( C T 1 , C T 2 ) = ( c t ^ M u l t , 0 , ⋯ , c t ^ M u l t , t − 1 ) \mathsf{CT}_{\mathrm{Mult}} = \mathsf{Mult}^t(\mathsf{CT}_1, \mathsf{CT}_2) = (\hat{\mathrm{ct}}_{\mathrm{Mult},0}, \cdots, \hat{\mathrm{ct}}_{\mathrm{Mult},t-1}) CT Mult = Mult t ( CT 1 , CT 2 ) = ( ct ^ Mult , 0 , ⋯ , ct ^ Mult , t − 1 ) 。那么以下成立:
∥ c a n ∘ D e c ( c t ^ M u l t , j ) ∥ ∞ ≤ 2 M ^ M ˇ + ( j − 1 ) M ˇ 2 q ℓ + N ( E R e l i n q ℓ + j ⋅ ( h + 3 ) ( q d i v + 1 ) ) ,
\| \mathsf{can} \circ \mathsf{Dec}(\hat{\mathrm{ct}}_{\mathrm{Mult},j}) \|_{\infty} \leq \frac{2\hat{M}\check{M} + (j-1)\check{M}^2}{q_{\ell}} + N \left( \frac{E_{\mathrm{Relin}}}{q_{\ell}} + j \cdot (h+3)(q_{\mathrm{div}}+1) \right),
∥ can ∘ Dec ( ct ^ Mult , j ) ∥ ∞ ≤ q ℓ 2 M ^ M ˇ + ( j − 1 ) M ˇ 2 + N ( q ℓ E Relin + j ⋅ ( h + 3 ) ( q div + 1 ) ) ,
其中 j ∈ { 1 , ⋯ , t − 1 } j \in \{1, \cdots, t-1\} j ∈ { 1 , ⋯ , t − 1 } 。
解释: 这个定理描述了 M u l t t Mult^t M u l t t 乘法后各个低位部分范数的增长。主要项 ( 2 M ^ M ˇ + ( t − 2 ) M ˇ 2 ) / q ℓ (2\hat{M}\check{M} + (t-2)\check{M}^2)/q_{\ell} ( 2 M ^ M ˇ + ( t − 2 ) M ˇ 2 ) / q ℓ 表明误差增长与 M ˇ \check{M} M ˇ 成正比。通过适当选择 M ^ ≈ q ℓ \hat{M} \approx q_{\ell} M ^ ≈ q ℓ 和 q ℓ q_{\ell} q ℓ 略大于 q d i v q_{\mathrm{div}} q div ,低位部分的范数在每次乘法后大约增长 log t \log t log t 比特。同样,为了维持精度,周期性的“重组-分解”操作对于 M u l t t Mult^t M u l t t 也是必要的。
5. 实验设置
5.1. 数据集
文章中没有明确指定使用特定的公开数据集。实验主要侧重于评估 M u l t 2 Mult^2 M u l t 2 算法在不同参数设置下的性能和精度表现,例如重复平方运算。这通常意味着使用了生成数据或基准测试场景来衡量同态加密操作的内在特性,而非针对某个特定应用的真实数据集。
5.2. 评估指标
论文使用了以下评估指标来衡量 M u l t 2 Mult^2 M u l t 2 和 M u l t t Mult^t M u l t t 的性能、精度和资源消耗:
误差增长 (Error Growth) :
概念定义: 衡量同态计算过程中累积的噪声或误差的大小。误差越小,计算结果越精确。
数学公式: 论文中用 log 2 ∥ ⋅ ∥ ∞ c a n \log_2 \|\cdot\|_\infty^{\mathrm{can}} log 2 ∥ ⋅ ∥ ∞ can 来表示,即在规范嵌入 (canonical embedding) 下的无限范数 (infinity norm) 的以 2 为底的对数。
Error bits = log 2 ∥ c a n ( Dec ( c t ) − expected_plaintext ) ∥ ∞
\text{Error}_{\text{bits}} = \log_2 \| \mathsf{can}(\text{Dec}(\mathsf{ct}) - \text{expected\_plaintext}) \|_\infty
Error bits = log 2 ∥ can ( Dec ( ct ) − expected_plaintext ) ∥ ∞
符号解释:
c a n \mathsf{can} can :规范嵌入函数,将环元素映射到复数向量。
D e c ( c t ) \mathsf{Dec}(\mathsf{ct}) Dec ( ct ) :密文 c t \mathsf{ct} ct 的解密结果(明文多项式)。
expected_plaintext \text{expected\_plaintext} expected_plaintext :期望的精确明文多项式。
∥ ⋅ ∥ ∞ \|\cdot\|_\infty ∥ ⋅ ∥ ∞ :向量的无限范数,即其元素绝对值的最大值。
log 2 \log_2 log 2 :以 2 为底的对数,将误差转换为比特数。
∥ c a n ∘ D e c ( c t ˇ ) ∥ ∞ \|\mathsf{can} \circ \mathsf{Dec}(\check{\mathrm{ct}})\|_\infty ∥ can ∘ Dec ( ct ˇ ) ∥ ∞ (或 M ˇ \check{M} M ˇ ):低位部分密文解密后在规范嵌入下的无限范数。这个指标衡量了低位部分的“大小”,它对误差增长有显著影响。
乘法深度 (Multiplicative Depth) :
概念定义: 在不进行引导操作的情况下,可以连续执行的同态乘法操作的最大次数。深度越大,可以评估的电路越复杂。
数学公式: 论文中给出了计算最大乘法深度的公式,与总模数 Q Q Q 和缩放因子 Δ \Delta Δ 有关。对于 M u l t 2 Mult^2 M u l t 2 ,公式为:
Depth = log 2 ( Q ) log 2 ( Δ ) − ( 1 − 1 / k ) ⋅ log 2 ( q d i v )
\text{Depth} = \frac{\log_2(Q)}{\log_2(\Delta) - (1 - 1/k) \cdot \log_2(q_{\mathrm{div}})}
Depth = log 2 ( Δ ) − ( 1 − 1/ k ) ⋅ log 2 ( q div ) log 2 ( Q )
其中 k k k 是两次误差刷新之间可以执行的 M u l t 2 Mult^2 M u l t 2 乘法次数。对于原始 Mult,公式为 Depth = log 2 ( Q ) / log 2 ( Δ ) \text{Depth} = \log_2(Q)/\log_2(\Delta) Depth = log 2 ( Q ) / log 2 ( Δ ) 。
符号解释:
Q Q Q :初始总密文模数。
Δ \Delta Δ :缩放因子。
q d i v q_{\mathrm{div}} q div :同态欧几里得除法的除数。
k k k :两次误差刷新之间执行的 M u l t 2 Mult^2 M u l t 2 乘法次数。
精度 (Precision) :
概念定义: 计算结果的有效比特数,衡量结果的准确性。通常通过计算解密结果与真实值之间的误差来确定。
数学公式: 论文中直接给出了负比特数,例如“-31.3 bits”,这通常表示 log 2 ( 相对误差 ) \log_2(\text{相对误差}) log 2 ( 相对误差 ) 。如果精度是 X X X 比特,意味着相对误差约为 2 − X 2^{-X} 2 − X 。
符号解释: 负值表示误差的比特数,绝对值越大表示精度越高。
最大模数比特大小 (log 2 ( Q L P ) \log_2(Q_L P) log 2 ( Q L P ) ) :
概念定义: 密文模数链中最大的模数与辅助密钥切换模数 P P P 的乘积的比特大小。这反映了方案的整体参数规模。
符号解释: Q L Q_L Q L 是密文链中的最大模数,P P P 是辅助模数。
环维度 (N N N ) :
概念定义: 多项式环 R = Z [ X ] / ( X N + 1 ) R = \mathbb{Z}[X]/(X^N+1) R = Z [ X ] / ( X N + 1 ) 的阶数。N N N 越大,安全强度通常越高,但计算和存储成本也越高。
符号解释: N N N 是一个 2 的幂次。
秘密密钥汉明权重 (h h h ) :
概念定义: 秘密密钥 s s s 中非零系数的个数。影响噪声增长和安全强度。
符号解释: h h h 为非零系数的数量。
素数因子比特大小 (log 2 q \log_2 q log 2 q ) :
概念定义: 模数链中各个素数因子(Base、Mult)和除数 q d i v q_{\mathrm{div}} q div 的比特大小。
符号解释: Base 指初始模数 Q 0 Q_0 Q 0 ,Mult 指乘法素数 q ℓ = Q ℓ / Q ℓ − 1 q_{\ell} = Q_{\ell}/Q_{\ell-1} q ℓ = Q ℓ / Q ℓ − 1 ,Div 指同态欧几里得除法的除数 q d i v q_{\mathrm{div}} q div 。
乘法延迟 (T m u l t T_{\mathrm{mult}} T mult ) :
概念定义: 执行一次同态乘法所需的时间。
符号解释: 以毫秒 (ms) 为单位。
NTT 数量 (#NTT) :
概念定义: 在维度 N N N 下执行数论变换 (Number Theoretic Transform) 的次数。NTT 是 RNS 运算中的核心计算,是计算成本的主要组成部分。
符号解释: 衡量计算复杂度。
密文大小 (ctxt size) :
概念定义: 单个密文在内存中占用的空间。
符号解释: 以兆字节 (MB) 为单位。
切换密钥大小 (key size) :
概念定义: 重线性化密钥 (relinearization key) 等切换密钥在内存中占用的空间。这些密钥通常非常大。
符号解释: 以兆字节 (MB) 为单位。
5.3. 对比基线
本文主要将提出的 M u l t 2 Mult^2 M u l t 2 (或 t = 2 t=2 t = 2 ) 算法与标准 CKKS 乘法算法 (Mult,或 t = 1 t=1 t = 1 ) 进行比较。
在实验中,为了公平比较,对两个方案的参数进行了精心设计,以确保它们在类似的精度、解密容量和安全级别(约 128 比特)下进行比较。在某些情况下,为了评估 M u l t 2 Mult^2 M u l t 2 在更高乘法深度下的表现,甚至会为标准 Mult 创建一个在安全级别上不切实际但能达到相同深度的参数集,以进行纯粹的精度对比。
6. 实验结果与分析
作者通过在 HEaaN 库上概念性实现 M u l t 2 Mult^2 M u l t 2 (即 t = 2 t=2 t = 2 ),在 Intel Xeon Gold 6242 处理器上进行了实验。安全估计基于 [1, 15]。
6.1. 误差增长
6.1.1. 参数设置
以下是原文 Table 1 的结果:
Multiplication algorithm
N
log2(QLP)
log2 Δ
log2 q
log2 P
Base
Mult
Div
Mult(t=1)
2 15 2^{15} 2 15
610
61
61
61 × 8 61 \times 8 61 × 8
-
61
Mult2(t=2, new)
2 15 2^{15} 2 15
449
61
61
38 × 8 38 \times 8 38 × 8
23
61
解释:
M u l t ( t = 1 ) Mult(t=1) M u lt ( t = 1 ) 代表标准 CKKS 乘法,M u l t 2 ( t = 2 , n e w ) Mult2(t=2, new) M u lt 2 ( t = 2 , n e w ) 代表本文提出的 M u l t 2 Mult^2 M u l t 2 。
两个参数集都使用了相同的环度 N = 2 15 N=2^{15} N = 2 15 ,并设定了相似的缩放因子 Δ \Delta Δ (61 比特) 和辅助模数 P P P (61 比特)。
M u l t ( t = 1 ) Mult(t=1) M u lt ( t = 1 ) 的总模数 log2(QLP) 为 610 比特,乘法模数 q ℓ q_{\ell} q ℓ 为 61 比特,共 8 层。
M u l t 2 ( t = 2 ) Mult2(t=2) M u lt 2 ( t = 2 ) 的总模数 log2(QLP) 显著降低到 449 比特,乘法模数 q ℓ q_{\ell} q ℓ 为 38 比特,除数 q d i v q_{\mathrm{div}} q div 为 23 比特,共 8 层。
尽管 M u l t 2 Mult^2 M u l t 2 的总模数更小,但两者都旨在达到相似的精度、解密容量和约 128 比特的安全级别。
6.1.2. 误差增长曲线
下图(原文 Figure 1)展示了重复平方次数与误差增长的关系:
解释:
图中曲线展示了重复平方次数(横轴)与误差(纵轴,以 log 2 ∥ ⋅ ∥ ∞ c a n \log_2 \|\cdot\|_\infty^{\mathrm{can}} log 2 ∥ ⋅ ∥ ∞ can 表示)之间的关系。
e 1 e_1 e 1 (绿色虚线): 代表标准 CKKS 乘法 (t = 1 t=1 t = 1 ) 的误差。它在每次平方后以约 1 比特的速率增长。
e 2 e_2 e 2 (蓝色实线): 代表 M u l t 2 Mult^2 M u l t 2 乘法 (t = 2 t=2 t = 2 ) 的误差。
ct ⊗ \otimes ⊗ ct (橙色点线): 代表 M u l t 2 Mult^2 M u l t 2 中被舍弃的低位部分 c t ˇ 1 ⊗ c t ˇ 2 \check{\mathrm{ct}}_1 \otimes \check{\mathrm{ct}}_2 ct ˇ 1 ⊗ ct ˇ 2 的平方范数,经 q d i v q_{\mathrm{div}} q div 重缩放后,它直接贡献于 e 2 e_2 e 2 的增长。
观察:
在开始的几次乘法中,e 2 e_2 e 2 的增长速率与 e 1 e_1 e 1 相似。
随着 c t ⊗ c t ct \otimes ct c t ⊗ c t (即低位部分)的增长,其贡献变得显著。在大约第 6 次重复平方后,e 2 e_2 e 2 开始比 e 1 e_1 e 1 更快地增长,这是由于 T e n s o r 2 Tensor^2 T e n so r 2 舍弃低位部分引入的误差累积效应。
这与理论分析(定理 4.8)一致,误差 e 2 e_2 e 2 是 e 1 e_1 e 1 和 c t ⊗ c t ct \otimes ct c t ⊗ c t 误差量级的总和。
结论: M u l t 2 Mult^2 M u l t 2 虽然节省了模数,但会使误差更快地增长。这突出了在多层乘法中需要引入“误差刷新”机制(如重组-分解)的重要性。
6.2. 增加同态容量
6.2.1. 参数设置
以下是原文 Table 2 的结果:
Mult. algorithm
N
log2(QLP)
log2 ∆
log2 q
log2 P
Base
Mult
Div
Mult(t=1)
2 15 2^{15} 2 15
855
57
57
57 × 13 57 \times 13 57 × 13
-
57
Mult2(t=2, new)
2 15 2^{15} 2 15
875
61
61
38 × 18 38 \times 18 38 × 18
23 × 3 23 \times 3 23 × 3
61
解释:
目标是最大化乘法深度,同时保持环度 N = 2 15 N=2^{15} N = 2 15 和 128 比特的安全级别。
M u l t ( t = 1 ) Mult(t=1) M u lt ( t = 1 ) 方案:总模数 log2(QLP) 为 855 比特,缩放因子 l o g 2 Δ log2 Δ l o g 2Δ 为 57 比特,支持 13 次乘法。
M u l t 2 ( t = 2 ) Mult2(t=2) M u lt 2 ( t = 2 ) 方案:总模数 log2(QLP) 为 875 比特,缩放因子 l o g 2 Δ log2 Δ l o g 2Δ 为 61 比特。为了处理误差增长,引入了 3 个 Div 素数(23 × 3 23 \times 3 23 × 3 比特),支持 18 次乘法。
为了公平比较,M u l t ( t = 1 ) Mult(t=1) M u lt ( t = 1 ) 的乘法模数 q ℓ q_{\ell} q ℓ 从 61 比特降低到 57 比特,使得其数值误差与 M u l t 2 Mult^2 M u l t 2 相似。这使得 M u l t ( t = 1 ) Mult(t=1) M u lt ( t = 1 ) 的乘法深度增加了一层。
6.2.2. 深度和精度结果
Mult2 方案实现了 18 次连续乘法,而标准 CKKS 方案仅允许 13 次。
通过构造一个虚拟的、具有扩展模数的 M u l t ( t = 1 ) Mult(t=1) M u lt ( t = 1 ) 参数集(l o g 2 ( Q L P ) = 1140 log2(QLP) = 1140 l o g 2 ( Q L P ) = 1140 比特,安全性不达标),作者比较了 18 次重复平方后的精度。
结果显示,M u l t ( t = 1 ) Mult(t=1) M u lt ( t = 1 ) 和 M u l t 2 ( t = 2 ) Mult2(t=2) M u lt 2 ( t = 2 ) 分别获得了 -31.3 比特和 -31.0 比特的精度,表明在相同深度下,M u l t 2 Mult^2 M u l t 2 方案在数值精度方面可以与标准 CKKS 方案相媲美。
误差刷新策略: 为了应对 M u l t 2 Mult^2 M u l t 2 误差的快速增长(如 6.1 节所示),作者在第 6 和第 12 次乘法后进行了“重组-分解”操作(D C P ∘ R C B DCP \circ RCB D CP ∘ RCB ),以将低位部分的范数重置为初始的小值。这解释了 Mult2 方案中使用 3 个 Div 素数的原因(1 个用于初始 DCP,2 个用于误差刷新)。
深度增益分析: 理论上,M u l t 2 Mult^2 M u l t 2 相对于 Mult 的深度增益可以通过公式计算。当误差刷新策略合理(例如,k k k 次乘法后进行一次刷新),且 q_div 约等于 Δ \sqrt{\Delta} Δ 时,M u l t 2 Mult^2 M u l t 2 可以实现约 2 倍的深度提升。
6.3. 增加精度
6.3.1. 参数设置与效率比较
以下是原文 Table 3 的结果:
Mult. algorithm
N
dnum
Tmult
#NTT
ctxt size
key size
Mult(t=1)
2 16 2^{16} 2 16
9
270ms
290
14.8MB
73.7MB
Mult2(t=2, new)
2 15 2^{15} 2 15
11
179ms
350
5.08MB
30.6MB
log2(QP)
log2 Δ
log2 q
log2 P
Base
Mult
Div
1,000
100
(50 × 2 50 \times 2 50 × 2 )
(50 × 2 50 \times 2 50 × 2 ) × 8 \times 8 × 8
-
(50 × 2 50 \times 2 50 × 2 )
680
100
(50 × 2 50 \times 2 50 × 2 )
60 × 8 60 \times 8 60 × 8
40
60
解释:
场景: 8 层乘法深度,100 比特缩放因子(高精度计算)。
标准 M u l t ( t = 1 ) Mult(t=1) M u lt ( t = 1 ) 方案:
需要环度 N = 2 16 N=2^{16} N = 2 16 ,总模数 log2(QLP) 为 1000 比特。这是因为高精度要求更大的模数,而大模数需要更大的 N N N 来维持 128 比特安全。
乘法模数 log2 q 设定为 ( 50 x 2 ) (50 x 2) ( 50 x 2 ) ,表示每个乘法模数是两个 50 比特素数的乘积,以匹配 100 比特的 Δ \Delta Δ 。
性能: 乘法时间 Tmult 270ms,密文大小 14.8MB,切换密钥大小 73.7MB。
M u l t 2 ( t = 2 ) Mult2(t=2) M u lt 2 ( t = 2 ) 方案(新方法):
M u l t 2 Mult^2 M u l t 2 允许将 Δ \Delta Δ (100 比特)分解为 q ≈ 2 60 q \approx 2^{60} q ≈ 2 60 和 q d i v ≈ 2 40 q_{\mathrm{div}} \approx 2^{40} q div ≈ 2 40 。
因此,它可以在更小的环度 N = 2 15 N=2^{15} N = 2 15 下实现相同的计算,且总模数 log2(QLP) 仅为 680 比特。
乘法模数 log2 q 设定为 60 比特,除数 q d i v q_{\mathrm{div}} q div 为 40 比特。
性能: 乘法时间 Tmult 179ms(加速 1.5 倍),密文大小 5.08MB(减小 2.9 倍),切换密钥大小 30.6MB(减小 2.4 倍)。
精度检查: 两个方案在 8 次重复平方后分别获得了 -81.2 比特和 -81.8 比特的精度,表明 M u l t 2 Mult^2 M u l t 2 在高精度场景下也能保持相似的精度。
6.3.2. 性能优势分析
模数和环度降低: M u l t 2 Mult^2 M u l t 2 能够显著降低所需的最大模数 (log2(QLP) 从 1000 比特降至 680 比特),这使得可以在更小的环维度 N N N (从 2 16 2^{16} 2 16 降至 2 15 2^{15} 2 15 ) 下满足相同的安全要求 (128 比特)。
直接性能提升: 环维度和模数的降低直接带来了:
更快的乘法速度: 延迟从 270ms 降至 179ms (约 1.5 倍加速)。
更小的密文大小: 从 14.8MB 降至 5.08MB (约 2.9 倍减小)。
更小的切换密钥大小: 从 73.7MB 降至 30.6MB (约 2.4 倍减小)。切换密钥通常是内存消耗最大的部分,这一改进尤为显著。
NTT 数量对比: M u l t ( t = 1 ) Mult(t=1) M u lt ( t = 1 ) 需要 290 次 N = 2 16 N=2^{16} N = 2 16 维度的 NTT,而 M u l t 2 ( t = 2 ) Mult2(t=2) M u lt 2 ( t = 2 ) 需要 350 次 N = 2 15 N=2^{15} N = 2 15 维度的 NTT。尽管 Mult2 的 NTT 次数更多,但由于其维度减半,总计算量反而减少了。
7. 总结与思考
7.1. 结论总结
本文提出了一种新颖的同态多精度乘法方法 M u l t t Mult^t M u l t t (包括 M u l t 2 Mult^2 M u l t 2 作为特例),用于 CKKS 同态加密方案。该方法的核心思想是将一个密文分解为 t t t 个组件(通过同态欧几里得除法),然后在执行乘法时,仅保留与所需精度相关的组件,舍弃低位项。
主要成果和意义包括:
显著降低模数消耗: M u l t t Mult^t M u l t t 能够将模数消耗降低约 t t t 倍,从而在不增加密文维度或引导操作次数的情况下,实现更深层次的电路评估。
提升同态容量: 实验证明,在相同环度和安全级别下,M u l t 2 Mult^2 M u l t 2 可以显著增加连续乘法的深度(例如,从 13 层增至 18 层)。
在不增加参数的情况下提高精度: 对于需要高精度的场景,M u l t 2 Mult^2 M u l t 2 可以在更小的参数集(例如,更低的环维度 N N N 和总模数 log2(QLP)) 下实现与标准 CKKS 方案相同的精度,并带来显著的性能提升(更快的计算、更小的密文和切换密钥大小)。
实用性提升: 这些改进使得 CKKS 在处理大规模、高深度计算(如机器学习)时更具效率和可行性。
7.2. 局限性与未来工作
作者在论文中指出了以下局限性及未来研究方向:
t > 2 t > 2 t > 2 的实现挑战: 本文主要实现了 M u l t 2 Mult^2 M u l t 2 。对于 t > 2 t > 2 t > 2 的 Tuple-CKKS,其实现复杂性更高,特别是涉及 q d i v ( t − 1 ) q_div^(t-1) q d i v ( t − 1 ) 的模数算术。实现高效的 t > 2 t > 2 t > 2 方案需要修改 RNS 表示以处理这种复合模数,这仍是一个开放的挑战。
高效的对/元组引导操作: 尽管本文讨论了使用 M u l t t Mult^t M u l t t 进行引导操作的可能性,但尚未提供具体的实现。构建高效的对/元组引导操作需要仔细管理同态线性变换中的误差增长,并处理引导过程中不同缩放因子的使用,这也是一个重要的未来工作方向。
7.3. 个人启发与批判
个人启发:
突破性思路: 本文最令人启发之处在于其“化整为零”的思路,将一个复杂的同态乘法任务分解为多个“低精度”的子任务。这种通过同态欧几里得除法实现密文分解的策略非常巧妙,有效地绕过了传统 CKKS 乘法中模数快速消耗的瓶颈。
工程价值显著: 通过降低模数和环维度,直接解决了 HE 方案在实际应用中面临的关键挑战:高计算延迟和巨大的内存开销(特别是切换密钥)。这对于推动 HE 在机器学习等领域的实际落地具有重要意义。
精度与效率的平衡: M u l t t Mult^t M u l t t 能够在保持甚至提高精度的同时,显著优化性能,这表明在设计 HE 算法时,对数值误差的精细控制是实现效率突破的关键。
批判与可以改进的地方:
误差累积与刷新开销: M u l t 2 Mult^2 M u l t 2 乘法引入了额外的误差项,导致误差增长速度加快,需要在多层乘法后进行周期性的“重组-分解”操作来刷新误差。虽然这有效缓解了误差问题,但也引入了额外的计算开销,这种开销在复杂电路中的总影响需要更详细的分析和优化。
t > 2 t > 2 t > 2 的实际性能: 论文虽然提出了 M u l t t Mult^t M u l t t 的理论框架和误差分析,但没有提供 t > 2 t > 2 t > 2 的实验结果。随着 t t t 的增加,虽然模数节省更多,但 T e n s o r t Tensor^t T e n so r t 的操作次数(t ( t + 1 ) / 2 t(t+1)/2 t ( t + 1 ) /2 )和误差累积项 (c h e c k M check_M c h ec k M 的增长)也会增加。因此,对于不同 t t t 值的最佳平衡点以及实际性能收益,仍需进一步的实验验证。
引导操作的集成: 引导操作是 FHE 的核心,但其在 M u l t t Mult^t M u l t t 框架下的具体实现和优化策略尚未明确。一个完整的、与 M u l t t Mult^t M u l t t 兼容且高效的引导操作将是该方法在 FHE 场景下能否全面发挥潜力的关键。
参数选择的复杂性: M u l t t Mult^t M u l t t 引入了额外的参数 q d i v q_{\mathrm{div}} q div 和 t t t ,使得参数选择变得更加复杂。如何为特定应用场景选择最优的参数组合(例如 q d i v q_{\mathrm{div}} q div 和 k k k )以平衡精度、性能和安全需求,需要更深入的指导或自动优化工具。
与现有库的兼容性: 虽然在 HEaaN 上进行了概念性实现,但将其集成到主流 HE 库(如 Microsoft SEAL、HElib)中,并进行广泛的基准测试,才能更好地评估其在各种实际应用中的表现。