李习习, 唐春明, 胡业周

广州大学数学与信息科学学院, 广州 510006

1 引言

云存储与云计算平台的快速发展使用户可以外包存储、计算自身的数据, 这样用户就能够节省投资费用, 简化复杂的设置和管理任务. 然而, 私密信息、有价值的商业数据泄露成为其发展的一大障碍. 全同态加密(full homomorphic encryption, FHE) 的出现为上述问题提供了一个很好的解决方案, 全同态加密的一个显著特征就是允许任何人对密文直接进行计算操作, 解密结果相当于对明文做同样的计算操作, 即dec(f(Enc(m1),Enc(m2),··· ,Enc(mn)))=f(m1,m2,··· ,mn).

传统的全同态加密体制对单个用户的单个比特进行加密, 无法实现一次加密多个比特以及对多个用户上传到云端的数据进行安全的多方联合计算. 例如, 他们可能希望云来计算他们数据库上的联合统计信息;在数据库集合中定位公共文件; 将多个(相互不信任的) 用户的数据集中在一起, 通过特定的计算以实现共同的目标、达成统一的决策(除此之外不泄露其它隐私信息) 等. 在本文中, 我们设计一种支持多比特多密钥的全同态加密方案, 使得多个用户可以安全联合计算目标数据的同时可以一次加密多个比特.

本文第2 节为综述相关工作; 第3 节给出符号说明以及一些与本文相关的定义定理等; 第4 节简要叙述我们的多比特全同态加密方案和该方案的安全性证明; 第5 节给出如何将多比特单密钥密文扩展成多比特多密钥密文; 第6 节给出我们的多比特多密钥全同态加密方案并且证明了密文扩展的的正确性; 第7 节总结全文.

2 相关工作

全同态加密的思想最早由Rivest 等人[1]于1978 年提出, 如何构造满足全同态性质的体制一直是困扰密码学家的难题, 直到2009 年Gentry 基于理想格提出来第一个全同态加密体制[2], 随后很多密码学家在全同态加密体制的研究取得进展. 2010 年Smart 等人[3]在PKC 上简化了Gentry09 体制的实现.2011 年Gentry 等人[4]对Gentry09 体制做进一步的简化, 并提出了部分同态加密方案的新的密钥生成算法, 减少密钥和密文长度, 使得部分参数的实现成为可能. 同年, Brakerski 等人基于LWE 提出了全同态加密方案[5], 但是他们的方案不能够利用自举以达到全同态的目的. 2012 年, Brakerski 又提出了一个基于LWE 的无需模数转换管理噪音也能很好的控制噪音增长的全同态加密方案[6]. 但上述方案都需要“计算密钥” 的辅助信息才能达到全同态的目的, 计算密钥的尺寸都很大, 是制约全同态加密效率的一大瓶颈. 2013 年Gentry 等人利用“近似特征向量” 技术, 设计了一个无需计算密钥的全同态加密方案[7], 掀起了全同态加密研究的一个新高潮. 此后, 研究人员在高效的自举算法、多密钥全同态加密方案等方面进行了大量的研究.

2016 年, Gama 等人提出了一个更高效的自举算法[8]: 运行一次自举算法累积的噪音的上界是线性的. López-Alt 等人最先开始研究多密钥全同态加密[9], 但是, 他们的方案用到了一个非标准的假设, 并且近年来也遭受到比较严重的攻击. 所以设计安全的多密钥全同态加密引起了人们的注意, 并研究出多个多密钥全同态加密[10–13]. 在文献[10] 与文献[14] 中, 将一个密文矩阵(Expand) 操作, 产生一个新的密文,并将密钥级联成组合密钥, 用组合密钥解密扩展后的密文可以得到正确的解密结构, 而且多密钥全同态加密方案的密文会随着不同的密钥数的增长而膨胀, 同态计算后的密文不能继续执行同态运算. 以上都是对单比特明文进行全同态加密, 而全同态加密方案一个最重要的问题就是效率问题, 单个比特的加密使得同态操作的效率很低, 为了提高全同态加密的计算效率, 人们提出了“密文打包” 的方法[15], 即将多个明文装入到一个密文中. 该方法使得对密文执行一次同态操作, 相当于并行对多个明文执行同样的操作. 本文基于2017 年李增鹏等人发表的基于Dual.LWE 多比特层次型全同态加密方案[16], 通过修改其加密算法使之成为无CRS 模型多比特全同态加密方案. 利用LinkAlgo 算法[17]对其密文进行密文扩展操作形成一个新的密文(多密钥密文), 从而设计出一种支持多比特多密钥全同态加密方案.

3 符号说明

4 MBGSW 方案

4.1 MBGSW 方案的正

4.2 MBGSW 方案安全性

5 用LinkAlgo 算法将上述多比特单密钥密文扩展成多比特多密钥密文

矩阵R ∈{0,1}n×N,V(s,t)是R(s,t)在(pk,sk)=(P,˜t)下用GSW 加密算法[4]下加密的β噪音密文, 即V(s,t)=PTR+R[s,t]G, 其中(s ∈[n],t ∈[N]). 设(pk′,sk′)=(P′,˜t′)为另一对密钥. LinkAlgo算法输入pk′和所有的V(s,t)∈Z(m+1)×Nq,输出Y使得STY=STP′TR+e,‖e‖∞≤m3β（(e为噪音).

算法1 LinkAlgo 算法Input: pk′ 和{V (s,t)}s∈[n],t∈[N]Output: Y ∈Z(m+1)×N q(1) 定义Ls,t ∈Z(m+1)×N q, 其中s ∈[n],t ∈[N]{Ls,t[a,b] =P′[a,s];t = b 0;其他(2) 输出Y =n∑N∑s=1t=1 V (s,t)G-1(Ls,t) ∈Z(m+1)×Nq

6 MMFHE 方案

-MMFHE.Eval(params, f,ˆC1,··· ,ˆCl)→(ˆC*):

6.1 方案的安全性:

6.2 密文扩展的正确性:

7 结论

本文基于Dual.LWE 假设提出来一个支持多比特加密的多密钥全同态加密方案, 该方案是选择明文攻击安全的. 相对于传统的单比特单密钥全同态加密方案, 该方案实现多比特多密钥全同态加密, 但该方案的运行效率与实际应用还有一定的差距, 进一步提高全同态加密方案的效率和安全性仍然是全同态加密技术研究的重点与难点.