Multi-value PBS

2023-12-22 19:01:46

参考文献:

  1. [CIM19] Carpov S, Izabachène M, Mollimard V. New techniques for multi-value input homomorphic evaluation and applications[C]//Topics in Cryptology–CT-RSA 2019: The Cryptographers’ Track at the RSA Conference 2019, San Francisco, CA, USA, March 4–8, 2019, Proceedings. Springer International Publishing, 2019: 106-126.
  2. [CGGI20] Chillotti I, Gama N, Georgieva M, et al. TFHE: fast fully homomorphic encryption over the torus[J]. Journal of Cryptology, 2020, 33(1): 34-91.
  3. [GBA21] Guimar?es A, Borin E, Aranha D F. Revisiting the functional bootstrap in TFHE[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021: 229-253.

Multi-value PBS

[CIM19] 分析了 FHEW 和 TFHE 的自举程序,发现:

  1. FHEW 使用 ACC 计算 X b ? s T a X^{b-s^Ta} Xb?sTa,然后使用关于 F F F 的 Test Vector 作用到 ACC 上(多项式数乘),将 LUT 旋转为常数项是 F ( m ) F(m) F(m)
    • 优点:盲旋转获得的 ACC,可以作用到关于不同 F F F 的多个 TV 上
    • 缺点:由于 ACC 和 TV 的乘法,噪声增长依赖于 TV 的范数
  2. TFHE 直接把这个 Test Vector 嵌入到初始的 ACC 中,计算过程中将它旋转 X b ? s T a X^{b-s^Ta} Xb?sTa 使得常数项是 F ( m ) F(m) F(m)
    • 优点:公开的 TV 直接初始嵌入到了 ACC 里,输出的噪声独立于 TV 范数
    • 缺点:每次 PBS 只能计算单个函数

总体来说,FHEW-like 的 LUT 计算步骤是:选取合适的 T V F TV_F TVF?,使得
T V F ( X ) ? X m ≡ F ( m ) + R ( X ) ( m o d Φ 2 N ( X ) ) TV_F(X) \cdot X^m \equiv F(m) + R(X) \pmod{\Phi_{2N}(X)} TVF?(X)?XmF(m)+R(X)(modΦ2N?(X))
其中 R ( X ) R(X) R(X) 的常数项为零, F ( m ) F(m) F(m) 是常数项。其中的 X m X^m Xm 是在 ACC 中同态计算的, T V F TV_F TVF? 根据需要加密(电路隐私)或不加密(公开的电路)。

注意 FHEW-like 不支持 LWE/RLWE 密文之间的 BGV-like 乘法,

  • TFHE 可以之间将 T V F TV_F TVF? 加密在 RLWE-based ACC 中。
  • 但是 FHEW 需要将 T V F TV_F TVF? 加密在 RGSW 内,使用外积来计算乘积(同态的模结构)。如果仅知道它的 RLWE 密文,还需要使用 [CGGI20] 的电路自举(多个 Gate PBS 求出若干 LWE 拼接成 GSW)。

Test polynomial factorization

为了综合 FHEW 和 TFHE 的优点,[CIM19] 提出将 Test Vector 分解为两部分,一部分(独立于 F F F)初始加密在 ACC 内,另一部分(依赖 F F F)最后最用到 ACC 上。

确切地说,给定任意的反循环函数 F : Z 2 N → Z 2 N F: \mathbb Z_{2N} \to \mathbb Z_{2N} F:Z2N?Z2N?(编码了待计算的 f : Z s → Z t f:\mathbb Z_s \to \mathbb Z_t f:Zs?Zt?),Test Vector 对应的多项式为:
T V F ( X ) = F ( 0 ) ? ∑ i = 1 N ? 1 F ( N ? i ) ? X i ∈ Z [ X ] TV_F(X) = F(0) - \sum_{i=1}^{N-1} F(N-i) \cdot X^i \in \mathbb Z[X] TVF?(X)=F(0)?i=1N?1?F(N?i)?XiZ[X]
我们简记 T V F ( X ) TV_F(X) TVF?(X) 的各项系数为 t i ∈ Z 2 N t_i \in \mathbb Z_{2N} ti?Z2N?

我们做如下分解:
τ ? T V ( 0 ) ( X ) ? T V ( 1 ) ( X ) ≡ T V F ( X ) ( m o d Φ 2 N ( X ) ) \tau \cdot TV^{(0)}(X) \cdot TV^{(1)}(X) \equiv TV_F(X) \pmod{\Phi_{2N}(X)} τ?TV(0)(X)?TV(1)(X)TVF?(X)(modΦ2N?(X))
[CIM19] 设置 τ = 1 / 2 \tau = 1/2 τ=1/2 以及 T V ( X ) = ∑ i X i TV(X) = \sum_i X^i TV(X)=i?Xi,计算出 T V F ( 1 ) ( X ) TV_F^{(1)}(X) TVF(1)?(X) 系数:
t 0 ′ = t 0 + t N ? 1 , ?? t k ′ = t k ? t k ? 1 , ? k ≥ 1 t_0' = t_0+t_{N-1},\,\, t_k' = t_k-t_{k-1},\forall k \ge 1 t0?=t0?+tN?1?,tk?=tk??tk?1?,?k1
其实也可以令 τ \tau τ 是多项式 T V F TV_F TVF? 系数的最大公因子,这使得 T V F ( 1 ) ( X ) TV_F^{(1)}(X) TVF(1)?(X) 的范数更小些。

在这里插入图片描述

几何解释:

  1. T V ( 0 ) TV^{(0)} TV(0) 嵌入到 ACC 内,它测试的是消息的 MSB,分别输出 ± τ \pm \tau ±τ
  2. T V F ( 1 ) TV_F^{(1)} TVF(1)? 作用到 ACC 上,它将上述的结果做了线性组合 t i ′ X i t_i'X^i ti?Xi,最终输出 F ( m ) F(m) F(m)

对于待计算的反循环函数 f : Z s → Z q f:\mathbb Z_s \to \mathbb Z_q f:Zs?Zq? s , q ∣ 2 N s,q \mid 2N s,q2N,令 r ( m ) : = ? m ? t / 2 N ? r(m):=\lfloor m \cdot t/2N \rceil r(m):=?m?t/2N? 是缩放舍入函数,那么设置 F = f ° r F = f \circ r F=f°r,构造出 T V F ( 1 ) ( X ) TV_F^{(1)}(X) TVF(1)?(X),[CIM19] 证明了
∥ T V F ( 1 ) ( X ) ∥ 2 2 ≤ s ? ( q ? 1 ) 2 \Big\| TV_F^{(1)}(X) \Big\|_2^2 \le s \cdot (q-1)^2 ?TVF(1)?(X) ?22?s?(q?1)2

Homomorphic LUT

现在,我们利用分解出的单个 τ ? T V ( 0 ) \tau \cdot TV^{(0)} τ?TV(0) 和若干个 T V F i ( 1 ) TV^{(1)}_{F_i} TVFi?(1)?,执行 multi-value PBS,

在这里插入图片描述

其中最花费时间的 step 3 是公共部分,仅执行一次。根据不同的 F i F_i Fi?,多次执行 step 4,输出同一个消息 m m m 的不同函数值 F i ( m ) F_i(m) Fi?(m)

在这里插入图片描述

为了计算 multi-value 布尔函数 f : Z 2 r → Z 2 t f:\mathbb Z_2^r \to \mathbb Z_2^t f:Z2r?Z2t?,由于 T V F ( 1 ) TV_F^{(1)} TVF(1)? 范数的约束,[CIM19] 将它分解为多个函数
f 1 , ? f t : Z 2 r → Z 2 f_1,\cdots f_t: \mathbb Z_{2^r} \to \mathbb Z_2 f1?,?ft?:Z2r?Z2?
其中 f i f_i fi? 的 domain 是整环 Z s , s = 2 r \mathbb Z_s,s=2^r Zs?,s=2r,range 是整环 Z q , q = 2 \mathbb Z_q,q=2 Zq?,q=2,从而有 ∥ T V F ( 1 ) ∥ 2 2 ≤ 2 r \| TV_F^{(1)} \|_2^2 \le 2^r TVF(1)?22?2r

为了方便布尔值和整环之间的转换 ? : ( m 0 , ? ? , m r ? 1 ) ∈ Z 2 r ? m ∈ Z 2 r \phi: (m_0,\cdots,m_{r-1})\in \mathbb Z_2^r \mapsto m \in \mathbb Z_{2^r} ?:(m0?,?,mr?1?)Z2r??mZ2r?,以及为了计算任意的布尔函数,[CIM19] 将 m ∈ Z 2 r m \in \mathbb Z_{2^r} mZ2r? 缩放为 m / 2 r + 1 ∈ [ 0 , 0.5 ) m/2^{r+1} \in [0,0.5) m/2r+1[0,0.5) 加密在 TFHE 密文中(MSB 强制为零),同时把 m i ∈ Z 2 m_i \in \mathbb Z_2 mi?Z2? 缩放为 m i / 2 r + 1 m_i/2^{r+1} mi?/2r+1,从而实现 PBS 的输入输出之间的连接。

在这里插入图片描述

对于 6-bits to 6-bits PBS,此方案的计算时间为 1.57 秒(相较于 Gate PBS 的 10 ms 简直太慢了吧)。

Combine PBS

随着 LUT 的精度提高(相位空间 Z q \mathbb Z_q Zq?,编码消息空间 Z t \mathbb Z_t Zt?),为了留出足够的纠错冗余(区间长度 Δ ≈ q / t \Delta \approx q/t Δq/t 大于噪声规模),不得不增大 ACC 的维度。

在这里插入图片描述

[GBA21] 提出可以将单个高精度 LUT 切分为多个很小的 LUT,迭代地计算出最终的查表结果。因为只需要 PBS 支持低精度 LUT 即可,从而避免参数规模的扩大。

他们给出了两种组合方法:树型组合(PBS 结果是 LUT)、链式组合(PBS 结果是 Seletor)

在这里插入图片描述

Tree-based PBS

设置数字分解基底 B B B,让 ACC 仅支持 t = B t=B t=B 的明文空间(LUT 的各个数值在 RLWE 系数上连续重复 N / B N/B N/B 次),

  • 输入数据 m ∈ Z B d m \in \mathbb Z_{B^d} mZBd?,将它分解为 ∑ i m i ? B i \sum_i m_i\cdot B^i i?mi??Bi,分别加密为 c i = L W E ( m i ) c_i=LWE(m_i) ci?=LWE(mi?)
  • 对于高精度函数 f : Z B d → Z B f: \mathbb Z_{B}^d \to \mathbb Z_B f:ZBd?ZB?(并行 d d d 个函数),对应的 B d B^d Bd-size LUT,将它顺序拆分 B d ? 1 B^{d-1} Bd?1 个区间,作为 B B B-size LUT
  • 易知各个 LUT 都以 m 0 m_0 m0? 作为 Selector,因此执行 PBS 获得 B d ? 1 B^{d-1} Bd?1 个消息 f ( x 0 = m 0 , ? ? ) f(x_0=m_0,\cdots) f(x0?=m0?,?) 的 LWE 密文
  • 将它们顺序打包 B d ? 2 B^{d-2} Bd?2 B B B-size LUT(通过 Functional Key-Switch),继续使用 m 1 m_1 m1? 作为 Selector 执行 PBS,计算出 f ( x 0 = m 0 , x 1 = m 1 , ? ? ) f(x_0=m_0,x_1=m_1,\cdots) f(x0?=m0?,x1?=m1?,?) 的 LWE 密文
  • 迭代执行,最终会输出 f ( m 0 , m 1 , ? ? , m d ? 1 ) f(m_0,m_1,\cdots,m_{d-1}) f(m0?,m1?,?,md?1?) 的 LWE 密文

注意到第一层的各个 LUT 是明文列表,并且作用在相同的 m 0 m_0 m0? 上,因此可以使用 [CIM19] 的 Multi-value PBS,仅执行一次盲旋转。但是输出的 LUT 被加密在了 RLWE 内(包含了 m 0 m_0 m0? 的信息),因此 Test Vetor 作用到 ACC 上需要利用外积。因为电路自举太慢了,所以 [GBA21] 对于后续的计算不再使用 Multi-value PBS 技术,仅仅使用 TFHE 的方式挨个计算。

在这里插入图片描述

对于特殊结构的函数 f f f,它可能连续的小区间内的数值是常数或者线性函数,从而某些小的 LUT 可以被简化掉(但是泄露的电路信息,不过不会泄露消息本身)。对于 Sigmoid,它的两端基本是常数(简单设置常数密文),中间基本是线性函数(利用 LWE 的线性同态),其余的部分是非线性的(利用 PBS 计算)。

在这里插入图片描述

Chain-based PBS

上述的 Tree-based PBS 是通用结构,但是噪声增长比较大。[GBA21] 推广了之前某个工作的整数比较算法,给出了链式组合结构:

  • 依旧是将 m m m 分解为 m i m_i mi?,将高精度 LUT 使用某种复杂的方式分解为 d d d 个很小的 LUT
  • 首先 c 0 c_0 c0? 执行 PBS 获得 c ˉ \bar c cˉ,将它和 c 1 c_1 c1? 做线性组合后,被用作下一个 LUT 的 Selector(而非 LUT),利用这些 Selector 迭代处理各个 LUT

它的噪声更小,但是更加适合 carry-like logics(例如:比较、算术加法、算术乘法)。

[GBA21] 并没有详细描述 Chain-based PBS 的具体流程。高精度 LUT 到底怎么分解的?Selector 的线性组合又是怎么确定的?完全没有写。

Improving building blocks

Base-aware Key-Switching

在 Tree-based PBS 中,需要使用 Functional Key-Switch,将上一层的 B B B 个 LWE 打包为一个 ACC 密文。由于 ACC 中需要留足冗余区间,导致其中包含大量的连续重复的系数,因此这个特殊的 KS 过程可以被专门优化:

在这里插入图片描述

使用空间换时间的策略,[GBA21] 将 KS 的规模扩大了 B B B 倍,但是同态线性解密时,不再需要计算较慢的多项式数乘,而是简单的内积(常数多项式数乘的加和)。

Multi-Value Extract

此外为了降低数乘的噪声,因为加和的方差 σ x + y 2 = σ x 2 + σ y 2 + 2 ρ σ x σ y \sigma_{x+y}^2 = \sigma_x^2+\sigma_y^2+2\rho\sigma_x\sigma_y σx+y2?=σx2?+σy2?+2ρσx?σy?,其中 ρ \rho ρ 是相关系数。如果计算数乘,

  • 给定一个 X X X 它是 x x x 附近的随机变量,那么 ρ = 1 \rho=1 ρ=1,从而 σ n x 2 = n 2 σ x 2 \sigma_{nx}^2=n^2\sigma_x^2 σnx2?=n2σx2?
  • 如果给定 X 1 , ? ? , X n X_1,\cdots,X_n X1?,?,Xn? 它们是 x x x 附近的独立变量,则有 ρ = 0 \rho=0 ρ=0,就仅是 σ n x 2 = n σ x 2 \sigma_{nx}^2=n\sigma_x^2 σnx2?=nσx2?

根据 TFHE 的启发式假设,ACC 的各个系数使用了独立的高斯噪声,因此我们可以将 x x x 对应区间的 b b b 项加起来,作为数乘 b x bx bx 的结果。这要求噪声规模更小一点,从而 PBS 输出的 ACC 常数项附近的半径 b / 2 b/2 b/2 区间内都加密相同的数值。

在这里插入图片描述

不幸的是,[GBA21] 在实验中并没有观察到噪声增长从平方降低而线性,并且实际噪声水平比 TFHE 估计的还要偏大。因此系数之间存在的相关性,事实上会影响到自举过程。

文章来源:https://blog.csdn.net/weixin_44885334/article/details/135158141
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。