福建网站建设优化,石家庄市住建局官网,长沙网站seo诊断,免费开源网站CKKS EXPLAINED, PART 3: ENCRYPTION AND DECRYPTION
Introduction
在之前的文章中#xff0c;CKKS解释了第二部分#xff1a;完整的编码和解码#xff0c;我们看到了如何实现CKKS的编码器和解码器#xff0c;这使我们能够将向量转换为多项式#xff0c;反之亦然。这一步…CKKS EXPLAINED, PART 3: ENCRYPTION AND DECRYPTION
Introduction
在之前的文章中CKKS解释了第二部分完整的编码和解码我们看到了如何实现CKKS的编码器和解码器这使我们能够将向量转换为多项式反之亦然。这一步骤是必要的因为我们将看到与直接使用向量相比使用多项式来构建同态加密方案要高效得多。
在本文中我们将看到如何利用困难问题如LWE或RLWE来构建一个近似同态加密方案。CKKS使用近似算术而不是精确算术这意味着一旦我们完成计算我们可能会得到一个略有不同于直接进行计算的结果。这意味着如果您加密了2和3将它们的密文相加然后解密您可能会得到类似于4.99或5.01但不是5的结果。而其他方案如BFV是精确的这意味着它们将产生确切的5。
那么为什么要使用CKKS呢CKKS更适用于实数上的算术运算其中我们可以得到近似但接近的结果而BFV更适用于整数上的算术运算。
在本文中我们将看到如何利用LWE和RLWE实现近似算术同态加密方案的加密和解密过程。
Learning with Error
CKKS是一种公钥加密方案其中生成了一个秘钥对包括一个私钥和一个公钥。公钥用于加密并可以共享而私钥用于解密并必须保密。
LWELearning With Error是CKKS的基础也是许多其他同态加密方案的基础之一。LWE问题最初由Regev在论文《On lattices, learning with errors, random linear codes, and cryptography》中引入。LWE问题是要区分形式为 ( a i , b i ) ( a i , ⟨ a i , s ⟩ e i ) (a_i, b_i) (a_i, \langle a_i, s \rangle e_i) (ai,bi)(ai,⟨ai,s⟩ei) 的带噪声对和 Z q n × Z q \mathbb{Z}_q^n\times\mathbb{Z}_q Zqn×Zq中真正随机的对。这里 a i , s ∈ Z q n a_i, s \in \mathbb{Z}_q^n ai,s∈Zqn a i a_i ai 是均匀采样的 s s s 是我们的秘密 e i ∈ Z q e_i \in \mathbb{Z}_q ei∈Zq 是小的噪声通常是高斯分布的用于增加问题的难度。如果不引入 e i e_i ei解决这个线性系统将会变得容易得多因为我们可以使用高斯消元法来解决线性系统。 Z q n × Z q \mathbb{Z}_q^n\times\mathbb{Z}_q Zqn×Zq 表示一个元素由两部分组成的集合其中第一部分是长度为 n n n 的整数向量每个分量都来自于模 q q q 的整数集合 Z q \mathbb{Z}_q Zq第二部分是一个整数同样来自于模 q q q 的整数集合 Z q \mathbb{Z}_q Zq。
具体来说 Z q n × Z q \mathbb{Z}_q^n\times\mathbb{Z}_q Zqn×Zq 可以表示为 Z q n × Z q { ( x 1 , x 2 , … , x n , y ) ∣ x i ∈ Z q , y ∈ Z q } \mathbb{Z}_q^n\times\mathbb{Z}_q \{(x_1, x_2, \ldots, x_n, y) \mid x_i \in \mathbb{Z}_q, y \in \mathbb{Z}_q\} Zqn×Zq{(x1,x2,…,xn,y)∣xi∈Zq,y∈Zq}
其中 x 1 , x 2 , … , x n x_1, x_2, \ldots, x_n x1,x2,…,xn 是整数向量的分量每个分量都来自于模 q q q 的整数集合 Z q \mathbb{Z}_q Zq y y y 是一个整数同样来自于模 q q q 的整数集合 Z q \mathbb{Z}_q Zq。
LWE问题的目标是区分形式为 ( a i , b i ) ( a i , ⟨ a i , s ⟩ e i ) (a_i, b_i) (a_i, \langle a_i, s \rangle e_i) (ai,bi)(ai,⟨ai,s⟩ei) 的带噪声对和 Z q n × Z q \mathbb{Z}_q^n\times\mathbb{Z}_q Zqn×Zq中真正随机的对。
在LWE问题中我们有一组带噪声的对 ( a i , b i ) (a_i, b_i) (ai,bi)其中 a i a_i ai 是长度为 n n n 的向量 b i b_i bi 是一个整数。这些带噪声的对是通过选择秘密向量 s s s生成矩阵 A ( a 1 , … , a m ) A(a_1,\ldots,a_m) A(a1,…,am)并添加噪声项 e i e_i ei 来构造的。
对于每个带噪声的对 ( a i , b i ) (a_i, b_i) (ai,bi)其中 a i a_i ai 是随机选择的向量 b i b_i bi 是通过将 a i a_i ai 与秘密向量 s s s 的内积加上噪声项 e i e_i ei 计算得到的。噪声项 e i e_i ei 是从特定分布中生成的随机数通常是一个小的扰动项。
与此相对 Z q n × Z q \mathbb{Z}_q^n\times\mathbb{Z}_q Zqn×Zq 表示一个集合其中元素是由长度为 n n n 的向量和一个整数组成的对。在这个集合中向量和整数的取值是完全独立的没有任何关联性。
LWE问题的目标是通过观察一组带噪声的对 ( a i , b i ) (a_i, b_i) (ai,bi) 来区分它们是否是由秘密向量 s s s 生成的。换句话说我们需要确定给定的带噪声对是来自于LWE构造还是来自于纯随机的对。这种区分能力是LWE问题的核心而解决LWE问题的算法将能够从带噪声的对中恢复出秘密向量 s s s 的近似。
example
假设我们有一个模数 q 7 q 7 q7向量维度 n 3 n 3 n3并且我们希望生成一个带噪声的对 ( a i , b i ) (a_i, b_i) (ai,bi)其中 a i a_i ai 是长度为 n n n 的向量 b i b_i bi 是一个整数。
首先我们随机选择一个秘密向量 s ( 2 , 4 , 1 ) s (2, 4, 1) s(2,4,1)其中每个分量都来自于模 q q q 的整数集合 Z q \mathbb{Z}_q Zq。然后我们生成一个噪声项 e i e_i ei该项满足特定的噪声分布。在这个例子中我们假设 e i e_i ei 是从均值为0、方差为2的离散高斯分布中生成的。
现在我们生成带噪声的对 ( a i , b i ) (a_i, b_i) (ai,bi)。对于每个 i i i我们随机选择向量 a i a_i ai其中每个分量 a i , j a_{i,j} ai,j 都是从模 q q q 的整数集合 Z q \mathbb{Z}_q Zq 中随机选择的。然后我们计算 b i ⟨ a i , s ⟩ e i b_i \langle a_i, s \rangle e_i bi⟨ai,s⟩ei其中 ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨⋅,⋅⟩ 表示向量的内积。
让我们通过一个具体的例子来说明
假设我们生成的随机向量 a i a_i ai 如下 a 1 ( 3 , 6 , 4 ) a_1 (3, 6, 4) a1(3,6,4) a 2 ( 2 , 3 , 5 ) a_2 (2, 3, 5) a2(2,3,5)
对于这两个向量我们计算相应的 b i b_i bi b 1 ⟨ a 1 , s ⟩ e 1 ( 3 ⋅ 2 6 ⋅ 4 4 ⋅ 1 ) e 1 29 e 1 b_1 \langle a_1, s \rangle e_1 (3 \cdot 2 6 \cdot 4 4 \cdot 1) e_1 29 e_1 b1⟨a1,s⟩e1(3⋅26⋅44⋅1)e129e1 b 2 ⟨ a 2 , s ⟩ e 2 ( 2 ⋅ 2 3 ⋅ 4 5 ⋅ 1 ) e 2 23 e 2 b_2 \langle a_2, s \rangle e_2 (2 \cdot 2 3 \cdot 4 5 \cdot 1) e_2 23 e_2 b2⟨a2,s⟩e2(2⋅23⋅45⋅1)e223e2
在这个例子中 e 1 e_1 e1 和 e 2 e_2 e2 是从离散高斯分布中生成的随机噪声项。
这样我们就得到了两个带噪声的对 ( a 1 , b 1 ) (a_1, b_1) (a1,b1) 和 ( a 2 , b 2 ) (a_2, b_2) (a2,b2)其中 a 1 , a 2 a_1, a_2 a1,a2 是长度为 3 的向量 b 1 , b 2 b_1, b_2 b1,b2 是整数。通过解决LWE问题我们的目标是从这些带噪声的对中学习到秘密向量 s s s 的近似。
LWE问题被认为与最坏情况的格问题一样困难目前对来自量子计算机的攻击是安全的。因此我们可以利用从 ( a i , ⟨ a i , s ⟩ e i ) (a_i,\langle a_i, s \rangle e_i) (ai,⟨ai,s⟩ei) 对中找到秘密 s s s 的难度并基于此构建一个加密系统。
假设我们已生成了一个保密的秘钥 s ∈ Z q n s \in \mathbb{Z}_q^n s∈Zqn并发布了 n n n 对形式为 ( a i , ⟨ a i , s ⟩ e i ) (a_i,\langle a_i, s \rangle e_i) (ai,⟨ai,s⟩ei) 的对可以写成矩阵形式为 ( A , A ⋅ s e ) (A,A \cdot s e) (A,A⋅se)其中 A ∈ Z q n × n A\in\mathbb{Z}_q^{n\times n} A∈Zqn×n e ∈ Z q n e \in \mathbb{Z}_q^n e∈Zqn。正如LWE问题所述从这个对中恢复秘密钥是困难的因此我们可以利用它来创建一个公钥。
实际上我们将使用 p ( − A ⋅ s e , A ) p(-A \cdot s e,A) p(−A⋅se,A) 作为我们的公钥可以公开使用因为很难从中提取出秘密钥。我们选择存储 − A ⋅ s -A \cdot s −A⋅s 而不是 A ⋅ s A \cdot s A⋅s 是为了方便但这并不改变问题。
然后为了使用公钥和私钥加密和解密一个消息 μ ∈ Z q n \mu \in \mathbb{Z}_q^n μ∈Zqn我们可以使用以下方案
使用公钥 p p p对 μ \mu μ进行加密输出 c ( μ , 0 ) p ( μ − A ⋅ s e , A ) ( c 0 , c 1 ) c (\mu, 0) p (\mu - A \cdot s e, A) (c_0, c_1) c(μ,0)p(μ−A⋅se,A)(c0,c1)。使用私钥 s s s对 c c c进行解密输出 μ ~ c 0 c 1 . s μ − A . s e A . s μ e ≈ μ \tilde{\mu}c_0c_1.s\mu-A.seA.s\mue\approx\mu μ~c0c1.sμ−A.seA.sμe≈μ。
因此在加密阶段我们使用公钥来对消息 μ \mu μ进行掩码。因此消息被隐藏在密文的第一个坐标中使用了掩码 − A ⋅ s -A \cdot s −A⋅s。请记住 A A A是均匀采样的因此它确实会有效地掩盖 μ \mu μ。要移除掩码我们可以使用 c c c的第二个坐标其中仅存储了 A A A并将其与私钥 s s s结合以获得解密结果 μ e \mu e μe。注意这里我们并没有得到原始消息 μ \mu μ而是 μ \mu μ加上一些噪音 e e e这就是为什么我们说我们有一个近似算术方案。如果 e e e足够小那么解密结果将接近于原始的 μ \mu μ。
因此我们已经看到如何利用 LWE 问题构建一个安全防御量子攻击的公共加密方案。上述实现的问题在于虽然秘密密钥的大小为 O ( n ) \mathcal{O}(n) O(n)但由于矩阵 A A A的存在公钥的大小为 O ( n 2 ) \mathcal{O}(n^2) O(n2)并且计算也需要 O ( n 2 ) \mathcal{O}(n^2) O(n2)次操作。因为 n n n将决定我们方案的安全性如果我们使用 LWE 构建我们的方案它在实践中将会太低效因为密钥的 O ( n 2 ) \mathcal{O}(n^2) O(n2)大小和复杂度将使其太不实际。
Ring Learning with Error
因此我们将考虑《On Ideal Lattices and Learning with Errors Over Rings》中介绍的Ring Learning With ErrorRLWE问题它是LWE在环上的一种变体。我们不再使用 Z q n \mathbb{Z}_q^n Zqn中的向量而是在 Z q [ X ] / ( X N 1 ) \mathbb{Z}_q[X]/(X^N1) Zq[X]/(XN1)中使用多项式进行计算这里假设 N N N是2的幂。现在我们从 Z q [ X ] / ( X N 1 ) \mathbb{Z}_q[X]/(X^N1) Zq[X]/(XN1)中随机选择多项式 a a a、 s s s和 e e e其中 a a a仍然是均匀采样的 s s s是一个小的秘密多项式 e e e是一个小的噪声多项式。转向RLWE有两个主要优势
密钥大小不再是二次的而是线性的因为我们现在输出公钥 p ( − a ⋅ s e , a ) p(-a\cdot se,a) p(−a⋅se,a)其中 a ⋅ s a\cdot s a⋅s表示 a a a与 s s s的多项式乘积。由于所有操作都是在多项式之间进行的私钥和公钥的大小都是 O ( n ) \mathcal{O}(n) O(n)。乘法是在多项式上进行的因此可以使用离散傅立叶变换进行多项式乘法复杂度为 O ( n log ( n ) ) \mathcal{O}(n\log(n)) O(nlog(n))而不是 O ( n 2 ) \mathcal{O}(n^2) O(n2)因为我们需要进行矩阵-向量乘法。
因此通过使用RLWE而不是LWE我们可以获得更小的密钥并且操作速度更快因此前面的方案变得更加实用。此外RLWE仍然是一个困难问题并提供强大的安全性保证因此使用RLWE仍然提供了一个安全的方案。
现在我们明白了为什么使用多项式是重要的因为它们为高效和安全的方案提供了基础。因此现在你可以理解为什么我们要费力地将向量转换为 Z q [ X ] / ( X N 1 ) \mathbb{Z}_q[X]/(X^N1) Zq[X]/(XN1)中的多项式反之亦然因为我们现在可以利用多项式环的代数结构。
假设我们有一个RLWE方案其中我们在环 Z q [ X ] / ( X 4 1 ) \mathbb{Z}_q[X]/(X^4 1) Zq[X]/(X41)上进行计算 q q q是我们的模量。我们希望生成一个公钥和一个私钥来加密和解密消息。 密钥生成 我们首先随机选择一个小的秘密多项式 s 3 X 2 2 X 1 s 3X^2 2X 1 s3X22X1 和一个小的噪声多项式 e X 3 X 2 2 X 1 e X^3 X^2 2X 1 eX3X22X1。 然后我们随机选择一个多项式 a X 3 2 X 2 X 1 a X^3 2X^2 X 1 aX32X2X1这个多项式仍然是均匀采样的。 我们计算公钥 p ( − a ⋅ s e , a ) p (-a \cdot s e, a) p(−a⋅se,a)。首先计算 − a ⋅ s − ( X 3 2 X 2 X 1 ) ⋅ ( 3 X 2 2 X 1 ) -a \cdot s -(X^3 2X^2 X 1) \cdot (3X^2 2X 1) −a⋅s−(X32X2X1)⋅(3X22X1)得到 − a ⋅ s − 3 X 5 − 5 X 4 − 3 X 3 − X 2 − 2 X − 1 -a \cdot s -3X^5 - 5X^4 - 3X^3 - X^2 - 2X - 1 −a⋅s−3X5−5X4−3X3−X2−2X−1然后加上噪声多项式 e e e得到 − a ⋅ s e − 3 X 5 − 5 X 4 − 3 X 3 − 2 X 2 − X -a \cdot s e -3X^5 - 5X^4 - 3X^3 - 2X^2 - X −a⋅se−3X5−5X4−3X3−2X2−X。公钥 p p p 就是这个结果和 a a a 的组合即 p ( − 3 X 5 − 5 X 4 − 3 X 3 − 2 X 2 − X , X 3 2 X 2 X 1 ) p (-3X^5 - 5X^4 - 3X^3 - 2X^2 - X, X^3 2X^2 X 1) p(−3X5−5X4−3X3−2X2−X,X32X2X1)。 加密 假设我们有一个消息 μ 2 X 2 X 1 \mu 2X^2 X 1 μ2X2X1我们希望将其加密。我们随机选择一个小的噪声多项式 e ′ X 2 1 e X^2 1 e′X21。 我们计算密文 c ( μ − a ⋅ s e ′ , a ) c (\mu - a \cdot s e, a) c(μ−a⋅se′,a)。首先计算 μ − a ⋅ s ( 2 X 2 X 1 ) − ( X 3 2 X 2 X 1 ) ⋅ ( 3 X 2 2 X 1 ) \mu - a \cdot s (2X^2 X 1) - (X^3 2X^2 X 1) \cdot (3X^2 2X 1) μ−a⋅s(2X2X1)−(X32X2X1)⋅(3X22X1)得到 μ − a ⋅ s − 3 X 6 − 3 X 5 − 2 X 4 − 2 X 3 − X 2 \mu - a \cdot s -3X^6 - 3X^5 - 2X^4 - 2X^3 - X^2 μ−a⋅s−3X6−3X5−2X4−2X3−X2然后加上噪声多项式 e ′ e e′得到 μ − a ⋅ s e ′ − 3 X 6 − 3 X 5 − 2 X 4 − X 3 − X 2 1 \mu - a \cdot s e -3X^6 - 3X^5 - 2X^4 - X^3 - X^2 1 μ−a⋅se′−3X6−3X5−2X4−X3−X21。密文 c c c 就是这个结果和 a a a 的组合即 c ( − 3 X 6 − 3 X 5 − 2 X 4 − X 3 − X 2 1 , X 3 2 X 2 X 1 ) c (-3X^6 - 3X^5 - 2X^4 - X^3 - X^2 1, X^3 2X^2 X 1) c(−3X6−3X5−2X4−X3−X21,X32X2X1)。 解密 使用私钥 s s s 对密文 c c c 进行解密。解密过程为 μ ′ c 0 c 1 ⋅ s \mu c_0 c_1 \cdot s μ′c0c1⋅s。将 c 0 c_0 c0 替换为 − 3 X 6 − 3 X 5 − 2 X 4 − X 3 − X 2 1 -3X^6 - 3X^5 - 2X^4 - X^3 - X^2 1 −3X6−3X5−2X4−X3−X21 c 1 c_1 c1 替换为 X 3 2 X 2 X 1 X^3 2X^2 X 1 X32X2X1 s s s 替换为 3 X 2 2 X 1 3X^2 2X 1 3X22X1。进行多项式乘法和加法后得到解密结果 μ ′ 2 X 2 X 1 \mu 2X^2 X 1 μ′2X2X1与原始消息 μ \mu μ 相同。
这是一个简化的RLWE示例演示了如何生成密钥、加密消息和解密密文。 RLWE的优势在于密钥的大小更小并且可以使用更高效的乘法操作进行计算。
Homomorphic operations
现在我们已经了解了为什么要在 Z q [ X ] / ( X N 1 ) \mathbb{Z}_q[X]/(X^N1) Zq[X]/(XN1)的多项式上工作以及如何基于此构建加密方案让我们看看如何定义密文上的加法和乘法以实现同态加密方案。
我们说过我们有一个秘密 s s s和一个公钥 p ( b , a ) ( − a ⋅ s e , a ) p(b,a)(-a\cdot se,a) p(b,a)(−a⋅se,a)。要加密一个消息 μ \mu μ我们简单地输出 c ( μ b , a ) c(\mub,a) c(μb,a)而要使用 s s s解密它我们评估 c 0 c 1 ⋅ s c_0c_1\cdot s c0c1⋅s这将近似地给出原始消息。
Addition
假设我们有两个消息 μ \mu μ 和 μ ′ \mu μ′并将它们加密为 c ( c 0 , c 1 ) c(c_0,c_1) c(c0,c1) 和 c ′ ( c 0 ′ , c 1 ′ ) c(c_0,c_1) c′(c0′,c1′)。那么 c add c c ′ ( c 0 c 0 ′ , c 1 c 1 ′ ) c_{\text{add}}cc(c_0c_0,c_1c_1) caddcc′(c0c0′,c1c1′) 就是 μ μ ′ \mu\mu μμ′ 的正确加密结果。也就是说当我们使用秘密 s s s 进行解密时我们会得到近似地 μ μ ′ \mu\mu μμ′。
确切地说对 c add c_{\text{add}} cadd 的解密过程为 c add , 0 c add , 1 ⋅ s c 0 c 0 ′ ( c 1 c 1 ′ ) ⋅ s c 0 c 1 ⋅ s c 0 ′ c 1 ′ ⋅ s μ μ ′ 2 e ≈ μ μ ′ c_{\text{add},0}c_{\text{add},1}\cdot sc_0c_0(c_1c_1)\cdot sc_0c_1\cdot sc_0c_1\cdot s \mu\mu2e\approx\mu\mu cadd,0cadd,1⋅sc0c0′(c1c1′)⋅sc0c1⋅sc0′c1′⋅sμμ′2e≈μμ′。这里我们假设 e e e 是可以忽略的。
这意味着如果你对密文进行加法操作并将其解密你将得到明文的加法结果这意味着通过这个简单的方案你可以允许某人在加密的数据上进行加法操作而用户仍然可以解密它并得到正确的结果。这是我们朝着同态加密方案迈出的第一步。
Multiplication
然而我们仍然需要定义密文上的乘法这更加复杂。事实上我们的目标是找到一个密文 c mult c_{\text{mult}} cmult当我们用秘密密钥 s s s 进行解密时我们得到明文的乘积。
由于两个密文的乘法更加复杂我们现在将重点放在将密文与明文相乘上并在以后的文章中看看如何在密文之间进行乘法运算。
假设我们有一个明文 μ \mu μ加密为密文 c ( c 0 , c 1 ) c(c_0,c_1) c(c0,c1)以及另一个明文 μ ′ \mu μ′。那么要获得乘法的密文我们只需要输出 c mult ( μ ′ ⋅ c 0 , μ ′ ⋅ c 1 ) c_{\text{mult}}(\mu\cdot c_0,\mu\cdot c_1) cmult(μ′⋅c0,μ′⋅c1)。
确实当解密 c mult c_{\text{mult}} cmult 时我们得到 μ ′ ⋅ c 0 μ ′ ⋅ c 1 ⋅ s μ ′ ⋅ ( c 0 c 1 ⋅ s ) μ ′ ⋅ ( μ e ) μ ′ ⋅ μ μ ′ ⋅ e ≈ μ ′ ⋅ μ \mu\cdot c_0\mu\cdot c_1\cdot s\mu\cdot (c_0c_1\cdot s)\mu\cdot (\mue)\mu\cdot \mu\mu\cdot e\approx\mu\cdot \mu μ′⋅c0μ′⋅c1⋅sμ′⋅(c0c1⋅s)μ′⋅(μe)μ′⋅μμ′⋅e≈μ′⋅μ。
因此通过这种加法和乘法的实现我们已经看到可以加密一些数据对其进行操作然后解密后得到与对明文数据进行计算相同的结果。
由于我们还有一些其他概念要解决例如密文-密文乘法、重线性化和重新缩放我们暂时不会涵盖代码实现。一旦我们掌握了所有的基本组件我们将把一切都组合在一起构建一个端到端的近似同态加密方案类似于CKKS
所以我希望你理解了如何使用RLWE构建同态加密方案并且下一步是密文-密文乘法
