专业定制网站,注册个网站要多少钱,平面设计师个人网站,管理咨询和战略咨询本文主要为翻译内容#xff0c;原文地址#xff1a;Introduction to the BFV encryption scheme、https://www.inferati.com/blog/fhe-schemes-bgv 之前的一篇博客我们翻译了CKKS全同态加密方案的内容#xff0c;但该篇上下文中有一些知识要点#xff0c;作者在BFV/BGV中已… 本文主要为翻译内容原文地址Introduction to the BFV encryption scheme、https://www.inferati.com/blog/fhe-schemes-bgv 之前的一篇博客我们翻译了CKKS全同态加密方案的内容但该篇上下文中有一些知识要点作者在BFV/BGV中已经做了讲解所以做了省略为了补齐这部分知识我们今天将这两篇的内容结合到一篇进行更全面的阐述。 BGV和BFV是“算术FHE”系列中的两种方案。自2011年/2012年首次发表以来的十年里BGV和BFV已经进行了调整和重新分析并被确定为基本上是等效的其在实现、效率和噪声传播方面存在细微差异因不同参数选择而异。并且方案的许多高级技巧也被用于CKKS。 1、介绍 Fan-VercauterenFV方案[Bra12, FV12]也称为 Brakerski-Fan-VercauterenBFV方案被认为是第二代全同态加密FHE方案之一它是基于带错误学习环RLWE问题构建的[LPR13]。BrakerskiGentry-Vaikuntanathan BGV [BGV14] 方案是另一种基于错误环学习的密码系统可提供对加密数据的计算。BGV 和 BFV 提供相同的功能即对整型消息进行精确计算但是它们的构造存在一些差异。 BFV 在两个环上实例化明文环包括未加密或可理解消息的编码密文环包括加密消息。与任何其他全同态加密方案类似BFV 允许不可信方在无法访问解密密钥的情况下对加密数据进行有意义的计算。这是由于同态属性使得在明文和密文空间之间存在一个映射或函数该映射保留了这两个空间中的运算。 BGV 与 BFV 方案类似也定义了明文环和密文环。加密过程将明文环中的输入明文元素映射到密文环中的密文元素。广义地讲加密是通过使用几乎随机的掩码隐藏明文消息来实现的该掩码是使用公钥或对称密钥操作模式下的私钥计算得出的。加密的输出通常是密文空间的两个元素第一个元素包含被掩码的明文数据而第二个元素包含可在解密过程中使用的辅助信息。解密使用私钥和密文中的辅助信息来移除掩码并恢复明文消息。对于熟悉 ElGamal 加密将单个明文元素映射到成对密文元素的读者来说这可能听起来很熟悉。 在基于环上带误差学习的全同态加密方案中一个关键概念是误差也称为噪声它在加密过程中被添加到明文消息中。该误差对于满足RLWE困难性假设至关重要否则RLWE将变成一个可以由商用计算机解决的简单计算问题其结果是基于此类简单问题构建的全同态方案将容易被攻破。同时当我们执行同态计算主要是同态加法和同态乘法时误差幅度会增大。且同态乘法产生的误差增长速度比同态加法产生的误差增长速度比快。 到目前为止我们讨论了BFV和BGV之间的相似之处。在接下来的段落中我们将描述这两种方案的不同之处。首先BFV方案通常是尺度不变或尺度无关的也就是说在同态计算过程中密文模数不会改变。另一方面BGV是一种尺度相关的方案它定义了多个密文模数每个层级有一个模数。正如我们在图1中看到的BGV定义了一系列“小”模数链。每个层级相关联的是一个密文大模数 。请注意小模数 的选择以及大模数 的集合不是任意的其背后的原理将在本文后面阐述。在执行同态计算时密文不断从一个层级移动到另一个层级。密文的典型流程如下一个新加密的密文从层级 开始我们将其称为用于演示的加密层级。当我们对密文进行计算时它从较高层级 移动到较低层级 。最终在解密之前密文处于层级1。应该指出的是上述向下受限的流程是BGV分层版本中的典型流程。在可自举的 BGV 中密文可以根据需要在两个方向向上或向下移动。 图1. 尺度相关的BGV密文模数 我们注意到前面关于加密和解密具有固定层级的描述是相当简化的因为在的任何层级进行加密或解密都是可能的。还应当指出的是BFV方案也可以实例化为尺度相关的方案这使得这两种方案之间的这种差异存在争议。 BFV和BGV之间另一个争议较小的区别在于密文结构以及明文消息的加密方式。图2展示了BFV和BGV的密文结构。在BFV中明文消息被放置在密文系数的最高有效位MSB一侧。这是通过在加密过程中用相当大的值 对消息进行缩放来实现的。另一方面BGV将消息放置在密文系数的最低有效位LSB一侧。重要的是在同态计算过程中明文和噪声永远不会重叠以便解密能够恢复预期的计算结果。 图 2. BFV 和 BGV 中的密文结构 MSB 代表最高有效位q 是密文模数t 是明文模数。摘自 [CKKS17] 2、明文空间和密文空间 BFV中的明文和密文空间是在两个不同的多项式环上定义的分别记为和其中 是环的维度 以及分别是明文和密文的系数模数。记号可以看作是整数系数模 和的多项式集合即系数在中且次数小于 n。出于效率考虑n通常设置为2的幂次方整数。注意在实际应用中 q通常远大于t因此 C的基数远大于P的基数这也意味着P中的一个明文消息M可以映射到C中的多个有效密文。 和中的阶或不同元素的数量分别为 和 。
表1展示了参数n 4和t 5时的有效明文消息示例。 BGV的明文和密文空间与BFV中的类似。明文多项式环定义为即次数小于n且系数在中的多项式集合其中明文模数t和环维度n均为整数。密文多项式环定义为其中 是 l 层的密文模数。出于效率考虑n通常像我们在BFV讨论中那样被设置为2的幂整数。此外 q通常远大于t这会影响加密后的消息扩展率。 BFV的明文空间为密文格式为 BGV的明文空间为密文格式为。 3、参数 我们在此描述BFV中使用的主要参数。除了在第3节中介绍的明文和密文空间参数之外BFV还使用了一些随机分布: 、、【随机分布可参考《CKKS全同态加密方案浅析》关于参数的介绍】。 我们注意到参数的选择是特定于应用场景的并且也由所需的安全级别驱动。对于一组当前被接受的参数我们建议读者参考同态加密标准中的表1和表2。 https://homomorphicencryption.org/wp-content/uploads/2018/11/HomomorphicEncryptionStandardv1.1.pdf 4、编码和解码 BFV和BGV在编码上类似回想一下明文空间是多项式环。这意味着消息需要被转换为中的多项式。这种转换被称为编码。文献中包含了许多为全同态加密提出的编码方案。我们在这里回顾两种针对整数数据类型的简单方案。 设 m 表示我们想要在全同态加密中加密的一个整数消息。第一种编码方案我们称之为朴素编码方案将明文元素构造为。也就是说我们将 M 设置为一个常数多项式其中 m 为常数项。虽然这种编码方案原则上很简单但特别是对于大消息 m 来说效率极低。原因是在对密文执行同态运算时明文系数的大小会增大。为了确保同态求值的结果与感兴趣计算的预期结果相匹配我们需要确保明文系数不会超出的范围。因此我们需要确保t比要在全同态中实现的计算的输入、任何中间结果和输出都足够大。朴素编码方案呈现出系数快速增长的情况。我们注意到这种编码方案存在一个更严重的局限性即浪费了明文多项式中的 个系数。这种方案的解码通过简单读取解密后得到的明文多项式的常数项来实现。其他更高效的编码方案会利用一个子集甚至所有系数称为打包或批量编码方案。 我们要介绍的另一种编码方案称为整数编码方案其工作方式如下 1. 用二进制表示m即 2. 构造。由于在实际中n太大未使用的位被设置为0。 由于明文系数的量级较小在同态求值过程中系数的增长通常较慢。请注意使用这种编码进行同态求值可能会导致明文多项式的次数增加。为了确保同态求值的结果与感兴趣的计算的预期结果相匹配我们需要确保明文系数的次数不会超出 的范围并且系数不会超出 的范围。 注意对于整数编码方案可以选择除2以外的任何整数分解基数例如三进制、四进制或k进制基数分解。整数编码方案的解码通过在处计算明文多项式来实现即计算。 5、密钥生成
私钥SK是从中生成的一个随机三元多项式它是一个次数为 n 且系数在 {-1、0、1}中的多项式。
BFV的公钥 PK 是一对多项式计算如下其中 a 是 中的随机多项式是从 中随机抽样的误差多项式。
符号意味着多项式算术应该在模 q 下进行。请注意由于 在 中多项式算术也应该在环多项式模下进行。
BGV的公钥PK也是一对多项式计算如下 其中 是 中的随机多项式是从中采样的随机误差多项式。
符号 表示多项式模 下进行计算。请注意与BFV中的密钥生成不同这里的误差是由 缩放的。 6、加密和解密 首先我们来介绍下BFV的加解密过程 在 P 中加密明文消息 M首先生成三个小的随机多项式从 生成 从 生成 和 然后返回密文 如下 (1)
参数被定义为 q 除以 t 的商即 。它用于缩放消息。 解密是通过在密钥上对密文进行评估来执行的如下所示并反转加密中应用的缩放因子 (2) 为了检查解密为何起作用以及在哪些条件下起作用让我们将等式2展开如下 (3) 需要注意的是 的无穷范数即多项式 中最大的绝对系数用 表示非常小因为 和 都是小多项式。更具体地说鉴于这些小多项式都受参数 的限制可以很容易地证明 。 为了继续进行证明我们需要展开模 下的等式(3)并完成对解密函数的求值。可以如下进行 (4) 其中 是某个多项式。将等式(4)乘以 得到 。解密中的取整函数去除 最后的模 运算去除 并恢复 。简而言之为了使解密正确地恢复 我们需要确保 否则噪声将会溢出并破坏消息。 接下来我们介绍BGV的加解密过程整体类似会一些小差异 加密算法将明文消息M和公钥PK作为输入并输出密文 从而对输入消息进行加密。加密过程如下我们生成三个小的随机多项式从 生成 从 生成 和 并计算 (5) 注意 中的误差多项式是如何被明文模数 缩放的。这与我们之前在图2中展示的情况一致即消息位于密文系数的低位而噪声可以在高位增长。 解密过程通过将密文和私钥 作为输入来逆转加密过程。如果在计算过程中噪声没有增长到无法控制的程度它将输出明文消息 。解密过程如下 (6) 为了检查解密为何起作用以及在哪些条件下起作用让我们将等式(5) 展开如下 (7) 通过将上述结果对 取模我们去除了噪声向量 并恢复出没有噪声的 。但这里有一个与v的范数相关的注意事项。只要 解密就有效其中 定义为v中最大的绝对系数。设置这个边界是为了使噪声的幅度不会增长过多而破坏消息。 7、同态计算 在本节中我们将解释BFV和BGV在同态计算求值过程中是如何工作的。在这里我们研究两个主要的同态操作加法和乘法。
BFV的同态加法 让我们以同态加法为参考来理解同态加法是如何工作的。这个过程非常简单我们只需将每个密文中相应的多项式相加如等式(8)所示 (8) 为了理解为什么这样可行让我们将等式(8)进行如下拆解假设 和 分别是对 和 的新的加密结果。从代数角度来看它们可以如下表示参见等式(1) (9) 通过将方程(8)中的 和 进行代入我们得到以下结果 (10) 很容易注意到等式(10)具有对 进行加密的有效密文形式。请注意在最坏情况分析下 中的误差项大约是输入密文中噪声项的总和即噪声是累加增长的。可以遵循上述用于推导 EvalAddPlain 表达式的过程。明文消息可以通过加密转换为密文形式且没有误差项即 。 BFV的同态乘法 同态乘法比同态加法更复杂。我们在此介绍基本过程并请读者参考外部资源以获取更多详细信息。 将密文写成在私钥SK 处的求值形式是有用的参考公式(4)就像我们在推导解密过程中所做的那样 (11)
将密文相乘会得到 (12) 密文看起来接近我们想要的加密形式 。我们注意到用 进行缩放会准确地得到我们在第一项中想要的东西再加上一些噪声。然而由于 不能整除 所以最后一项 会产生很大的噪声。相反我们将使用因子 进行缩放。现在我们可以写成 。我们也可以写成 。用 进行缩放并将这些表达式代入等式(12)我们得到以下结果 (13) 推导过程的最后一步是将等式(13)模 化简这会得到 (14) 其中 是由等式(13)中的最后两项产生的舍入误差。 乘法运算中的噪声增长具有近似为 的线性因子即 其中 是乘积密文中的噪声 是输入密文中的噪声。 简而言之为了评估同态乘法我们计算输入密文的张量积并按 进行缩放如下所示 (15) 可以注意到EvalMult 将结果密文中的项数从 2 个环元素增加到了 3 个。此外为了解密得到的密文必须使用稍微不同的解密过程。幸运的是这些复杂情况可以通过重线性化来解决这将在后续部分进行描述。 BGV的同态加法 如公式(16)所示同态加法以两个相对于相同模数 定义的密文 和 作为输入并返回一个密文 该密文包含对输入中加密的两个明文消息之和的加密即 。只要被加数密文中的误差不是太大这就适用。为了理解这一点让我们分析同态加法过程。公式(5)相当简单我们只需将每个密文中的相应多项式相加。 (16) 为了理解这为何可行让我们对公式(16)进行如下拆解假设 和 分别是对 和 的新的加密结果果。从代数角度来看它们可以如下表示参见公式(5)。 (17) 将 和 代入公式(16)我们得到以下结果 (18) 很容易看出公式(18)具有对 进行加密的有效密文的形式。请注意在 中的误差项在最坏情况分析下大约是输入密文中噪声项的总和即噪声是累加增长的。 BGV的同态乘法 同态乘法以两个相对于相同模数 定义的密文 和 作为输入并返回一个密文$ 该密文包含对输入密文中加密的两个明文消息之积的加密即 。 在接下来的分析中我们将解密公式解释为在私钥SK处的密文评估 (19) 将密文相乘会得到 (20) 密文乘积的解密公式具有对 进行加密的有效密文结构其噪声项为 。注意噪声项是如何随着输入密文中噪声的乘积而呈乘法增长的 。这意味着随着我们在计算中进行得更深入噪声呈指数增长。为了解决这个问题BGV使用模数切换ModSwitch来降低乘法噪声的增长速度。模数切换将在本文后面进行描述。 根据上述讨论我们可以推断出\(EvalMult\)可以通过输入密文的多项式乘法进行计算如下面的公式所示 (21) EvalMult 将结果密文中的环元素数量从 2 增加到了 3。此外乘积密文是相对于 而不是原始的私钥 定义的也就是说它可以使用 进行解密。为了将元素数量恢复到 2 并使密文可以使用 进行解密可以使用接下来描述的重线性化过程。 8、重线性化 BFV的重线性化过程的主要目的是将由 EvalMult 产生的乘积密文product ciphertexts的大小减少回两个环元素。 这个问题可以具体表述如下令 。我们的目标是找到 使得 (22) 通过评估密钥 提供对 的访问。请注意这是 的掩码版本因为。现在我们可以计算 如下 (23) 如果我们写出方程(23)的解密公式我们得到 (24) 需要注意的是由于 在 中有系数所以项 可能会很大。不过有一种使用基分解的技术可以减少这个误差。更多细节我们请读者参考[FV12]。 BGV由于与密文模数相关的一些小变化我们在这里简要重申相同的问题和相同的目标使得 (25) 通过评估密钥 计算 如下 (26) 通过解密公式(24)我们就会得到我们想要的内容。 9、模数切换 如前所述模数切换MODSWITCH用于控制乘法噪声。这个概念最初在[BGV14]中被引入它利用了这样一个事实给定一个相对于模数q和私钥SK定义的密文C它可以被转换为一个相对于另一个模数 和相同私钥SK定义的等价密文 使得 (27) 这种转换是通过将C的系数乘以 的量并进行适当的舍入来完成的。为了降低噪声幅度我们选择一个比 小得多的 这使我们能够降低乘法噪声。 请注意在BGV的情境中q可以是任何层级 的 而在此情境中q简单地就是 。此外密文模数 的选择使得它们对取模是等价的。这导致在不影响加密的明文消息的情况下降低了噪声。从明文的角度看就好像我们是按1进行缩放。
模数切换MODSWITCH可以按照公式(28)进行计算其中[·]是一个合适的舍入函数。转换后的密文C是根据新的模数q定义的。 (28) 10、安全性 BFV/BGV 方案安全性源于 RLWE 问题的难度。我们注意到选择最佳的参数以最大化性能并同时满足安全性和功能性约束是一项相当复杂的任务最好咨询专业密码学家来进行选择。对于 BFV/BGV 的简要安全分析和一组推荐参数我们建议读者参考同态加密标准。 11、总结
BFV和BGV同态加密方案的发展路径和关键里程碑
11.1. BFV发展路径
BFV方案Brakerski/Fan-Vercauteren最初是由Zvika Brakerski提出的并由Fan和Vercauteren进一步改进。其发展历程可以分为以下几个阶段 2011年Brakerski提出基于学习有噪声问题LWE和理想格的同态加密基础模型。这一模型首次展示了如何利用噪声增长的管理实现多次加密操作。 2012年Brakerski和Vercauteren改进了初始方案引入了特殊模数来控制噪声增长即现在称为BFV的方案。此时他们提出了新的编码方式允许整数加法和乘法运算特别适合用于需要高精度计算的场景。 2014年Fan和Vercauteren提出了一个改进版本通过调整参数和编码策略来进一步优化BFV的噪声管理使得BFV方案在整数加密中更为高效稳定这一版本正式确立了BFV的模型。
BFV更适合低深度、精确计算不需要模数转换。
11.2. BGV发展路径
BGV方案Brakerski-Gentry-Vaikuntanathan则是在BFV方案基础上进一步通过模数转换技术改善了噪声控制和运算效率特别适合高深度、多乘法操作的同态加密场景。BGV的发展路径主要包括以下阶段 2011年Brakerski和Vaikuntanathan提出一个非耦合模数的噪声控制技术为后续的BGV方案打下基础。这项技术允许在不同模数下控制噪声增长使同态乘法不至于导致噪声增长过快。 2012年Brakerski、Gentry和Vaikuntanathan联合提出了BGV方案首次引入模数转换modulus switching技术。该技术通过每次乘法操作后逐步减小模数来管理噪声使得BGV方案能够支持更高深度的乘法操作。这一创新为高深度同态加密计算带来了显著的效率提升。 2013年BGV方案得到进一步的优化引入了批处理batching和密文旋转ciphertext rotation技术允许在密文中进行向量操作提升了批处理密文的计算效率。
BGV在重线性化的基础上支持模数转换适合高深度和批处理计算噪声控制更好密文大小管理更高效。 因此选择使用BFV还是BGV取决于具体应用需求比如精度需求和计算深度。如果需要更高的运算深度和效率BGV会是更合适的选择而对于低深度、精确度要求高的场景BFV则更适用。 在《Revisiting Homomorphic Encryption Schemes for Finite Fields》这篇文章里作者在PALISADE中做了BGV和BFV的实现 BGV在大明文模数下噪声增长比较小他们的结果是优化后的BFV和BGV在大明文模数下表现近似稍好于BGV。 BFV的效率在小明文模数下较好BGV的效率在适中或者较大的模数情况下表现较好。 PALISADE中的BFV实现比之前最好的实现在深层乘法电路的评估上快了4倍。
