祥符网站建设,提供商城网站,活动发布类网站开发,自己做发卡网站《全同态加密理论、生态现状与未来展望》系列由lynndell2010gmail.com和mutourend2010gmail.com整理原创发布#xff0c;分为上中下三个系列#xff1a;
全同态加密理论、生态现状与未来展望#xff08;上#xff09;#xff1a;专注于介绍全同态加密理论知识。全同态加密…《全同态加密理论、生态现状与未来展望》系列由lynndell2010gmail.com和mutourend2010gmail.com整理原创发布分为上中下三个系列
全同态加密理论、生态现状与未来展望上专注于介绍全同态加密理论知识。全同态加密理论、生态现状与未来展望中1专注于介绍全同态加密四代算法中第一代第二代FHE算法的衍化历程。全同态加密理论、生态现状与未来展望中2专注于介绍全同态加密四代算法中第三代第四代FHE算法的衍化历程。全同态加密理论、生态现状与未来展望下专注于介绍当前全同态加密生态现状及未来展望。
整个系列内容可能存在纰漏希望能得到大家的反馈有任何问题欢迎邮件联系lynndell2010gmail.com和mutourend2010gmail.com或在本文下方评论留言。
3.3 第3代基于LWE和RLWE 图 7: 第 3 代基于 LWE 和 RLWE
3.3.1 GSW13
Homomorphic Encryption from Learning with Errors:Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
安全参数为 λ \lambda λ电路深度为 L L L。模为 q q q、噪声分布 χ \chi χ、维数 n n n 以及 m m m。 其中分布 χ \chi χ是 Z \mathbb{Z} Z上的噪声高斯分布 m 2 n log q m2n\log q m2nlogq。令 l ⌈ log q ⌉ l \lceil \log q \rceil l⌈logq⌉, N ( n 1 ) l N (n1)l N(n1)l。 密钥生成 选择随机向量 s ′ ← Z q n \mathbf{s} \leftarrow \mathbb{Z}^n_q s′←Zqn私钥为 s k s ( 1 , s ′ ) ∈ Z q n 1 sk \mathbf{s} (1, \mathbf{s}) \in \mathbb{Z}^{n1}_q sks(1,s′)∈Zqn1。 有以下等式成立 Powerof2 ( s ) ( s , 2 s , ⋯ , 2 l − 1 s ) m o d q ( 1 , 2 , ⋯ , 2 l − 1 , s ′ , 2 s ′ , ⋯ , 2 l − 1 s ′ ) m o d q \text{Powerof2}(\mathbf{s}) (\mathbf{s}, 2\mathbf{s}, \cdots, 2^{l-1}\mathbf{s}) \mod q (1, 2, \cdots, 2^{l-1},\mathbf{s}, 2\mathbf{s}, \cdots, 2^{l-1}\mathbf{s}) \mod q Powerof2(s)(s,2s,⋯,2l−1s)modq(1,2,⋯,2l−1,s′,2s′,⋯,2l−1s′)modq 选取随机矩阵 A ′ ← Z q m × n \mathbf{A} \leftarrow \mathbb{Z}^{m \times n}_q A′←Zqm×n和噪声向量 e ← χ m \mathbf{e} \leftarrow \chi^m e←χm计算 b : A ′ ⋅ s ′ e b : \mathbf{A} \cdot \mathbf{s} \mathbf{e} b:A′⋅s′e 令 A \mathbf{A} A为 n 1 n1 n1列矩阵由向量 b \mathbf{b} b和矩阵 A ′ \mathbf{A} A′构成 A [ b ∣ − A ′ ] ∈ Z q m × ( n 1 ) \mathbf{A} [\mathbf{b} | -\mathbf{A}] \in \mathbb{Z}_q^{m \times (n1)} A[b∣−A′]∈Zqm×(n1) 公钥为 p k A pk \mathbf{A} pkA。 注意有以下等式成立 A ⋅ s [ b ∣ − A ′ ] ⋅ ( 1 , s ′ ) ( A ′ ⋅ s ′ e ) − A ′ s ′ e \mathbf{A} \cdot \mathbf{s} [\mathbf{b} | -\mathbf{A}]\cdot (1,\mathbf{s}) (\mathbf{A} \cdot \mathbf{s} \mathbf{e})-\mathbf{A}\mathbf{s} \mathbf{e} A⋅s[b∣−A′]⋅(1,s′)(A′⋅s′e)−A′s′e 加密 消息为 m ∈ { 0 , 1 } m \in \{0, 1\} m∈{0,1}选取随机矩阵 R ∈ { 0 , 1 } N × m \mathbf{R} \in \{0, 1\}^{N \times m} R∈{0,1}N×m如下计算 C : m ⋅ I N R ⋅ A \mathbf{C} :m \cdot \mathbf{I}_N\mathbf{R} \cdot \mathbf{A} C:m⋅INR⋅A 其中 I N \mathbf{I}_N IN是 N × N N \times N N×N的单位矩阵。则密文为 C \mathbf{C} C。为满足同态性密文长度不变通常记为 Flatten ( C ) \text{Flatten}(\mathbf{C}) Flatten(C)。 解密 输入私钥 s \mathbf{s} s和密文 C \mathbf{C} C如下计算 C s ( m ⋅ I N R ⋅ A ) s m ⋅ I N s R e m ⋅ I N s e ∗ m ⋅ Powersof2 ( s ) e ∗ \mathbf{C}\mathbf{s} (m \cdot \mathbf{I}_N\mathbf{R} \cdot \mathbf{A})\mathbf{s} m \cdot \mathbf{I}_N\mathbf{s}\mathbf{R}\mathbf{e} m \cdot \mathbf{I}_N\mathbf{s}\mathbf{e}^* m\cdot\text{Powersof2}(\mathbf{s})\mathbf{e}^* Cs(m⋅INR⋅A)sm⋅INsRem⋅INse∗m⋅Powersof2(s)e∗ 其中 m I N s ( m , m s ′ ) m\mathbf{I}_N\mathbf{s}(m,ms) mINs(m,ms′)取出 m m m R ⋅ e e ∗ ≈ 0 \mathbf{R} \cdot \mathbf{e}\mathbf{e}^*\approx 0 R⋅ee∗≈0。 同态加法 C C ′ ( m m ′ ) ⋅ I N ( R R ′ ) ⋅ A \mathbf{C}\mathbf{C} (mm)\cdot \mathbf{I}_N(\mathbf{R}\mathbf{R}) \cdot \mathbf{A} CC′(mm′)⋅IN(RR′)⋅A 通常记为 Flatten ( C C ′ ) \text{Flatten}(\mathbf{C}\mathbf{C}) Flatten(CC′)。 解密 ( C C ′ ) s ( ( m m ′ ) ⋅ I N ( R R ′ ) ⋅ A ) s ( m m ′ ) ⋅ I N s ( R R ′ ) e (\mathbf{C}\mathbf{C})\mathbf{s}((mm) \cdot \mathbf{I}_N(\mathbf{R}\mathbf{R}) \cdot \mathbf{A})\mathbf{s}(mm) \cdot \mathbf{I}_N\mathbf{s}(\mathbf{R}\mathbf{R})\mathbf{e} (CC′)s((mm′)⋅IN(RR′)⋅A)s(mm′)⋅INs(RR′)e 同态乘法 C ∙ C ′ ( m ⋅ I N R ⋅ A ) ∙ ( m ′ ⋅ I N R ′ ⋅ A ) \mathbf{C}\bullet\mathbf{C} (m\cdot \mathbf{I}_N\mathbf{R} \cdot\mathbf{A})\bullet(m\cdot \mathbf{I}_N\mathbf{R} \cdot\mathbf{A}) C∙C′(m⋅INR⋅A)∙(m′⋅INR′⋅A) 通常记为 Flatten ( C ∙ C ′ ) \text{Flatten}(\mathbf{C} \bullet\mathbf{C}) Flatten(C∙C′)。 解密 由前面的解密步骤可知 C s m ⋅ Powersof2 ( s ) e ∗ \mathbf{C}\mathbf{s}m\cdot\text{Powersof2}(\mathbf{s})\mathbf{e}^* Csm⋅Powersof2(s)e∗所以如下解密 ( C ∙ C ′ ) s C ∙ ( m ′ ⋅ Powersof2 ( s ) e ′ ) m ′ C Powersof2 ( s ) C e ′ m ′ ( m Powersof2 ( s ) e ) C e ′ m ′ m Powersof2 ( s ) m ′ e C e ′ \begin{aligned} (\mathbf{C}\bullet\mathbf{C}) \mathbf{s}\\ \mathbf{C}\bullet (m \cdot \text{Powersof2}(\mathbf{s})\mathbf{e})\\ m\mathbf{C}\text{Powersof2}(\mathbf{s})\mathbf{C}\mathbf{e}\\ m(m\text{Powersof2}(\mathbf{s})\mathbf{e})\mathbf{C}\mathbf{e}\\ mm\text{Powersof2}(\mathbf{s})m\mathbf{e}\mathbf{C}\mathbf{e} \end{aligned} (C∙C′)sC∙(m′⋅Powersof2(s)e′)m′CPowersof2(s)Ce′m′(mPowersof2(s)e)Ce′m′mPowersof2(s)m′eCe′
当 m ′ e C e ′ ≤ ( N 1 ) E ( ( n 1 ) l 1 ) ⋅ 2 n B log q m\mathbf{e}\mathbf{C}\mathbf{e}\le (N1)E((n1)l1)\cdot 2nB\log q m′eCe′≤(N1)E((n1)l1)⋅2nBlogq时可解密成功。 经过深度为 L L L的电路计算后结果密文的噪声至多为 ( N 1 ) L E (N1)^LE (N1)LE。因此需满足一下条件才能正确解密 ( N 1 ) L E ( ( n 1 ) l 1 ) L ⋅ 2 n B log q q / 8 (N1)^L E((n1)l1)^L \cdot 2nB\log q q/8 (N1)LE((n1)l1)L⋅2nBlogqq/8 GSW 方案的主要缺点是较高的通信成本密文相对于对应的明文较大和计算复杂性。为了减少计算开销提出了各种优化方法以改进启动过程图7。
3.3.2 TRLWE18
TFHE: Fast Fully Homomorphic Encryption over the Torus
令 R Z [ x ] / ⟨ x d 1 ⟩ R \mathbb{Z}[x]/\langle x^d 1 \rangle RZ[x]/⟨xd1⟩。其中 d d d是2的幂次方。令 T R [ x ] / ⟨ x d 1 ⟩ m o d 1 T \mathbb{R}[x]/\langle x^d 1 \rangle \mod 1 TR[x]/⟨xd1⟩mod1和 R 2 F 2 [ x ] / ⟨ x d 1 ⟩ R_2 \mathbb{F}_2[x]/\langle x^d 1 \rangle R2F2[x]/⟨xd1⟩即 R 2 R_2 R2中的任何元素都是具有二进制系数的 R R R中的多项式。 TRLWE18方案构造如下 密钥生成 输入安全参数 λ \lambda λ输出小的私钥 s ∈ R 2 n \mathbf{s}\in R_2^n s∈R2n。 加密 输入私钥 s ∈ R 2 n \mathbf{s}\in R_2^n s∈R2n错误参数 α \alpha α和消息 m ∈ T m \in T m∈T。然后选择一个均匀随机的掩码 a ∈ T n a \in T^n a∈Tn并选择一个小的噪声 e ∈ χ e \in \chi e∈χ。其中 χ \chi χ 是一个B有界分布则密文为 c : ( a , b ) ( a , s ⋅ a m e ) ∈ T n × T \mathbf{c} : (\mathbf{a}, b)(\mathbf{a}, \mathbf{s} \cdot \mathbf{a} m e) \in T^n \times T c:(a,b)(a,s⋅ame)∈Tn×T 解密 输入私钥 s ∈ R 2 n s \in R_2^n s∈R2n和密文 c ∈ T n 1 \mathbf{c} \in T^{n1} c∈Tn1,计算密文 c \mathbf{c} c的秘密线性 κ \kappa κ-Lipschitz函数 φ s \varphi_s φs称为相位。该相位 φ s : T n × T → T \varphi_s:T^n \times T \to T φs:Tn×T→T 满足 φ s ( a , b ) b − s ⋅ a \varphi_s(\mathbf{a}, b) b - s \cdot \mathbf{a} φs(a,b)b−s⋅a 注意该函数由私钥 s ∈ R 2 n \mathbf{s} \in R_2^n s∈R2n参数化。相位 φ s ( c ) \varphi_\mathbf{s}(\mathbf{c}) φs(c)接近实际的消息 φ s ( c ) s ⋅ a m e − s ⋅ a m e \varphi_\mathbf{s}(\mathbf{c}) \mathbf{s} \cdot \mathbf{a} m e - \mathbf{s} \cdot \mathbf{a} m e φs(c)s⋅ame−s⋅ame 最后将 φ s ( c ) \varphi_s(c) φs(c) 四舍五入到消息空间 M ⊂ T M \subset T M⊂T 中的最近点。 同态密文的线性组合 设 c 1 , … , c p \mathbf{c}_1, \dots, \mathbf{c}_p c1,…,cp为 p p p个独立的密文具有相同的密钥 s \mathbf{s} s并且设 f 1 , … , f p f_1, \dots, f_p f1,…,fp为 R R R中的整数多项式。如下构造线性组合的密文 c ∑ i 1 p f i ⋅ c i \mathbf{c} \sum_{i1}^p f_i \cdot \mathbf{c}_i ci1∑pfi⋅ci 要求误差幅度保持小于 1 / 4 1/4 1/4 ∣ ∣ e ∣ ∣ ∞ ≤ 1 / 4 ||e||_{\infty} \leq 1/4 ∣∣e∣∣∞≤1/4。 解密 Dec s ( c ) ∑ i 1 p f i ⋅ Dec s ( c i ) \text{Dec}_\mathbf{s}(\mathbf{c})\sum_{i1}^p f_i \cdot \text{Dec}_\mathbf{s}(\mathbf{c}_i) Decs(c)i1∑pfi⋅Decs(ci)
密文可以线性组合从而得到一个新的密文解密后可以获得明文的线性组合。
3.4 第4代基于LWE和RLWE 图 8: 基于基于 LWE 和 RLWE 的第四代 FHE
3.4.1 CKKS16
Homomorphic Encryption for Arithmetic of Approximate Numbers
令 R Z [ x ] / ⟨ x d 1 ⟩ R \mathbb{Z}[x]/\langle x^d 1 \rangle RZ[x]/⟨xd1⟩ 且 d 2 M d 2^M d2M。对于基数 p p p、模 q 0 q_0 q0和自然数 L L L选择的层次令 q ℓ p ℓ ⋅ q 0 q_\ell p^\ell \cdot q_0 qℓpℓ⋅q0对于 ℓ 1 , … , L \ell 1, \ldots, L ℓ1,…,L。注意层次 ℓ \ell ℓ的密文是 R q ℓ R_{q_\ell} Rqℓ中的一个向量。考虑以下相关分布对于实数 σ \sigma σ D G ( σ 2 ) DG(\sigma^2) DG(σ2)是一个在 Z d \mathbb{Z}^d Zd上的离散高斯分布从独立的离散高斯分布中采样每个分量的方差为 σ 2 \sigma^2 σ2。对于 0 ⟨ ρ ⟨ 1 0 \langle \rho \langle 1 0⟨ρ⟨1的实数分布 Z O ( ρ ) ZO(\rho) ZO(ρ)是一个在 { − 1 , 0 , 1 } d \{-1, 0, 1\}^d {−1,0,1}d上的分布。其中 0 0 0的概率为 1 − ρ 1 - \rho 1−ρ而 − 1 -1 −1或 1 1 1的概率为 ρ 2 \frac{\rho}{2} 2ρ。最后 χ \chi χ是一个 B B B-有界分布。
层次型CKKS16方案构造如下 密钥生成 输入安全参数 λ \lambda λ选择 M M M、整数 h h h和 t t t以及实数 σ \sigma σ使得对关联的RLWE实例最佳攻击的复杂度为 2 λ 2^\lambda 2λ。私钥为 s k ( 1 , s ) sk (1, s) sk(1,s)。其中 s ∈ χ s \in \chi s∈χ。生成一个均匀随机的 a ∈ R q L a \in R_{q_L} a∈RqL并计算 b − a s e m o d q L b-as e \mod q_L b−asemodqL。其中 e e e 为 D G ( σ 2 ) DG(\sigma^2) DG(σ2)。最后采样 a ′ ∈ R t ⋅ q L a\in R_{t \cdot q_L} a′∈Rt⋅qL和 e ′ ∈ D G ( σ 2 ) e\in DG(\sigma^2) e′∈DG(σ2)并计算 b ′ − a s e ′ t s ′ m o d t ⋅ q L b -as e ts \mod t \cdot q_L b′−ase′ts′modt⋅qL。公钥为 p k ( b , a ) pk (b, a) pk(b,a)和评估密钥为 e v k ( b ′ , a ′ ) evk (b, a) evk(b′,a′)。 加密 消息为 m ∈ R m \in R m∈R公钥为 p k ( b , a ) ∈ R q L 2 pk(b,a) \in R_{q_L}^2 pk(b,a)∈RqL2随机选择 v ∈ Z O ( 1 / 2 ) v \in ZO(1/2) v∈ZO(1/2)和噪声 e 0 , e 1 ∈ D G ( σ 2 ) e_0, e_1 \in DG(\sigma^2) e0,e1∈DG(σ2)如下计算密文 c ( β , α ) v ( b , a ) ( m e 0 , e 1 ) m o d q ℓ ( v b m e 0 , v a e 1 ) m o d q ℓ . \mathbf{c} (\beta, \alpha) v(b,a) (m e_0, e_1) \mod q_\ell (vbm e_0,vae_1)\mod q_\ell. c(β,α)v(b,a)(me0,e1)modqℓ(vbme0,vae1)modqℓ. 解密 输入私钥 s k ( 1 , s ) sk (1, s) sk(1,s)和密文 c ∈ R q ℓ 2 \mathbf{c} \in R_{q_\ell}^2 c∈Rqℓ2如下计算 ⟨ c , s k ⟩ m o d q ℓ β α s m o d q ℓ v b m e 0 ( v a e 1 ) s m o d q ℓ v ( − a s e ) m e 0 ( v a e 1 ) s m o d q ℓ m v e e 0 e 1 s \begin{aligned} \langle \mathbf{c}, sk \rangle \mod q_\ell \\ \beta \alpha s \mod q_\ell \\ vbm e_0(vae_1)s\mod q_\ell \\ v(-ase)m e_0(vae_1)s\mod q_\ell \\ m ve e_0e_1s \end{aligned} ⟨c,sk⟩modqℓβαsmodqℓvbme0(vae1)smodqℓv(−ase)me0(vae1)smodqℓmvee0e1s 标量与密文乘法 输入标量 k k k和密文 c \mathbf{c} c直接乘 k c ( k β , k α ) k v ( b , a ) k ( m e 0 , e 1 ) m o d q ℓ ( k v b k m k e 0 , k v a k e 1 ) m o d q ℓ . k\mathbf{c} (k\beta, k\alpha) kv(b,a) k(m e_0, e_1) \mod q_\ell (kvbkm ke_0,kva ke_1)\mod q_\ell. kc(kβ,kα)kv(b,a)k(me0,e1)modqℓ(kvbkmke0,kvake1)modqℓ. 解密 ⟨ k c , s k ⟩ m o d q ℓ k β k α s m o d q ℓ k v b k m k e 0 k ( v a e 1 ) s m o d q ℓ k v ( − a s e ) k m k e 0 k ( v a e 1 ) s m o d q ℓ k m k v e k e 0 k e 1 s \begin{aligned} \langle k\mathbf{c}, sk \rangle \mod q_\ell \\ k\beta k\alpha s \mod q_\ell \\ kvbkm ke_0k(vae_1)s\mod q_\ell \\ kv(-ase)km ke_0k(vae_1)s\mod q_\ell \\ km kve ke_0ke_1s \end{aligned} ⟨kc,sk⟩modqℓkβkαsmodqℓkvbkmke0k(vae1)smodqℓkv(−ase)kmke0k(vae1)smodqℓkmkveke0ke1s 解密获得 k m km km。如果 k 10000 k10000 k10000则是扩大如果 k 1 / 10000 k1/10000 k1/10000则是缩小。注意直接缩小可能会与噪声重叠解密会出错。通常需要先放大后缩小才不会与噪声重叠。 同态加法 c c ′ ( ( v v ′ ) b ( m m ′ ) ( e 0 e 0 ′ ) , ( a a ′ ) a ( e 1 e 1 ′ ) ) m o d q ℓ \mathbf{c} \mathbf{c}((vv)b(mm) (e_0e_0),(aa)a(e_1e_1))\mod q_\ell cc′((vv′)b(mm′)(e0e0′),(aa′)a(e1e1′))modqℓ 解密 输入私钥 s k ( 1 , s ) sk (1, s) sk(1,s)和密文 c c ′ ∈ R q ℓ 2 \mathbf{c} \mathbf{c} \in R_{q_\ell}^2 cc′∈Rqℓ2如下计算 ⟨ ( c c ′ ) , s k ⟩ m o d q ℓ ( β β ′ ) ( α α ′ ) s m o d q ℓ ( v v ′ ) b ( m m ′ ) ( e 0 e 0 ′ ) ( a a ′ ) a s ( e 1 e 1 ′ ) s m o d q ℓ ( v v ′ ) ( − a s e ) ( m m ′ ) ( e 0 e 0 ′ ) ( a a ′ ) a s ( e 1 e 1 ′ ) s m o d q ℓ ( m m ′ ) ( v v ′ ) e ( e 0 e 0 ′ ) ( e 1 e 1 ′ ) s \begin{aligned} \langle (\mathbf{c} \mathbf{c}), sk \rangle \mod q_\ell \\ (\beta\beta) (\alpha\alpha) s \mod q_\ell \\ (vv)b(mm) (e_0e_0) (aa)as(e_1e_1)s\mod q_\ell \\ (vv)(-ase)(mm) (e_0e_0) (aa)as(e_1e_1)s\mod q_\ell \\ (mm) (vv)e (e_0e_0)(e_1e_1)s \end{aligned} ⟨(cc′),sk⟩modqℓ(ββ′)(αα′)smodqℓ(vv′)b(mm′)(e0e0′)(aa′)as(e1e1′)smodqℓ(vv′)(−ase)(mm′)(e0e0′)(aa′)as(e1e1′)smodqℓ(mm′)(vv′)e(e0e0′)(e1e1′)s 同态乘法 c ⋅ c ′ ( β , α ) ( β ′ , α ′ ) ( β β ′ , β α ′ , α β ′ , α α ′ ) ( d 0 , d 1 ) t − 1 d 2 e v k m o d q ℓ , \mathbf{c} \cdot \mathbf{c} (\beta, \alpha)(\beta, \alpha) (\beta\beta,\beta\alpha,\alpha\beta,\alpha\alpha) (d_0, d_1) t^{-1} d_2 evk \mod q_\ell, c⋅c′(β,α)(β′,α′)(ββ′,βα′,αβ′,αα′)(d0,d1)t−1d2evkmodqℓ, 使用密钥交换技术使得扩展密文 c ⋅ c ′ ( d 0 , d 1 , d 2 ) \mathbf{c} \cdot \mathbf{c} (d_0, d_1, d_2) c⋅c′(d0,d1,d2)变成正常密文 ( β ˉ , α ˉ ) (\bar{\beta}, \bar{\alpha}) (βˉ,αˉ)。 解密 如果是扩展密文 c ⋅ c ′ ( d 0 , d 1 , d 2 ) \mathbf{c} \cdot \mathbf{c} (d_0, d_1, d_2) c⋅c′(d0,d1,d2)则使用扩展私钥 ( 1 , s , s 2 ) (1,s,s^2) (1,s,s2)解密 如果是再线性化密文 ( β ˉ , α ˉ ) (\bar{\beta}, \bar{\alpha}) (βˉ,αˉ)则使用正常私钥 ( 1 , s ) (1, s) (1,s)解密通常是该情况使得加密生成的密文与经过同态计算的密文不可区分。
需要注意当我们有两个密文 c , c ′ \mathbf{c}, \mathbf{c} c,c′处于不同的级别 ℓ ′ ℓ \ell \ell ℓ′ℓ 时应该通过调整更高级别的密文的级别来匹配两个密文的级别即 ℓ ′ ℓ \ell \ell ℓ′ℓ。这可以通过重新缩放过程实现该过程将级别为 ℓ \ell ℓ 的密文 c ∈ R q ℓ 2 \mathbf{c} \in R_{q_\ell}^2 c∈Rqℓ2 转换为 c ′ ⌊ q ℓ ′ / q ℓ ⌉ m o d q ℓ ′ \mathbf{c} \lfloor q_{\ell} / q_\ell \rceil \mod q_{\ell} c′⌊qℓ′/qℓ⌉modqℓ′。
CKKS16特点 消息空间可以表示为扩展域 C C C中的元素。非正式地消息 m m m可以嵌入 S R [ x ] / ⟨ x d 1 ⟩ S R[x]/\langle x^d 1 \rangle SR[x]/⟨xd1⟩ 中。由于 x d 1 x^d 1 xd1的根是复数单位根若要将 m ∈ S m \in S m∈S转换为复数向量只需在这些复数根上对其进行求值。
第四代方案类似于第二代方案区别在第四代是近似计算能用于浮点数计算且计算速度显著提高。
3.4.2 CKKS16应用
CKKS16实现浮点计算 1.234 × 0.689 × 2.194 × 0.971 × 3.323 × 4.154 × 0.489 × 3.772 ? 1.234\times 0.689\times 2.194\times 0.971\times 3.323\times 4.154\times 0.489\times 3.772 ? 1.234×0.689×2.194×0.971×3.323×4.154×0.489×3.772? ChatGPT 4o: 46.03 46.03 46.03 Gork 2.0: 45.8 45.8 45.8 deepseek: 46.12 46.12 46.12
逐步计算并保留2位小数 1.23 × 0.68 × 2.19 × 0.91 × 3.32 × 4.15 × 0.48 × 3.77 41.62 1.23 \times 0.68 \times 2.19 \times 0.91 \times 3.32 \times 4.15 \times 0.48 \times 3.7741.62 1.23×0.68×2.19×0.91×3.32×4.15×0.48×3.7741.62
逐步计算并保留所有小数 1.23 ⋅ 0.68 ⋅ 2.19 ⋅ 0.91 ⋅ 3.32 ⋅ 4.15 ⋅ 0.48 ⋅ 3.77 41.5594574077313280 ≈ 41.56 1.23\cdot 0.68\cdot 2.19\cdot 0.91\cdot 3.32\cdot 4.15\cdot 0.48\cdot 3.77 41.5594574077313280\approx 41.56 1.23⋅0.68⋅2.19⋅0.91⋅3.32⋅4.15⋅0.48⋅3.7741.5594574077313280≈41.56
先放大再缩小 12340 ⋅ 6890 ⋅ 21940 ⋅ 9170 ⋅ 33230 ⋅ 41540 ⋅ 4890 ⋅ 37720 / 1000 0 8 4.361 ⋅ 1 0 33 / 1000 0 8 43.61 12340\cdot 6890\cdot 21940\cdot 9170\cdot 33230\cdot 41540\cdot 4890\cdot 37720 / {10000^8}4.361\cdot {10^{33}}/{10000^8} 43.61 12340⋅6890⋅21940⋅9170⋅33230⋅41540⋅4890⋅37720/1000084.361⋅1033/10000843.61
方法 先放大再计算再缩小最终结果则能获得准确值。 消息1.234扩大12340然后加密然后同态乘法然后解密然后缩小10000获得1.234。加密和解密过程中的噪声对放大的消息影响较小。
缩减技术 CKKS16的密文能够乘以常量 1 / p 1/p 1/p实现对应明文数据的缩小用于缩小噪声。 图 9: 近似同态计算
参考文献 GGH公钥密码系统 Public-key cryptosystems from lattice reduction problems Regev05论文On Lattices, Learning with Errors, Random Linear Codes, and Cryptography Brakerski12论文Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP Micciancio-Regev书 Lattice-based cryptography KTX07论文Multi-bit Cryptosystems Based on Lattice Problems DGHV10论文Fully homomorphic encryption over the integers LV10论文On Ideal Lattices and Learning with Errors over Rings Gentry09论文Fully homomorphic encryption using ideal lattices CR16论文Recovering Short Generators of Principal Ideals in Cyclotomic Rings BV11论文Efficient Fully Homomorphic Encryption from (Standard)LWE LTV13论文On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption GSW13论文Homomorphic Encryption from Learning with Errors:Conceptually-Simpler, Asymptotically-Faster, Attribute-Based TRLWE18论文TFHE: Fast Fully Homomorphic Encryption over the Torus 陈智罡 全同态加密从理论到实践 周福才、徐剑 格理论与密码学 Google Jeremy Kun 2024.5博客 A High-Level Technical Overview of Fully Homomorphic Encryption Optalysys团队2024年10月博客 Fully Homomorphic Encryption industry leaders join forces to form global FHE Hardware Consortium Fhenix团队2023年10月17日博客 The Holy Grail of Encryption: The Rise of FHE Technology NGC Ventures团队2024年1月12日博客 Introduction to FHE and Blockchain: Implications for Scalability and Privacy Awesome Fully Homomorphic Encryption (FHE) x Blockchain resources, libraries, projects, and more Awesome Homomorphic Encryption PANews 2024年9月17日文章 全同态加密FHE的进展与应用 2022年论文《Survey on Fully Homomorphic Encryption, Theory, and Applications》 Craig Gentry 2022年论文《Homomorphic encryption: a mathematical survey》 2024年12月20日Jorge MyszneNiobium Microsystems 首席产品官 博客 3 Homomorphic Encryption Trends for 2025 HCLTech团队2024年6月研报 Homomorphic encryption: Exploring technology trends and future approach 2024年论文《vFHE: Verifiable Fully Homomorphic Encryption》 PPS Lab团队2023年10月博客 Arithmetizing FHE in Circom PPS Lab团队2023年10月博客 A primer on the FHEW TFHE schemes 2024年论文《Oraqle: A Depth-Aware Secure Computation Compiler》 2023年10月论文《A Survey on Implementations of Homomorphic Encryption Schemes》 Sunscreen团队2021年8月博客 An Intro to Fully Homomorphic Encryption for Engineers TFHE2016年论文《Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds》 BGV2011年论文 《Fully Homomorphic Encryption without Bootstrapping》 BFV2012年论文《Somewhat Practical Fully Homomorphic Encryption》 CKKS2016年论文《Homomorphic Encryption for Arithmetic of Approximate Numbers》 HomomorphicEncryption.org 2018年slide Building Applications with Homomorphic Encryption Greenfield Capital 2024年7月博客 The muted Seven – 7 things you should consider re confidential compute Sunscreen 2023年8月博客 How SNARKs fall short for FHE 2024年4月18日BigBrainVC团队博客 Flawed Homomorphic Encryption 2024年Verisense Network slide An Introduction To FHE and Its Application in Rust Vitalik 2020年7月20日博客 Exploring Fully Homomorphic Encryption 2023年论文《Verifiable Fully Homomorphic Encryption》 2018年《Homomorphic Encryption Standard v1.1》 2021年论文《SoK: Fully Homomorphic Encryption Compilers》 2024年论文《SoK: Fully Homomorphic Encryption Accelerators》 Sunscreen团队2023年5月博客 Building an FHE compiler for the real world Zama团队2023年5月23日博客 Private Smart Contracts Using Homomorphic Encryption Craig Gentry 2024年6月分享视频 FHE: Past, Present and Future
