BFV-MKFHE: 基于BFV 的多密钥全同态加密方案设计*

杨亚涛, 赵东仓, 李兆夫, 刘亚奇

1.北京电子科技学院 电子与通信工程系, 北京100070

2.西安电子科技大学 通信工程学院, 西安710071

1 引言

在当前大数据与云计算背景下, 高效安全的数据处理显得尤其重要.云计算技术解决了本地计算资源匮乏的问题, 使得外包任务和数据成为人们共享信息和处理数据的主要方式.云计算在成本和效率方面为我们提供便利的同时, 也带来了很多机密性问题和隐私泄露隐患.当今社会, 人们对数据安全和隐私保护的要求越来越高, 因此, 如何在数据计算过程中保证用户数据的隐私性和安全性, 成为云环境中迫切需要解决的实际问题.

全同态加密(fully homomorphic encryption, FHE) 技术因其密文可计算的突出优势在众多隐私保护手段中脱颖而出, 为隐私计算提供了一种有效的解决方案.常规的全同态加密方案主要包括公私钥生成、加密、密文运算和解密四个过程, 具体过程示意如图1 所示.

图1 常规全同态加密(FHE) 运算示意图Figure 1 Traditional full homomorphic encryption (FHE) operation

1978 年Rivset 等人[1]提出隐私同态的概念; 直到2009 年,Gentry 给出了全同态加密方案[2,3]的理论证明, 它的结构由三部分构成: 首先, 构造一个有限同态加密方案, 可以评估有限复杂度的函数; 其次, 尽可能简化该方案的解密方案; 最后, 对简化的解密函数进行同态计算, 得到最终密文.杨亚涛等人在SEAL(simple encrypted arithmetic library) 全同态加密库的基础上先后设计了同态加权电子投票系统[4]和同态密文指纹识别系统[5], 拓展了同态密码的应用价值, 推动了全同态密码从理论层面走向实际应用的进程.文献[6] 通过分析研究近年来国内外在同态密码领域的相关研究成果, 对当前同态密码的发展情况、应用现状以及未来可能的研究与发展方向做了详细描述.

多密钥全同态加密(multi-key fully homomorphic encryption, MKFHE) 技术允许对独立密钥加密的不同数据进行计算, 同态计算后的密文由所有参与者使用自己的私钥分布式解密, 再将各部分解密结果联合起来得到最终结果(如图2–3 所示), 这是常规全同态加密技术无法实现的.

图2 多密钥全同态加密(MKFHE) 运算示意图Figure 2 Multi-key fully homomorphic encryption (MKFHE) operation

随着多方安全计算技术的发展, 在同态加密的实际应用中, 通常需要面对多用户多密钥的场景, 而传统的全同态加密技术的同态计算只能对使用相同身份创建的密文(同一密钥下的密文) 执行, 这一固有的缺陷使得FHE 的实际应用有着较大的局限性.为了在多用户场景下解决隐私计算问题, 人们开始了MKFHE 方案的探索研究.

2012 年, López-Alt 等人[7]提出了第一个MKFHE 的构造LTV12, 基于NTRU (number theory research unit) 加密系统首次给出了MKFHE 的概念.后续较多构造方案均是在此基础上得到的.多密钥全同态加密技术的良好特性使得其在处理安全多方计算问题时具有显著优势, 未来将得到更广泛的应用,因此在该方向的理论与应用研究具有很大的现实意义.

2 相关工作

在 TCC 2017 上, Chen 等人提出了一个新的安全性基于环 LWE 问题的多跳 MKFHE 方案CZW17[8].不同于以往关于标准假设的基于GSW 型的MKFHE 方案, 该方案的架构建立在BGV型的FHE 上, 该方案继承了BGV 方案的优点, 可以加密一个环形元素作为明文, 并支持基于CRT (Chinese Remainder Theorem) 的密文封装技术.此外, 该方案密文扩展程序的复杂性只取决于所涉及的密钥数量, 而无关乎密文数量.2019 年, Chen 等人设计了BFV 与CKKS 方案的多密钥变体, 创造性提出利用单一加密算法构造用户私钥的组合密文来生成重线性化密钥(计算密钥) 的新思路, 且无需对私钥密文扩展, 与之前借助GSW 方案生成计算密钥的技术相比, 该计算密钥生成算法更简洁快速.由此构造了高效的MKFHE 方案CDKS19[9], 并对该方案进行了应用研究.相比于CZW17 和LZY+19[10]方案, 该方案在空间和时间复杂度上都有所降低.

