近似同态加密的 IND/SIM-CPA+ 安全性:对于 CKKS 实际有效的攻击

2023-12-13 09:27:03

参考文献:

  1. [LM21] Li B, Micciancio D. On the security of homomorphic encryption on approximate numbers[C]//Advances in Cryptology–EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I 40. Springer International Publishing, 2021: 648-677.
  2. [CHK20] Cheon J H, Hong S, Kim D. Remark on the security of ckks scheme in practice[J]. Cryptology ePrint Archive, 2020.
  3. [Bel20] M. Bellare. personal communication, December 2020.
  4. [DS16] Ducas L, Stehlé D. Sanitization of FHE ciphertexts[C]//Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I 35. Springer Berlin Heidelberg, 2016: 294-310.

CKKS 满足 IND-CPA 安全性,但是并非是 IND-CPA+ 安全的,它在某些 MPC 场景中完全不安全!

Preliminaries

Passive Attacker

由于 FHE 密文的延展性,安全性 IND-CCA2 是不可达的,同时 IND-CCA1 实际中也难以实现,因此让人们往往把 IND-CPA 作为设计目标。

然而,在云计算、MPC 等场景下,敌手可以获得某些消息的解密(访问了受限的解密神谕),这导致敌手的能力实际上没能被 IND-CPA 安全性定义所完全捕获。

我们考虑三方场景(解密者 Alice,服务器 Bob,加密者 Eva):Alice 生成 ( s k , p k ) (sk,pk) (sk,pk),Eva 加密数据 m m m 发送给 Bob,Bob 收到密文 c t ct ct 之后做一定的运算 f f f,将 c t ′ ct' ct 发送给 Alice 解密,最后将 m ′ m' m 发送给 Eva。整个流程中, m , f m,f m,f 可以被 Eva 主动选择(也可以不选择、甚至不知道), c t , c t ′ , m ′ ct,ct',m' ct,ct,m 可以被 Eva 被动接收(不可以篡改、不可以注入)。

实际上 Eva 是一个被动敌手(passive attacker),其行为如图:

在这里插入图片描述

被动敌手可以通过访问 FHE 提供的公开标准接口(legitimate operations)构造出某个 m ? m^* m? 对应的 c t ′ ct' ct,要求解密神谕(有能力检查 c t ′ ct' ct 确实是合法产生的)回应 m ′ m' m,从而可能帮助被动敌手区分密文、甚至私钥恢复。

Approximate Encryption

Raw (R)LWE Encryption Scheme,

  • KeyGen:私钥 s ← χ s s \gets \chi_s sχs?,公钥 ( b : = a ? s + e , a ) (b:=a\cdot s+e,a) (b:=a?s+e,a),其中 a ← U ( R q ) a \gets \mathcal U(\mathcal R_q) aU(Rq?) e ← χ e e \gets \chi_e eχe?
  • Encrypt:简单计算 c : = u ? ( b , a ) + ( m , 0 ) + ( e 0 , e 1 ) c:=u \cdot (b,a) + (m,0) + (e_0,e_1) c:=u?(b,a)+(m,0)+(e0?,e1?),其中 u ← χ r u \gets \chi_r uχr? e 0 , e 1 ← χ e e_0,e_1 \gets \chi_e e0?,e1?χe?
  • Decrypt:简单输出 m ′ : = ? s , c ? ( m o d q ) m':=\langle s,c\rangle \pmod q m:=?s,c?(modq),易知 m ′ = m + e ′ m'=m+e' m=m+e

注意上述的加解密不包含编码(纠错码、SIMD 打包),解密就是一个线性运算

  1. 如果采取了纠错码(比如 MSD 编码),使满足解密正确性,称之为精确同态方案(Exact),比如 BGV、BFV
  2. 如果密文的解密结果不是精确值,称之为近似同态方案(Approximate),比如 CKKS

CKKS 因为没有使用 Δ ≈ q / t \Delta \approx q/t Δq/t 缩放因子,这使得噪声增长速度比 BGV、BFV 慢得多,因此可以执行特别深的电路(而不必自举)

