Multi-value PBS
参考文献:
- [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.
- [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.
- [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 的自举程序,发现:
- 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 的范数
- 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)?Xm≡F(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=1∑N?1?F(N?i)?Xi∈Z[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?,?k≥1
其实也可以令
τ
\tau
τ 是多项式
T
V
F
TV_F
TVF? 系数的最大公因子,这使得
T
V
F
(
1
)
(
X
)
TV_F^{(1)}(X)
TVF(1)?(X) 的范数更小些。
几何解释:
- 将 T V ( 0 ) TV^{(0)} TV(0) 嵌入到 ACC 内,它测试的是消息的 MSB,分别输出 ± τ \pm \tau ±τ
- 用 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,q∣2N,令
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??m∈Z2r?,以及为了计算任意的布尔函数,[CIM19] 将 m ∈ Z 2 r m \in \mathbb Z_{2^r} m∈Z2r? 缩放为 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} m∈ZBd?,将它分解为 ∑ 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 估计的还要偏大。因此系数之间存在的相关性,事实上会影响到自举过程。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!