当前主流的MKFHE 方案按照基于的全同态加密系统不同, 主要分为以下四种类型:

第一种类型是NTRU 型的MKFHE 方案.该类型以López-Alt 等人[7]在2012 年首次提出的MKFHE 方案LTV12 为代表, 该方案首次给出了MKFHE 的密码学定义.2020 年, Chen 等人构造了一种在同态运算后无需使用密钥转换技术进行密文维度约减的NTRU 型MKFHE 方案CZL+20[11],在一定程度上降低了密钥尺度.2020 年, 李瑞琪等人[12]设计了一个基于NTRU 的支持批处理的层级MKFHE 方案, 该方案使用工具向量(gadget vector) 相关技术, 在构造方法上相比以往MKFHE 更为简洁, 较大程度降低了计算复杂度和通信开销.

第二种类型是GSW 型的MKFHE 方案.2013 年, Gentry 等人提出了第一个基于身份的完全同态(IBFHE) 加密方案GSW13[13], 然而他们的方案只在单一身份设置下有效.2015 年, Clear 和Mc-Goldrick 在GSW13[13]方案基础上, 将结果推广到多身份的情况下, 在标准模型下构造了基于LWE 安全的MKFHE 方案CM15[14].该方案是第一个基于标准LWE 成熟假设的MKFHE 方案, 此后人们在此基础上提出了更多优化和扩展方案.在TCC2016 上, Peikert 和Shiehian 提出了基于GSW 的多跳(multi-hop) 多密钥全同态加密方案PS16[15], 该方案比以前的基于LWE 的方案具有更小的密文尺度.紧接着, Brakerski 和Perlman 构造了一个基于LWE 安全的全动态(fully dynamic) MKFHE 方案BP16[16], 该方案支持无限次的同态操作, 适用于动态增加的多个参与方; 此外, 该方案的密文尺度和同态操作的空间复杂度只相对当前各参与方数量呈线性增长.

第三种类型是BGV 型的MKFHE 方案.2012 年, Brakerski 等人构造了BGV12 方案[17], 该方案在同态计算后使用密钥交换(key-switching) 技术对膨胀的密文维度进行约减, 是另一种形式的重线性化技术.另外, BGV 型方案涉及到模数交换(modulus-switching) 技术, 这是与BFV 型方案最大的不同之处.该类型的代表性方案除了上文提到的CZW17[8]和CDKS19[9]之外, 在2019 年, Li 等人构造了BGV型MKFHE 方案LZY+19[10], 该方案给出GSW 的可分离密文扩展, 可以将扩展密文的大小缩小一半左右; 其次, 方案在计算密钥生成过程中使用RBGV 密文和RGSW 密文的混合同态乘法, 可以显著减少输入/输出密文的数量, 进而提高效率; 最后, 该方案构造了一个定向解密协议, 允许被评估的密文被任何目标用户解密, 并消除了现有MKFHE 方案中被评估密文只能由参与同态计算的用户解密的限制.

第四种类型是TFHE 型的MKFHE 方案.在ASIACRYPT 2016 上, Chillotti 等人构造了FHE方案CGGI16[18].紧接着, 在ASIACRYPT 2017 上, Chillotti 等人在CGGI16 方案的基础上提出了CGGI17[19]方案, 该方案可以减少密文扩展.在ASIACRYPT 2019 上, Chen 等人基于Chillotti 等人在ASIACRYPT 2016 上设计的低延迟同态加密思路, 提出了一个MKHE 方案CCS19[20], 该方案构造的密文尺度和同态计算的计算成本分别以线性和四次方的方式增长, 与以前的工作相比, 在具体复杂度方面更有效率.