采取 BV 的 tensor 技术,采取 GHS 的 raising the modulus 技术,同态乘法为:

  • 预计算:运算秘钥 e v k = ( b : = a s + e + p s 2 , a ) ∈ R p q 2 evk=(b:=as+e+ps^2, a) \in \mathcal R_{pq}^2 evk=(b:=as+e+ps2,a)Rpq2?,其中 a ← U ( R p q ) a \gets \mathcal U(\mathcal R_{pq}) aU(Rpq?) e ← χ e e \gets \chi_e eχe?

  • 在线计算:输入 c 0 , c 1 ∈ R q 2 c_0,c_1\in \mathcal R_{q}^2 c0?,c1?Rq2?,计算多项式乘积并且重线性化,
    c = ( b 0 b 1 , a 0 b 1 + a 1 b 0 ) + ? [ a 0 a 1 ] q ? e v k p ? ( m o d q ) c = (b_0b_1, a_0b_1+a_1b_0) + \left\lfloor \frac{[a_0a_1]_q \cdot evk}{p} \right\rceil \pmod q c=(b0?b1?,a0?b1?+a1?b0?)+?p[a0?a1?]q??evk??(modq)

CKKS 选取模数为 q l = q 0 ? p l q_l=q_0 \cdot p^l ql?=q0??pl,其中 p = 2 p=2 p=2 是 base, l l l 是 level,密文 ( c , Δ , l ) (c,\Delta,l) (c,Δ,l) 是带标记的,其中的 Δ \Delta Δ 是定点数的缩放因子,SIMD 编码是 $m=Encode(z;\Delta):=\lfloor \phi^{-1}(\Delta \cdot z)\rceil $,映射 ? : R → C N / 2 \phi: \mathcal R \to \mathbb C^{N/2} ?:RCN/2 是典范嵌入,选用 ζ 2 N 4 j + 1 , j ∈ [ N / 2 ] \zeta_{2N}^{4j+1},j \in [N/2] ζ2N4j+1?,j[N/2] 作为根。