此外, 在量子同态领域也有相应的多密钥方案.比如在方案DSS16[21]的基础上发展而来的MKFHE方案Goy18[22].

2020 年, 李宁波等人[23]对当前MKFHE 领域的各类文献成果进行了分析归纳, 详细介绍了每个类型中典型的MKFHE 方案的构造方式, 并分别对其存在的问题进行了分析对比, 在此基础上, 对未来一段时间多密钥全同态加密的研究方向与趋势做出了展望.

通过以上分析可以看到, 之前绝大多数高效的多密钥全同态加密方案都是基于或利用GSW 方案来构造的, 且普遍存在以下两个问题: 第一, 密钥交换(重线性化) 过程通常较为繁琐, 计算复杂度较大, 从而影响了整个方案的效率.这主要是由于计算密钥的生成往往需要借助GSW 等方案, 所需的密钥在数量和尺度上都难以降低.第二, 密文运算会产生较多的噪声, 噪声是影响全同态加密方案性能的重要因素, 在多密钥的情况下, 对噪声的控制显得尤其重要, 现有的方案应对噪声积累大多缺乏有效措施.

BGV 与BFV 同为第二代全同态加密的代表性算法, BGV 方案主要涉及到一个模数转换技术, 在BGV 方案中, 模数的选取与每次需要减少的噪声大小有关, 也与需要执行的算术电路有关, 因此BGV 的可用性受到一定限制.然而在BFV 中, 模数能够选取到软件/硬件能表达的最大位数, 并且由于BFV 将模数转换的方案隐式包含在了乘法运算中, 所以BFV 方案不需要额外的技术手段来解决这个问题.相关实验证明, 在明文空间模数较小的情况下, BFV 方案比BGV 方案的效率更高, 但是针对BFV 设计的多密钥全同态加密方案较少, 因此本文采用BFV 算法的基本架构, 通过修改GZW17 方案的密钥交换、模数转换等过程, 优化加解密算法, 提出了一种基于BFV 的多密钥全同态加密方案, 该方案继承了第二代FHE 方案的优点, 可以加密环上的明文.在密文/明文比率、同态操作的复杂性和其他通信开销方面, 比以前的工作更为有效.

本文提出的基于BFV 的多密钥全同态加密方案, 主要贡献为:

(1) 提出了一种高效的基于BFV 的MKFHE 方案, 称为BFV-MKFHE 方案.我们将CZW17 方案的BGV 加密算法的结构修改为BFV 加密算法的结构, 减去了模数转化过程, 使得加密算法更为简洁,可以在一定程度上提高同态运算效率.此外, 本方案通过改变加密运算的取整方式来对加密算法进行优化,该方法减少了计算冗余, 在一定程度上减缓了噪声积累.

(2) 修改了CZW17 方案中计算密钥的生成过程, 使得多密钥重线性化算法更简洁高效.本方案通过单一加密算法来加密用户私钥, 用最终生成的组合密文来生成计算密钥, 重线性化算法建立在效率更高的CDKS19 方案的基础上, 并通过模数提高技术对算法进行优化, 降低了同态运算的计算复杂度.本方案完成一次同态乘法解密时产生的噪声值减小为CDKS19 方案的1/p,生成计算密钥的密文尺寸相比CZW17方案和LZY+19 方案约减小1/4, 运算效率更高.

3 预备知识

3.1 符号定义

文中斜体的大写字母(例如A)表示矩阵,斜体的小写字母(例如a)表示向量,a[i]表示向量a中的第i个元素.给定一个概率分布D, 用x ←D表示x是D中的采样.对于集合S,x ←S表示从S中均匀采样出X.本文的方案建立在环R==Z[x]/(xn+1)上,λ为安全系数,χ是R上的错误概率分布,K为参与方数量上限,L表示电路深度, 令l=L,···,0.选择整数n=n(λ), 定义多项式环R=Z(x)/xn+1,多项式环R 上的噪声分布为χ=χ(λ,K,L),q=ploy(n) 为密文模数.

3.2 RLWE 问题与比特分解函数

环上带错学习问题RLWE 最初由Lyubashevsky 等[24]提出, 定义如下:

对于安全参数λ, 设f(x) 是一个循环多项式Φm(x), 其deg(F) = Φ(M) 取决于λ, 并设置R=Z[x]/(f(x)).设q=q(λ)≥2 为整数.对于随机元素s ∈Rq和在R上的分布χ=χ(λ), 用Aqs,χ表示通过选择均匀随机元素a ←Rq和噪声项e ←χ得到的分布, 输出(a,[as+e]q).RLWEd,q,χ问题是区分分布和均匀分布U(R2q) 的不同.

2012 年Micciancio[25]给出了工具向量(gadget vector)g和比特分解函数g−1(·) 的概念, 具体来说, 如果令g= (gi)∈zd为一个工具向量,q是一个整数, 比特分解函数g−1是一个将一个元素a ∈Rq转化为一个向量u=(u0,u1,···,ud−1)∈Rd的函数, 且满足

3.3 BFV 全同态加密算法

2012 年, Fan 等人[26]通过对Brakerski 所提方案[27]进行优化, 提出了BFV 同态方案.BFV 方案建立在环R=Z[x]/(xn+1) 上,λ为安全系数,t为约减明文多项式的系数,χ是R上的错误概率分布,ω是对数的底数.BFV 全同态加密方案共包括私钥生成、公钥生成、计算密钥生成、加密、解密、同态加法和同态乘法7 个算法.该方案具体算法如下:

4 BFV-MKFHE 方案设计

4.1 多密钥重线性化算法的设计与优化

在单密钥情况下, 基于RLWE 的密文进行同态乘法包括两个步骤: 向量乘法和重线性化.对于输入的密文ct1和ct2, 首先计算它们的向量乘积, 得到一个满足＜ct,sk⊗sk＞=＜ct1,sk＞·＜ct2,sk＞的扩展密文.由于sk·sk 包含非线性部分s2, 所以需要执行作为同态运算核心操作的重线性化程序, 将扩展的密文转换为加密相同明文信息的典型密文.这个过程需要一个重线性化密钥(计算密钥), 它是通过在sk 下加密s2得到的, 因此, 重线性化的过程可以理解为一个密钥切换过程.

本文的重线性化算法建立在CDKS19 方案的基础上, 通过构造用户私钥的组合密文来生成计算密钥,并通过应用模数提高技术对算法进行改进, 该算法无需对用户私钥的密文进行扩展, 同时尽可能来降低同态运算的计算复杂度, 具有较好的性能.

4.1.1 计算密钥的生成算法设计

在多密钥同态算法中, 计算密钥的生成与使用是影响算法效率与性能的关键环节, 其中如何降低计算密钥生成的复杂度是需要考虑的主要问题.本节中借助单一加密算法[9]来生成计算密钥, 具体步骤如下:

Setup(1λ): 给定一个安全参数λ, 设置RLWE 的维度n、密文模数q、特殊模数p、密钥分布χ、环上的错误分布Ψ.生成一个随机向量a ←U(Rdq), 最后, 返回公共参数pp=(n,q,p,χ,Ψ,a).

KeyGen(pp): 选取私钥s ←χ, 错误向量e ←Ψd, 输出公钥b=−s·a+e(modq)∈Rdq.公共参数pp 包含一个随机生成的向量a ∈Rdq, 作为共同参考字符串模型, 同其他MKHE 方案一样, 所有各方都应该采取相同的公共参数作为密钥生成算法的输入, 以支持多密钥同态运算.

UniEnc(µ,s): 输入一个明文m ∈R, 输出一个密文D=[d0|d1|d2]∈Rd×3q, 具体步骤如算法1 所示.

4.1.2 模数提高技术的引入