为了控制噪声增长速度,使用 Rescaling 技术(就是 BGV 的模切换),
R S ( ( c ∈ R q l 2 , Δ , l ) , l ′ ) = ( ? c p l ? l ′ ? ∈ R q l ′ 2 , p l ? l ′ Δ , l ′ ) RS((c \in \mathcal R_{q_{l}}^2,\Delta,l), l') = \left(\left\lfloor \frac{c}{p^{l-l'}} \right\rceil \in \mathcal R_{q_{l'}}^2, p^{l-l'}\Delta, l'\right) RS((cRql?2?,Δ,l),l)=(?pl?lc??Rql?2?,pl?lΔ,l)
CKKS 的线性解密结果为 m ′ = m + e ∈ R q m'=m+e \in \mathcal R_q m=m+eRq?,其中 $m=\lfloor \phi^{-1}(\Delta \cdot z)\rceil $,最终的输出是近似值 z ′ = D e c o d e ( m ′ ; Δ ) : = ? ( m ′ / Δ ) = z + e ′ z' = Decode(m';\Delta):= \phi(m'/\Delta) = z+e' z=Decode(m;Δ):=?(m)=z+e

Security Notions

Indistinguishability-Based

[LM21] 首先基于游戏,给出了 IND-CPA+ 的定义,

在这里插入图片描述

Simulation-Based

[LM21] 接着基于模拟,给出了 SIM-CPA+ 的定义,

在这里插入图片描述

在这里插入图片描述

Separations Between Them

易知,IND-CPA+ 立即导致 IND-CPA(它仅访问一次 E,并且不访问 H 和 D),可以证明 IND-CPA+ 是严格强的:

  • 对于精确同态加密,[LM21] 证明了 IND-CPA+ 等价于 IND-CPA
  • 对于近似同态加密,[LM21] 证明了 IND-CPA+ 严格强于 IND-CPA

可以证明,SIM-CPA+ 导致了 IND-CPA+,并且两者相分离(SIM-CPA+ 严格更强):

  • 对于精确同态加密,[LM21] 证明了 SIM-CPA+ 等价于 IND-CPA+
  • 对于近似同态加密,[Bel20] 证明了 SIM-CPA+ 严格强于 IND-CPA+

确切地说,我们定义有界查询数量的变体 ( q , l ) (q,l) (q,l)-IND-CPA+ 和 ( q , l ) (q,l) (q,l)-SIM-CPA+,它对于任意的受限敌手满足上述 IND-CPA+ 安全定义、SIM-CPA+ 安全定义,除了这里的敌手只能访问至多 l ( κ ) l(\kappa) l(κ) 次 E 和 H 神谕,访问至多 q ( κ ) q(\kappa) q(κ) 次 D 神谕。[LM21] 证明了:对于任意的 q ≥ 2 q \ge 2 q2,都存在 ( q , l ) (q,l) (q,l)-SIM-CPA+ 安全,但是 ( q + 1 , l ) (q+1,l) (q+1,l)-IND-CPA+ 不安全的近似同态加密。因此,在 IND-CPAIND-CPA+ 之间,存在无限长的安全性(严格)递增的安全性序列

此外,上述的定义都是适应性的(security with adaptively chosen queries):敌手可以主动选取不同的查询次数和顺序。我们可以要求敌手在看到 p k , e v k pk,evk pk,evk 之前就已经确定了它的查询顺序,这就是非适应的(fully non-adaptive model)。[LM21] 证明了非适应安全比适应性安全弱的多:存在近似同态加密方案,它是 SIM-CPA+ 非适应安全的,但不是 ( 2 , 2 ) (2,2) (2,2)-IND-CPA+ 适应性安全的。

Circuit Privacy and Functional Decryption

Circuit Privacy:电路隐私是说,从 E n c ( m ) Enc(m) Enc(m) 同态计算出 E n c ( f ( x ) ) Enc(f(x)) Enc(f(x)),不会泄露 f f f 的信息。

Functional Decryption:函数解密是说,选取 f ∈ L f \in \mathcal L fL,要求 D 神谕回应 f ( D e c ( c ) ) f(Dec(c)) f(Dec(c)),而非 m = D e c ( c ) m=Dec(c) m=Dec(c) 本身。

[LM21] 简单描述了如何将 IND-CPA+ 以及 SIM-CPA+ 的安全性定义扩展到两者。

Attacks to CKKS

[LM21] 给出了 CKKS 的被动敌手下的私钥恢复攻击(这远比 IND-CPA+ 攻击更强),因此 CKKS 虽然是 IND-CPA 安全,却不是 IND-CPA+ 安全。

Linear Key-Recovery Attack

简单起见,我们考虑对称加密。

如果敌手可以获得密文 c = ( b : = a ? s + m + e , a ) c=(b:=a \cdot s+m+e,a) c=(b:=a?s+m+e,a) 的解密 m ′ = m + e m'=m+e m=m+e,那么
b ? m ′ = a ? s ( m o d q ) b-m' = a \cdot s \pmod q b?m=a?s(modq)
它是关于 s s s 的线性方程,

  • 对于 LWE-based,只需要收集 n n n 个线性方程组,就可以求解出 s s s
  • 对于 RLWE-based,只要 a ∈ R q a \in \mathcal R_q aRq? 可逆,甚至只需要一个方程,就可以计算出 s = ( b ? m ′ ) ? a ? 1 s=(b-m') \cdot a^{-1} s=(b?m)?a?1

CKKS 的模数为 q l = q 0 ? 2 l q_l=q_0 \cdot 2^l ql?=q0??2l,导致 a ∈ R q a \in \mathcal R_q aRq? 基本都是不可逆的,但依旧可以恢复出 s s s 的部分信息

Lattice Attack

CKKS 采取了 SIMD 编码,最终的解密结果是 z ′ = D e c o d e ( m ′ ) z'=Decode(m') z=Decode(m) 而非 m ′ m' m 本身

[LM21] 采取重编码手段,尝试恢复出 m ′ m' m

  • 如果 E n c o d e ( z ′ ) = D e c ( E n c ( m ; e ) ) Encode(z') = Dec(Enc(m;e)) Encode(z)=Dec(Enc(m;e)),那么获得 m ′ = m + e m'=m+e m=m+e 之后,可以采取上述的线程代数的手段恢复出私钥
  • 如果 E n c o d e ( z ′ ) = D e c ( E n c ( m ; e ) ) + ? Encode(z') = Dec(Enc(m;e))+\epsilon Encode(z)=Dec(Enc(m;e))+?,只要 ∥ ? ∥ 2 ≤ 2 ? N / 2 ? ( q N ? h ) , h = H W ( s ) \|\epsilon\|_2 \le 2^{-N/2} \cdot (q\sqrt N-h), h=HW(s) ?2?2?N/2?(qN ??h),h=HW(s),那么使用格基约简求解近似 CVP 问题,依旧可以高效恢复出私钥

在多种 CKKS 的实现中(HEAAN、HElib、SEAL、PALISADE),编码解码过程都是利用 double-precision FFT 完成的。而密文的存储/运算,有些使用 Multi-precision Integer,有些则使用 RNS 系统。总体上,CKKS 的计算精度越高,那么 ? \epsilon ? 就越小,这导致更加有效的攻击。

Experiments

仅使用线性代数攻击 CKKS,

在这里插入图片描述

对于不同实现的攻击结果,

在这里插入图片描述

Against IND-CPA+ Attack

最后 [LM21] 建议修改解密函数,不要输出 m ′ = m + e ~ m'=m+\tilde e m=m+e~(其中的 e ~ \tilde e e~ 包含了 s k sk sk u , e u,e u,e 的信息),而是输出一个近似值(不依赖私钥和随机带)

  1. 添加高斯噪声:简单在解密结果上添加高斯噪声,但是敌手可以通过多次解密同一个密文,统计出原本的解密结果
  2. 添加确定性噪声:利用 PRF 关于 ct 计算出确定的噪声(强制每个密文至多解密一次),这个类似于噪声洪泛(noise flooding techniques),但是需要超多项式的模数。或者使用 [DS16] 的密文消毒(Sanitization of FHE Ciphertexts,通过 soak-spin-repeat 策略,迭代 Rerandomize、Bootstrapping 滚洗),使用较小的参数达到某个先验的界 q q q-IND-CPA+ 安全
  3. 精确解密:选取合适的 Δ \Delta Δ 使得高概率满足 ? ( m + e ~ ) / Δ ? = ? m / Δ ? \lfloor (m+\tilde e)/\Delta\rceil = \lfloor m/\Delta\rceil ?(m+e~)?=?m?(后者是精确值),输出近似值 ? ( m + e ~ ) / Δ ? \lfloor (m+\tilde e)/\Delta\rceil ?(m+e~)? 而非 m + e ~ m+\tilde e m+e~ 本身,这似乎是对于 CKKS 更有前途的

[CHK20] 对 HEAAN 做了修改,提供了两种场景下的解密函数,

  • Dec:这是原始的解密函数,它提供了 IND-CPA 安全,不允许泄露解密结果给任何人
  • DecForShare:对解密结果添加一定的高斯噪声,但是 B c t x t B_{ctxt} Bctxt? 的规模 [CHK20] 并没有具体给出

[CHK20] 调查了其他几个实现的办法:

  • HElib 粗糙地估计各个密文的噪声上界 B B B,然后根据它来添加噪声
  • PALISADE 限制明文空间仅使用实部,虚部强行置为 0 0 0,运算过程中虚部会累积一定的噪声,用它们来估计密文的噪声规模
  • Lattigo 要求用户提供期望的输出精度 b b b,然后执行 DecodeAndRound,舍入解码的结果
  • SEAL 简单要求用户不要泄露解密结果(躺平了)

但是上述这些都只能缓解问题,重新设计一个更加安全可靠的近似同态加密,仍是个开放问题。

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