算法3 模数提高的重线性化算法MR-Relin(ct,(Di,bi)1≤i≤k)Input: 一个扩展密文ct = (ci,j)0≤i,j≤k, k 对计算密钥和公钥组合{(Di,bi)}1≤i≤k Output: 一个密文ct′ = (c′i)0≤i≤k ∈R(k+1)q 1 令(c′i)0≤i≤k ←0;2 for 1 ≤i ≤k do i,j ←< g−1(ci,j),bj > (mod pq),4 c′3 c′′i,j ←⎿p−1 ·c′′i,j⏋,5 (c′′0,c′′i) ←(c′′0,c′′i)+g−1(c′i,j)[di,0|di,1](mod pq),j ←c′j+ < g−1(ci,j),di,2 > (mod pq);7 end 8 计算c′0 ←c0,0 +⎿p−1 ·c′′0 ⏋(mod q);9 对所有的1 ≤i ≤k, 计算c′1 ←c0,i +ci,0⎿p−1 ·c′′i ⏋(mod q).6 c′′

4.2 加密算法取整方式的优化

噪声是影响全同态密码算法性能的主要障碍.在密文域上进行同态计算将导致噪声增长, 特别是同态乘法引起的噪声增长更为显著, 当噪声增加到一定程度时, 解密算法将失败.在BFV 的加密算法中, 明文m ∈Rt, 公钥表示为pk=(p0,P1), 作抽样e1,e2←χ, 密文可以表示为

4.3 BFV-MKFHE 方案构造

本节详细给出BFV-MKFHE 方案的6 个算法,即MKFHE.Setup、MKFHE.KeyGen、MKFHE.Enc、MKFHE.CTExt、MKFHE.Eval、MKFHE.Dec.

(1) MKFHE.Setup(1λ,1k,1l)在给定安全参数λ的情况下, 定义K为参与方数量上限,L表示电路深度, 令l=L,···,0.选择整数n=n(λ), 定义多项式环R=Z(x)/xn+1, 多项式环R上的噪声分布为χ=χ(λ,K,L),

由于在部分解密过程中使用噪声泛洪技术(noise flooding techniques) 引入噪声项ei ←ϕ(ϕ为噪声分布).该步骤的安全性是基于LWE 困难问题的, 公布的各部分解密结果为m∗i= [cisi+ei]q,并不会泄露用户私钥si.该方案加密算法的安全性是基于RLWE 困难问题,满足IND-CPA安全的, 修改后的联合解密算法是具有已知系数的秘密的(近似) 线性组合.因此, 在以上分布式解密过程中公布部分解密结果不会泄露用户信息(明文或密钥).

算法4 多密钥全同态密文扩展MKFHE.CTExt(ct1,ID1,ct2,ID2)Input: 两个密文组{ct1 = (c10,c11,··· ,c1,k1),ID1 = (id11,id12,··· ,id1k1)},{ct2 = (c20,c21,··· ,c2,k2),ID2 = (id21,id22,··· ,id2k2)}Output: 两个扩展密文组{ct1 = (c∗10,c∗11,··· ,c∗1k),ID1 = (id1,id2,··· ,idk)},{ct2 = (c∗20,c∗21,··· ,c∗2k),ID2 = (id1,id2,··· ,idk)}1 ID1 =ID2 = ID1 ∪ID2 = (id1,id2,··· ,idk), k ≥max{k1,k2}, 所有参与用户合并为一个集合, 则可以共享同一组私钥sk = (1,s1,··· ,sk).2 令c∗10 = c10, 对所有的1 ≥i ≥k, 令c∗1,i =■■ ■c1,j, idi = id1j(1 ≥j ≥ki)0, else , 即原有用户的密文不变, 新用户的密文位置补零.

5 方案证明与分析

5.1 正确性证明

由以上推导可以证明方案中所使用的重线性算法的正确性.

5.2 安全性分析

BFV-MKFHE 方案是在典型BFV 加密算法的基础上设计的, 借鉴了LZY+19 方案和CDKS19 方案中的计算密钥的生成算法, 并重构优化了加解密方式, 其安全性仍是基于RLWE 困难问题.

如前所述, 该MKFHE 方案包含了单一加密算法.密文是通过将编码后的明文添加到随机加密的零中产生的.因此, 只需证明零的随机加密在计算上与随机变量没有区别即可, 证明如下:

定义一个随机变量(a,b,c0,c1)∈R4q, 其中a ←U(Rq),b=−s·a+e(modq) 满足s ←χ,e ←Ψ;(c0,c1) =v·(b,a)+(e0,e1)(modq) 满足v ←χ,e0,e1←Ψ.首先, 将b的定义优化为b ←U(Rq), 由于参数(n,q,χ,Ψ) 下私钥s的RLWE 问题是困难的, 所以它们在计算上是不可区分的.然后, (b,c0) 和(a,c1) 可以被看作是秘密v的两个RLWE 密文, 在同样的RLWE 假设下, 它们与均匀随机变量U(R2q)在计算上是不可区分的.

只需要将密文模数设为pq, 就能得到模数提高技术下的单一加密算法和重线性化算法.因此, 我们也可以证明在参数为(n,q,χ,Ψ) 的RLWE 假设下, 该MKFHE 方案的模数提高技术是IND-CPA 安全的.

以上分析证明, 我们设计的BFV 型MKFHE 方案BFV-MKFHE 的安全性等同于LZY+19 方案和CDKS19 方案的安全性, 满足IND-CPA 安全.

5.3 重线性化算法噪声分析

BFV-MKFHE 方案主要通过在重线性化算法中使用模数提高技术来减少噪声积累的, 因此本节主要对重线性化算法的噪声进行分析.

本文算法中的噪声呈现高斯分布, 所以本节通过计算噪声的方差, 对噪声进行评估和对比分析.

通过以上模数提高技术使用前后重线性化算法噪声的方差对比, 可以得出结论: 使用模数提高技术可以使得重线性化算法噪声降低.

5.4 性能分析

BFV-MKFHE 方案借鉴了CDKS19 方案中较为简洁的重线性化思路, 并通过模数提高技术加以优化, 同时通过改变加密时的取整方式, 减少了加密算法的噪声积累, 降低了计算冗余.与BGV 型的MKFHE 方案CZW17 和LZY+19 相比, 省去了每一层的模数转换环节, 同时简化了计算密钥的生成过程, 较大程度降低了算法的计算复杂度, 同态运算的效率更高.

表1 提供了BFV-MKFHE 方案与几种典型方案的主要特征比较.由表1 可知, BFV-MKFHE 方案的三个基本特征与CZW17 相同, 两者的安全性都是基于RLWE 假设, 多个密钥环且支持批处理.

表1 BFV-MKFHE 方案与其他方案的主要特征比较Table 1 Comparison of main features of BFV-MKFHE scheme with other schemes

表2 是本方案与目前经典的MKFHE 方案(CZW17 方案、LZY+19 方案、CDKS19 方案) 的部分性能对比.从表2 中可以看出, 本方案中计算密钥密文的尺寸相对于CDKS19 方案没有改变, 但较CZW17方案与LZY+19 方案约减小1/4, 且无需对用户私钥的密文进行扩展.CDKS19 方案一次同态乘法解密时产生的噪声值相较于前两个方案均降低了n倍, 由于本方案在重线性化之前使用了模数提高技术, 所以使得一次同态乘法解密时产生的噪声值减小为CDKS19 方案的1/p.此外, 本方案优化了BFV 加密算法中的取整方式, 降低了计算冗余, 与以往方案的综合比较可知, 本方案的运算效率更高.

表2 BFV-MKFHE 方案与其他方案的部分性能比较Table 2 Partial performance comparison of BFV-MKFHE solution with other solutions

6 小结

本文在CZW17 方案的基础上构造了基于BFV 的多密钥全同态加密方案BFV-MKFHE, 在保证运算效率和安全性的同时, 继承了BFV 方案不需要模数转换的优点.在计算密钥的生成上, 借鉴了CDKS19 方案中较为简洁的单一加密算法, 并利用模数提高技术进行优化, 使得在同态操作的复杂性和其他通信开销方面, 比以前的研究工作更有效.相对于CDKS19 方案, 计算密钥密文的尺寸相同, 且无需对用户私钥的密文进行扩展.相对于CZW17 方案与LZY+19 方案, 本方案在计算密钥的密文尺寸、一次同态乘法产生的噪声值以及是否需要扩展计算密钥的密文方面均有所提升.下一步, 将研究如何进一步减小生成计算密钥的密文尺寸, 提高全同态运算的效率.