Recent Development of Theory and Application on Homomorphic Encryption
-
摘要:
随着云计算、云存储等各类云服务的普及应用,云环境下的隐私保护问题逐渐成为业界关注的焦点,同态密码成为解决该问题的关键手段,其中,如何构造高效的全同态加密方案是近年来同态加密研究的热点之一。首先,该文介绍了同态密码的发展情况,从不同角度对同态加密方案进行了分类分析,着重描述了可验证全同态加密方案的研究进展。通过分析近年来公开的同态加密领域知识产权文献,对同态加密在理论研究和实际应用中所取得的进展进行了归纳总结。其次,对比分析了目前主流全同态加密库Helib, SEAL以及TFHE的性能。最后,梳理了同态加密技术的典型应用场景,指出了未来可能的研究与发展方向。
Abstract:With the popularization of various cloud services such as cloud computing and cloud storage, privacy preservation issues in the cloud environment have gradually become the focus of industrial applications. Homomorphic encryption has become an important method to solve this issue. Among them, how to construct an efficient fully homomorphic encryption scheme is one of the hotspots at present. Firstly, the development of homomorphic encryption is introduced. The homomorphic encryption schemes are analyzed and classified from different perspectives. The research progress of verifiable fully homomorphic encryption schemes is discussed in detail. By analyzing the property rights literature on homomorphic encryption that has been published in recent years, the progress in the theoretical research and application about homomorphic encryption are summarized. Secondly, the working performances of three typical homomorphic encryption libraries, Helib, SEAL and TFHE, are compared and analyzed. Finally, various application scenarios of homomorphic encryption technology are sorted out, and possible research and development directions in the future are proposed.
-
1. 引言
随着移动通信业务需求的迅速增长,对信息传输的频谱效率和能量聚集度提出了更高的要求,如何实现更加灵活、高效的通信已成为现阶段通信研究的热点问题[1-3]。近年来,围绕如何提高频谱效率和能量聚集度,一系列解决方案相继被提出。一方面,从提升信号能量聚集度的角度出发,一系列高灵活性、高能量聚集性的调制方法被提出,统一滤波多载波(Universal Filtered Multi-Carrier, UFMC)[4]、广义频分复用(Generalized Frequency Division Multiplexing, GFDM)[5]、基于椭圆球面波函数的多载波调制(Multi-Carrier Modulation based on Prolate Spheroidal Wave Functions, MCM-PSWFs)[6,7]等。其中,相比于UFMC,GFDM,MCM-PSWFs将具有完备正交性、时域奇偶对称性和最佳时频能量聚集性等优良基础特性的椭圆球面波函数(Prolate Spheroidal Wave Functions, PSWFs)[7-9]作为基础信号,具有信号波形设计灵活、高能量聚集性以及高系统频带利用率(Spectral Efficiency, SE)[7]的优势,非常符合下一代通信系统对能量聚集度的需求,具有巨大的应用潜力,极具有应用前景[6,7]。另一方面,从拓展信息映射维度、提高系统频带利用率角度出发,Nyquist传输(Faster Than Nyquist, FTN)[10]、时域波形复用技术(OVerlapped Time Domain Multiplexing, OVTDM)[11]、多载波索引调制(Multi-Carrier Modulation with Index Modulation, MCM-IM)[12-14]等高系统频带利用率的信号波形相继被提出。其中,相比于FTN,OVTDM,MCM-IM作为空间索引调制的拓展[12],具有同时利用信号索引和多进制调制符号来进行信息映射,大幅提升系统频带利用率的优势[14]。
为进一步提升MCM-PSWFs的系统频带利用率,鉴于MCM-PSWFs,MCM-IM的上述优势,文献[15]将IM引入MCM-PSWFs,提出了基于信号分组优化的PSWFs多载波调制方法(Multi-Carrier Modulation based on PSWFs with Signal Grouping Optimization, MCM-PSWFs-SGO)。本方法首先对PSWFs信号进行分组优化,再利用信号索引、脉冲幅度调制2个维度进行信息映射,具有高能量聚集度、高频谱效率的优势。尽管如此,由于部分未被激活的子载波没有用来传递信息,MCM-PSWFs-SGO仍有部分频谱资源可进一步被利用,这在一定程度上限制了其系统频带利用率的提升。在解决基于正交频分复用(Orthogonal Frequency Division Multiplexing, OFDM)的索引调制[15]存在的频谱资源未被充分利用的问题中,清华大学的Mao等人[16]提出了双模辅助的OFDM索引调制技术(Dual-Mode index modulation aided OFDM, DM-OFDM),其主要思想是采用两个互不重叠的星座图进行比特信息映射的方式,使得全部子载波均被利用,有效解决了频谱资源未被充分利用的问题,实现了系统频带利用率的进一步提升。这为解决MCM-PSWFs-SGO的频谱资源得到进一步利用问题提供了很好的思路。
围绕如何提高MCM-PSWFs-SGO的系统频带利用率,本文将DM-IM[16]引入MCM-PSWFs-SGO,提出双模PSWFs多载波索引调制方法(Multi-Carrier index Modulation based on PSWFs with Dual-Mode, DM-MCM-PSWFs),利用双星座图进行比特信息映射,有效增加了调制符号组合数,进一步提高了系统频带利用率。采用第2星座图对剩余子载波进行额外的信息加载,实现了频谱资源的进一步利用,同时提高了调制符号间的最小欧氏距离(Minimum Euclidean Distance, MED)。理论与仿真分析表明,相比于MCM-PSWFs-SGO,所提方法在具有相同功率谱与峰均功率比的前提下,以增加计算复杂度为代价,具有更优的系统频带利用率与误码性能。
2. DM-MCM-PSWFs调制解调与检测方法
MCM-PSWFs-SGO系统频带利用率提升受限的原因在于,采取单星座图对激活子载波进行信息加载,其余未被激活子载波则未被利用,频谱效率尚有提升空间。因此,如何利用未被激活的PSWFs信号传输额外的调制符号,是进一步提升MCM-PSWFs-SGO系统频带利用率的关键。
2.1 DM-MCM-PSWFs调制方法
图1(a)给出了DM-MCM-PSWFs发射端原理框图,图1(b)为接收端框图。该方法引入双星座图映射,通过2个星座图分别产生调制符号,对全部子载波进行信息加载,利用I/Q两个支路进行分别传输,且采用相同的信号索引结构[15]。
考虑到PSWFs信号分组数、每组信号路数、调制星座图进制数以及激活信号路数等参数直接决定系统整体性能,需要依据可用时频资源大小、系统整体性能需求,进行整体的设计和选择[15]。为便于分析,假设可用时宽为
T(s) 、带宽为B(Hz) ,信号分组数g 、每组信号路数为n 、每组激活的信号路数为k ,两种星座图的调制阶数相同,且均为M 。在发射端,首先进行PSWFs信号的分组、选择过程,该过程与文献[15]中处理过程相同。将输入2m(bit)待传信息比特平均分为g组,每组包含
p′=2m/g=pI+pQ(bit) 信息,其中pI=pQ=p,pI= pα,I,1+pα,I,2 ,pQ=pα,Q,1+pα,Q,2 ,α∈[1,g] ,pα,I/Q,1 为I/Q支路信号索引部分携带信息量,pα,I/Q,2 为两个星座图产生的调制符号携带的信息量,如图1(a)所示;而后,进行双星座图设计与比特信息映射,生成调制符号,并产生DM-MCM-PSWFs调制信号。(1)星座图设计与比特信息映射:与MCM-PSWFs-SGO不同,DM-MCM-PSWFs将原有的单一星座图调制方法变更为双星座图调制,由额外的星座图对原本未被利用的子载波进行信息加载,如图2所示。为保证接收端能够顺利解调和检测出信号索引比特所携带的信息,需对选取的两个星座图有所区分,因此,选择的两个星座图必须满足互不重叠的关系。
下面对所提方法具体调制流程进行说明。首先,依据每组PSWFs信号路数
n 、激活PSWFs信号路数k ,设计DM-MCM-PSWFs信号索引方案[15]。则I/Q支路信号索引与由两个星座图分别产生的调制符号携带的信息量为pα,I,1=pα,Q,1=⌊log2Ckn⌋(bit),pα,I,2=pα,Q,2=pα,I,A,2+pα,I,B,2=pα,Q,A,2+pα,Q,B,2=(n−k)log2M+klog2M(bit) (1) 其中,
pα,I/Q,A,2,pα,I/Q,B,2 分别表示由第1/2星座图所生成调制符号携带的信息量。从而,信号索引部分依据
pα,I,1,pα,Q,1(bit) ,从第α 子块对应的n 个PSWFs信号中选择k 个加载第2星座图产生的调制符号,同时由剩余的n–k个PSWFs信号加载第1星座图产生的调制符号。其中,PSWFs信号索引可以表示为II,α={iI,α,1,iI,α,2,⋯,iI,α,n}IQ,α={iQ,α,1,iQ,α,2,⋯,iQ,α,n}} (2) 其中,
II/Q,α,γ 表示第α 个子块,编号为γ∈[1,n] 的PSWFs信号由第1/2星座图进行调制符号映射。若II/Q,α,γ=0 ,则代表该位置的子载波传输由第1星座图产生的调制符号;若II/Q,α,γ=1 ,则代表该位置的子载波传输由第2星座图产生的调制符号。鉴于I/Q支路采用相同的信号索引结构,故以I支路为例,表1给出了n=4,k=2时DM-MCM-PSWFs的映射方案。表 1 n=4,k=2时DM-MCM-PSWFs的一种映射方案比特信号 信号索引 子载波映射 [0,0] {0,0,1,1} {sAI(1),sAI(2),sBI(1),sBI(2)} [0,1] {0,1,0,1} {sAI(1),sBI(1),sAI(2),sBI(2)} [1,0] {1,0,0,1} {sBI(1),sAI(1),sAI(2),sBI(2)} [1,1] {0,1,1,0} {sAI(1),sBI(1),sBI(2),sAI(2)} (2)调制信号产生:在调制信号产生部分,I/Q支路信息序列
pα,I,2 ,pα,Q,2 (bit)经双星座图调制产生的调制符号可表示为Sα,I={sAI(λ),sBI(β)},Sα,Q={sAQ(λ),sBQ(β)} (3) 其中,
λ=1,2,⋯,n−k 且β=1,2,⋯,k ,sAI(λ),sBI(β), sAQ(λ),sBQ(β) 分别由所选择的两个星座图定义。图3给出了双星座图的调制符号加载流程,其中,sα,I,A,sα,I,B,sα,Q,A,sα,Q,B 分别表示I/Q支路内两个星座图生成调制符号的集合。进而,子块调制符号产生第
α 个子块的调制符号Xα∈Cn×1 ,如图3所示,即Xα=[xI,α(1)+ixQ,α(1),⋯,xI,α(n)+ixQ,α(n)]T (4) 其中,
xI/Q,α(γ)∈S ,γ∈[1,n] 。最后,产生全部g 个子块、ng 支路PSWFs信号对应的调制符号X= [(X1)T,(X2)T,⋯,(Xg)T]T ;并采用基于奇偶对称性的调制信号产生方法[9],生成DM-MCM-PSWFs调制信息,即s(t)=gn−1∑i=0x(i+1)φi(t) (5) 其中,
φi(t) 为第i 阶PSWFs信号。2.2 DM-MCM-PSWFs调制信号的解调与检测方法
图1(b)给出了调制信号的解调与检测的原理框图。与MCM-PSWFs-SGO不同,DM-MCM-PSWFs采取基于极大似然 (Maximum Likelihood, ML)[15]的信号索引检测方法,对所有可能的信号索引方案进行遍历,以最小化接收信号与样本信号之间的欧氏距离,恢复出信号索引方式,即
{ˆII/Q,α,ki,ˆsI/Q,α,ki,DI/Q,α,ki}=argminII/Q,α,ki,sI/Q,α,kin∑γ=1|Re{[y]υ,υ}−sI/Q,α(υ)|2 (6) 其中,
DI/Q,α,ki 为{ˆII/Q,α,ki,ˆsI/Q,α,ki} 的欧氏距离,y∈Cng×1 为接收端不同PSWFs信号对应的调制符号。进而,根据恢复出的信号索引方案,在对应的子载波映射位置上分别进行两个星座图的解调,最后恢复出接收端调制信号所携带的全部比特信息。值得注意的是,由于所提方法需要进行额外星座图的解调与检测处理,其调制信号解调与检测的计算复杂度将高于MCM-PSWFs-SGO,该部分问题将于第3节详细讨论。
3. 系统性能分析
本节从系统频带利用率、系统误码性能、信号索引检测复杂度、调制信号功率谱与峰均功率比(Peak-to-Average Power Ratio, PAPR)4个方面,对比分析了双模PSWFs多载波索引调制方法与基于信号分组优化的PSWFs多载波调制的性能差异。此外,鉴于索引调制方法具有最优参数选择的特点,为更加全面地分析所提方法系统性能,本节还对比分析了所提方法与基于PSWFs的正交多载波调制(Multi-Carrier Orthogonal Modulation based on PSWFs, MCOM-PSWFs)[6,7]间的性能差异。
3.1 系统频带利用率分析
假设采用的PSWFs信号时间带宽积为
c=B/F(Hz⋅s) ,根据PSWFs分组优化方法[15],当传输码元周期个数为Q 时,不同调制方法的系统频带利用率可统一表示为η=QmeQT(B+F) (7) 其中,
T 为单个码元周期调制信号时宽,me 为单个码元周期调制符号携带信息量,对于不同的调制方法,me 分别为me,1=2g(⌊log2Ckn⌋+(n−k)log2M+klog2M)me,2=2g(⌊log2Ckn⌋+klog2M)me,3=(c−l)log2M} (8) 式中,
me,1 ,me,2 ,me,3 分别代表所提方法、MCM-PSWFs-SGO和MCOM-PSWFs单个码元周期调制符号携带信息量。(1)与基于PSWFs的正交多载波调制(MCOM-PSWFs)相比:结合式(7)和式(8)可知,所提方法的系统频带利用率由
c−l,M,n,k 共同决定,通过合理的参数选择,能够保证me,1>me,3 ,当MCOM-PSWFs采用8QAM,n=6,k=3 时,SE提升了8.4%,BER则提升了0.47 dB,如表2所示。表 2 不同多载波调制方法系统频带利用率调制方法 g n k SE(bit/s/Hz) Eb/N0(dB) ρ(%) DM-MCM-PSWFs 15 6 3 3.09 11.98 / MCM-PSWFs-SGO-2PAM 9 10 7 2.41 11.05 28.2 MCM-PSWFs-SGO-4PAM 23 4 1 1.90 13.46 62.6 23 4 2 2.85 14.95 8.4 MCOM-PSWFs-8QAM 1 92 92 2.85 12.45 8.4 (2)与基于信号分组优化的椭圆球面波多载波调制解调与检测方法(MCM-PSWFs-SGO)相比:MCM-PSWFs-SGO与所提方法的系统频带利用率均由
c−l,M,n,k 共同决定,当M 相同时,根据式(7),所提方法的系统频带利用率将大于MCM-PSWFs-SGO。当MCM-PSWFs-SGO的调制阶数M 为所提方法的两倍时,二者的系统频带利用率关系将分为以下3种情况:第1种,当k<n/2 时,所提方法的系统频带利用率仍高于MCM-PSWFs-SGO;第2种,当k=n/2 时,二者拥有相同的系统频带利用率;第3种,当k>n/2 时,所提方法的系统频带利用率将低于MCM-PSWFs-SGO。值得一提的是,在后两种情况中,尽管所提方法的系统频带利用率并不高于MCM-PSWFs-SGO,但其在误码性能方面始终保持显著优势,这一性能将在下一小节详细阐述。表2给出了带宽为
B=1.44MHz ,频率间隔为F=15kHz ,BER=10−5 时不同参数条件下,3种调制方法的系统频带利用率对比。其中,l=4 ,ρ 表示相比于另外两种调制方法,所提方法对系统频带利用率的提升。3.2 系统误码性能分析
鉴于MED能够反映调制方法的误码性能,本节选用MED对不同调制方法的系统误码性能进行分析。图4给出了未进行信道编码情况下的不同调制方法系统误码性能。其中,DM-MCM-PSWFs采用如图3所示的星座图;并且,为保证MCOM-PSWFs与所提方法的系统频带利用率相同,MCOM-PSWFs采用QAM来产生调制符号,QAM的进制数为
(ξ+log2M)(ξ−1+log2M) 。其中,ξ 为ξ≥1 的正整数。当每比特信息对应的能量为Eb 时,不同调制方法的MED可表示为d21=244(log22M1)2−1⋅2⌊log2CknMn1⌋Ebnd22=124(log2M2)2−1⋅2⌊log2CknMk2⌋Ebkd23=12log2M3⋅Eb2(ξ+log2M)2+2(ξ−1+log2M)2−1} (9) 其中,
d21 ,d22 ,d23 分别为所提方法、MCM-PSWFs-SGO和MCOM-PSWFs的MED,M1 ,M2 ,M3 分别为所提方法、MCM-PSWFs-SGO和MCOM-PSWFs的调制阶数。(1)与基于PSWFs的正交多载波调制(MCOM-PSWFs)相比:由式(9)可知,所提方法与MCOM-PSWFs的MED比值为
d21d23=4⌊log2CknMn1⌋4(log22M1)2−1⋅[2(ξ+log2M)2+2(ξ−1+log2M)2−1]log2Mn3 (10) 为保证MCOM-PSWFs与所提方法的系统频带利用率相同,MCOM-PSWFs采取8QAM星座图,此时取
M3=8,M1=2 。由于4⌊log2Ckn⌋+4n>3n ,故式(10)结果大于1。这表明所提方法在信号的MED高于MCOM-PSWFs。值得注意的是,由于DM-MCM-PSWFs中信号索引部分的存在,其在小信噪比下易产生信号索引方案检测错误的现象,所以此时影响系统误码性能的主导因素是信号索引方案检测性能,在此情况下,即使后续调制符号解调未发生错误,但由于映射位置已经发生改变,所恢复的比特信息也可能产生错误;在大信噪比情况下,能够保证信号索引检测结果的准确性,此时影响系统误码性能的主导因素是调制符号的MED,因此,在系统频带利用率相同的情况下,所提方法误码性能在大信噪比下要优于MCOM-PSWFs。当所提方法与MCOM-PSWFs的系统频带利用率均为2.85 bit/s/Hz时,BER提升约为0.23 dB,如图4(a)所示。(2)与基于信号分组优化的椭圆球面波多载波调制(MCM-PSWFs-SGO)相比:由式(9)可知,所提方法与MCM-PSWFs-SGO的MED比值为
d21d22=4(log2M2)2−14(log22M1)2−1⋅2⌊log2CknMn1⌋⌊log2CknMk2⌋⋅kn (11) 同样,为保证MCM-PSWFs-SGO与所提方法的系统频带利用率相同,MCM-PSWFs-SGO选取4PAM为星座图,则式(11)可以化简为
d21d22=2k⌊log2Ckn⌋+2knn⌊log2Ckn⌋+2kn (12) 由式(12)可知,当
k=n/2 时,二者拥有相同的MED;当k>n/2 时,所提方法的系统MED将大于MCM-PSWFs-SGO。然而,由于MCM-PSWFs-SGO中置0点的存在,其信号索引检测性能要差于所提方法,这意味着,当所提方法与MCM-PSWFs-SGO系统频带利用率相同时,所提方法具有更优的误码性能。更进一步,当二者选取相同的PAM调制符号时,所提方法在频带利用率相同时的误码性能要始终优于MCM-PSWFs-SGO。在n=4,k=2 与n=8,k=4 时,二者具有相同系统频带利用率,所提方法的误码性能相比于MCM-PSWFs-SGO分别提升约2.71 dB, 2.55 dB,如图4(a)、图4(c)所示。此外,鉴于索引调制方法的系统性能与参数条件的选择密切相关,因此,在参数优选的情况下,所提方法能够实现系统频带利用率与误码性能的双重提升。如当
n=7,k=3 时,所提方法相对于MCM-PSWFs-SGO,SE提高了0.27 bit/s/Hz,BER提高了2.40 dB;相对于MCOM-PSWFs,SE提高了0.37 bit/s/Hz,BER提高了0.35 dB,如图4(b)所示。当n=9,k=4 时,所提方法相对于MCM-PSWFs-SGO,SE提高了0.20 bit/s/Hz,BER提高了2.26 dB;相对于MCOM-PSWFs,SE提高了0.24 bit/s/Hz,BER提高了0.22 dB,如图4(d)所示。3.3 系统信号索引检测复杂度分析
由于MCOM-PSWFs不存在索引部分,因此DM-MCM-PSWFs与MCM-PSWFs-SGO的算法复杂度均高于MCOM-PSWFs。现对比所提方法与MCM-PSWFs-SGO的信号索引检测复杂度。表3给出了带宽为
B=1.44MHz ,频率间隔为F=15kHz 时不同参数条件下,所提方法与MCM-PSWFs-SGO两种调制方法的信号索引检测乘法复杂度[15],其中,l=4 。表 3 信号索引检测乘法运算量调制方式 运算量 n k 乘法次数(B=1.44 MHz) DM-MCM-PSWFs-ML O(ng2⌊Ckn⌋) 4 1/2/3 368 MCM-PSWFs-SGO-ML O(2kg2⌊Ckn⌋) 4 1 184 4 2 368 4 3 552 MCM-PSWFs-SGO-OS O(gnlog2n) 4 2 16 当激活子载波数
k<n/2 时,MCM-PSWFs-SGO的基于ML的信号索引检测的乘法复杂度要低于所提方法;当k=n/2 时,二者的乘法复杂度相等;k>n/2 时,MCM-PSWFs-SGO的基于ML的信号索引检测的乘法复杂度要高于所提方法,如表3所示。但在针对MCM-PSWFs-SGO的信号索引检测方法中,基于顺序统计量(Order Statistic, OS)[17]的检测方法作为一种ML的替代检测方法,在大幅度降低系统运算复杂度的情况下能够达到和ML相同的检测性能。因此,结合前两节关于3种调制方法频带利用率与误码性能的分析可知,所提方法是以较高的计算复杂度换取了系统频带利用率与误码性能的双重提升。3.4 调制信号功率谱与峰均功率比分析
图5给出了DM-MCM-PSWFs与MCM-PSWFs-SGO的调制信号功率谱和峰均功率比。其中,F=15 kHz, c=12Hz·s, l=3, n=8, k=4。仿真分析表明,DM-MCM-PSWFs具有与MCM-PSWFs-SGO相同的调制信号功率谱和峰均功率比,并且拥有同样高能量聚集度的优势。
4. 结束语
本文提出双模PSWFs多载波索引调制方法,采用两个互不重叠的星座图进行比特信息映射,使得全部子载波均得到利用,完成了对MCM-PSWFs-SGO中频谱资源的进一步利用,实现了系统频带利用率和大信噪比下的误码性能的双重提升。虽然仍存在较高的计算复杂度,但这是当前硬件条件和计算能力可以承受的。相比于基于信号分组优化的PSWFs多载波调制、基于PSWFs的正交多载波调制,本文具有更优的系统整体性能,有望为下一代通信系统提供更加灵活、高效的调制方法,实现更高频谱效率与能量聚集度的信息传输。
值得注意的是,本方法仍有进一步提升的空间,由于所提方法并未对MCM-PSWFs-SGO中的分组优化方法与信号索引方案进行改变,每个子块的PSWFs信号仍然被分成了功能不同的两个部分,这也限制了能够采用的信号索引方案的数量。因此,如何引入多星座图进行比特信息映射,进一步提升所提方法的频谱效率,将是下一步研究所关注的重点。此外,由于本方法在低信噪比下的误码性能仍有提升的空间,因此,如何对信号索引检测进行优化,进一步提升系统整体误码性能,也是下一步工作重点。
-
表 1 提高全同态加密效率的解决方案
方式 解决方案 优化Bootstrapping Gentry09[2]:首次提出Bootstrapping Ducas15[12]:运行时间从6 min缩短至1 s以内 Chillotti16[13]:运行时间从1 s以内缩短至0.1 s以内,密钥大小从1 GB减小至24 MB Chen18[14]:自举深度从log2h+2log2t降至log2h+log2t Batching Smart14[15]:构造可支持SIMD操作的FHE方案 Castryck18[16]:提高了明文封装容量和参数优化灵活性 无噪声FHE Kipnis12[18]:基于矩阵和多项式的无噪声FHE方案MORE和PORE Gentry14[20]:基于完备群概念的无噪声FHE框架 FPGA设计 Shi18[24]:16×24 bit有限域FFT算法的FPGA设计 Xie19[25]:768 kbit大整数乘法器FPGA设计 表 2 全同态加密在整数域和实数域上的研究进展
类型 解决方案 明文空间为整数的FHE Gentry10[27]:第1个基于整数的FHE方案DGHV方案 Cheon13[28]:将批处理技术引入DGHV方案 Nuida15[29]:将DGHV方案的明文空间从Z2扩展至ZQ Cheon15[31]:将LWE问题归约为AGCD问题的一个变体 明文空间为实数的FHE Jaschke16[33]:通过与2的幂迭代相乘近似将有理数表示为整数 Dowlin17[34]:将定点小数编码为整系数多项式,但明文模随电路深度的增加呈指数增大 Cheon17[35]:可进行浮点数近似计算的CKKS方案,但仅为层次型FHE方案 Cheon18[36]:将文献[35]中的层次型同态加密方案扩展为全同态加密方案 表 3 可验证同态加密研究进展
解决方案 研究进展 存在问题 Johnson02[41] 首次提出同态签名的概念 – Boneh11[42] 首个可执行确定阶数多项式运算的同态签名方案 – Gneearo13[43] 形式化定义了同态消息认证的概念 – Catalano13[44] 支持低次多项式运算的同态MAC方案 不能同时满足简洁性和复合性 Catalano14[46] 引入了一个新的密码学原语LAEPuV – Joo14[48] 首次给出在HAE中IND-CPA和IND-CCA的定义 – Bai18[45] 基于默克尔哈希树的同态认证方案 复合度上有所不足 Fiore16[50] 提出多密钥同态认证(M-HS)方案 可能存在不可信签名者 Lai18[51] 基于零知识证明提出了一种M-HS通用结构 没有分析其认证安全性和实用性 Alagic17[52] 可验证的量子全同态加密方案 – 表 4 同态加密相关的知识产权聚焦的不同应用领域
表 5 Test_Timing效率测试结果(μs)
m 密钥生成 加密 解密 同态加 同态乘 4051 317037 6786 4039 97 26701 4369 571082 8041 5173 98 31477 4859 664138 10497 7554 193 41354 表 6 SEAL中BFV方案效率测试(μs)
Poly Coeff Plain 加密 解密 同态加 同态乘 重线性化 4096 109 786433 93464 32306 314 390192 63711 8192 218 786433 267727 112898 1074 1510281 319876 16384 438 786433 884862 439232 4341 6146131 1846517 表 7 SEAL中CKKS方案效率测试(μs)
Poly Coeff 加密 解密 同态加 同态乘 重线性化 4096 109 87557 3359 309 12476 63459 8192 218 274215 12748 1071 47599 314501 16384 438 964821 51465 4317 200248 1850888 -
RIVEST R L, ADLEMAN L, and DERTOUZOS M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978, 4(11): 169–180. GENTRY C. A fully homomorphic encryption scheme[D]. [Ph. D. dissertation]. Stanford University, 2009. BRAKERSKI Z and VAIKUNTANATHAN V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[C]. The 31st Annual Cryptology Conference, Santa Barbara, USA, 2011: 505–524. doi: 10.1007/978-3-642-22792-9_29. BRAKERSKI Z and VAIKUNTANATHAN V. Efficient fully homomorphic encryption from (standard) LWE[C]. The 52nd IEEE Annual Symposium on Foundations of Computer Science, Palm Springs, USA, 2011: 97–106. doi: 10.1109/FOCS.2011.12. PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes[C]. International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, 1999: 223–238. doi: 10.1007/3-540-48910-X_16. 李增鹏, 马春光, 周红生. 全同态加密研究[J]. 密码学报, 2017, 4(6): 561–578. doi: 10.13868/j.cnki.jcr.000208LI Zengpeng, MA Chunguang, and ZHOU Hongsheng. Overview on fully homomorphic encryption[J]. Journal of Cryptologic Research, 2017, 4(6): 561–578. doi: 10.13868/j.cnki.jcr.000208 GENTRY C, SAHAI A, and WATERS B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[C]. The 33rd Annual Cryptology Conference, Santa Barbara, USA, 2013: 75–92. doi: 10.1007/978-3-642-40041-4_5. 宋新霞, 陈智罡. 基于抽象解密结构的全同态加密构造方法分析[J]. 电子与信息学报, 2018, 40(7): 1669–1675. doi: 10.11999/JEIT170997SONG Xinxia and CHEN Zhigang. Analysis of constructing fully homomorphic encryption based on the abstract decryption structure[J]. Journal of Electronics &Information Technology, 2018, 40(7): 1669–1675. doi: 10.11999/JEIT170997 李宗育, 桂小林, 顾迎捷, 等. 同态加密技术及其在云计算隐私保护中的应用[J]. 软件学报, 2018, 29(7): 1830–1851. doi: 10.13328/j.cnki.jos.005354LI Zongyu, GUI Xiaolin, GU Yingjie, et al. Survey on homomorphic encryption algorithm and its application in the privacy-preserving for cloud computing[J]. Journal of Software, 2018, 29(7): 1830–1851. doi: 10.13328/j.cnki.jos.005354 李子臣, 张卷美, 杨亚涛, 等. 基于NTRU的全同态加密方案[J]. 电子学报, 2018, 46(4): 938–944. doi: 10.3969/j.issn.0372-2112.2018.04.023LI Zichen, ZHANG Juanmei, YANG Yatao, et al. A fully homomorphic encryption scheme based on NTRU[J]. Acta Electronica Sinica, 2018, 46(4): 938–944. doi: 10.3969/j.issn.0372-2112.2018.04.023 杨亚涛, 刘博雅, 孙亚飞, 等. NTRU全同态掩码防御方案[J]. 计算机学报, 2019, 42(12): 2742–2753. doi: 10.11897/SP.J.1016.2019.02742YANG Yatao, LIU Boya, SUN Yafei, et al. Fully homomorphic masking defense scheme based on NTRU[J]. Chinese Journal of Computers, 2019, 42(12): 2742–2753. doi: 10.11897/SP.J.1016.2019.02742 DUCAS L and MICCIANCIO D. FHEW: Bootstrapping homomorphic encryption in less than a second[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 2015: 617–640. doi: 10.1007/978-3-662-46800-5_24. CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[C]. The 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016: 3–33. doi: 10.1007/978-3-662-53887-6_1. CHEN Hao and HAN K. Homomorphic lower digits removal and improved FHE bootstrapping[C]. The 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 2018: 315–337. doi: 10.1007/978-3-319-78381-9_12. SMART N P and VERCAUTEREN F. Fully homomorphic SIMD operations[J]. Designs, Codes and Cryptography, 2014, 71(1): 57–81. doi: 10.1007/s10623-012-9720-4 CASTRYCK W, ILIASHENKO I, and VERCAUTEREN F. Homomorphic SIM2D operations: Single instruction much more data[C]. The 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 2018: 338–359. doi: 10.1007/978-3-319-78381-9_13. 王励成, 李婧. 无噪声全同态加密浅析[J]. 密码学报, 2017, 4(6): 579–595. doi: 10.13868/j.cnki.jcr.000209WANG Licheng and LI Jing. Simple analysis on noiseless fully homomorphic encryptions[J]. Journal of Cryptologic Research, 2017, 4(6): 579–595. doi: 10.13868/j.cnki.jcr.000209 KIPNIS A and HIBSHOOSH E. Efficient methods for practical fully-homomorphic symmetric-key encryption, randomization, and verification[J]. Urban Research & Practice, 2012, 7(3): 255–257. NUIDA K. A simple framework for noise-free construction of fully homomorphic encryption from a special class of non-commutative groups[J]. IACR Cryptology ePrint Archive, 2014, 2017: 97. GENTRY C. Computing on the edge of chaos: Structure and randomness in encrypted computation[J]. Electronic Colloquium on Computational Complexity, 2014, 21: 106. LIU Dongxi. Practical fully homomorphic encryption without noise reduction[J]. IACR Cryptology ePrint Archive, 2015, 2015: 468. YAGISAWA M. Improved fully homomorphic encryption without bootstrapping[J]. IACR Cryptology ePrint Archive, 2017, 2017: 763. LI Jing and WANG Licheng. Noise-free symmetric fully homomorphic encryption based on noncommutative rings[J]. IACR Cryptology ePrint Archive, 2015, 2015: 641. 施佺, 韩赛飞, 黄新明, 等. 面向全同态加密的有限域FFT算法FPGA设计[J]. 电子与信息学报, 2018, 40(1): 57–62. doi: 10.11999/JEIT170312SHI Quan, HAN Saifei, HUANG Xinming, et al. Design of finite field FFT for fully homomorphic encryption based on FPGA[J]. Journal of Electronics &Information Technology, 2018, 40(1): 57–62. doi: 10.11999/JEIT170312 谢星, 黄新明, 孙玲, 等. 大整数乘法器的FPGA设计与实现[J]. 电子与信息学报, 2019, 41(8): 1855–1860. doi: 10.11999/JEIT180836XIE Xing, HUANG Xinming, SUN Ling, et al. FPGA design and implementation of large integer multiplier[J]. Journal of Electronics &Information Technology, 2019, 41(8): 1855–1860. doi: 10.11999/JEIT180836 SMART P N and VERCAUTEREN F. Fully homomorphic encryption with relatively small key and ciphertext sizes[C]. The 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, 2010: 420–443. doi: 10.1007/978-3-642-13013-7_25. VAN DIJK M, GENTRY C, HALEVI S, et al. Fully homomorphic encryption over the integers[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Riviera, France, 2010: 24–43. doi: 10.1007/978-3-642-13190-5_2. CHEON J H, CORON J, KIM J, et al. Batch fully homomorphic encryption over the integers[C]. The 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, 2013: 315–335. doi: 10.1007/978-3-642-38348-9_20. NUIDA K and KUROSAWA K. (Batch) Fully homomorphic encryption over integers for non-binary message spaces[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 2015: 537–555. doi: 10.1007/978-3-662-46800-5_21. HOWGRAVE-GRAHAM N. Approximate integer common divisors[C]. International Cryptography and Lattices Conference, Providence, USA, 2001: 51–56. doi: 10.1007/3-540-44670-2_6. CHEON J H and STEHLÉ D. Fully homomophic encryption over the integers revisited[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 2015: 513–536. doi: 10.1007/978-3-662-46800-5_20. 王彩芬, 成玉丹, 刘超, 等. 基于整数的多对一全同态加密方案[J]. 电子与信息学报, 2018, 40(9): 2119–2126. doi: 10.11999/JEIT171194WANG Caifen, CHENG Yudan, LIU Chao, et al. Multiple to one fully homomorphic encryption scheme over the integers[J]. Journal of Electronics &Information Technology, 2018, 40(9): 2119–2126. doi: 10.11999/JEIT171194 JASCHKE A and ARMKNECHT F. Accelerating homomorphic computations on rational numbers[C]. The 14th International Conference on Applied Cryptography and Network Security, Guildford, UK, 2016: 405–423. doi: 10.1007/978-3-319-39555-5_22. DOWLIN N, GILAD-BACHRACH R, LAINE K, et al. Manual for using homomorphic encryption for bioinformatics[J]. Proceedings of the IEEE, 2017, 105(3): 552–567. doi: 10.1109/JPROC.2016.2622218 CHEON J H, KIM A, KIM M, et al. Homomorphic encryption for arithmetic of approximate numbers[C]. The 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017: 409–437. doi: 10.1007/978-3-319-70694-8_15. CHEON J H, HAN K, KIM A, et al. Bootstrapping for approximate homomorphic encryption[C]. The 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 2018: 360–384. doi: 10.1007/978-3-319-78381-9_14. MÉAUX P, JOURNAULT A, STANDAERT F X, et al. Towards stream ciphers for efficient FHE with low-noise ciphertexts[C]. The 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016: 311–343. doi: 10.1007/978-3-662-49890-3_13. BROADBENT A and JEFFERY S. Quantum homomorphic encryption for circuits of low T-gate complexity[C]. The 35th Annual Cryptology Conference, Santa Barbara, USA, 2015: 609–629. doi: 10.1007/978-3-662-48000-7_30. DULEK Y, SCHAFFNER C, and SPEELMAN F. Quantum homomorphic encryption for polynomial-sized circuits[C]. The 36th Annual International Cryptology Conference, Santa Barbara, USA, 2016: 3–32. doi: 10.1007/978-3-662-53015-3_1. 薛锐, 吴迎, 刘牧华, 等. 可验证计算研究进展[J]. 中国科学: 信息科学, 2015, 45(11): 1370–1388. doi: 10.1360/N112014-00336XUE Rui, WU Ying, LIU Muhua, et al. Progress in verifiable computation[J]. Scientia Sinica Informationis, 2015, 45(11): 1370–1388. doi: 10.1360/N112014-00336 JOHNSON R, MOLNAR D, SONG D, et al. Homomorphic signature schemes[C]. Cryptographers’ Track at the RSA Conference, San Jose, USA, 2002: 244–262. doi: 10.1007/3-540-45760-7_17. BONEH D and FREEMAN D M. Homomorphic signatures for polynomial functions[C]. The 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, 2011: 149–168. doi: 10.1007/978-3-642-20465-4_10. GENNARO R and WICHS D. Fully homomorphic message authenticators[C]. The 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, 2013: 301–320. doi: 10.1007/978-3-642-42045-0_16. CATALANO D and FIORE D. Practical homomorphic MACs for arithmetic circuits[C]. The 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, 2013: 336–352. doi: 10.1007/978-3-642-38348-9_21. 白平, 张薇, 李聪. 云环境下运用基于编号Merkle Hash Tree的同态认证方案[J]. 中国科技论文, 2018, 13(2): 181–185. doi: 10.3969/j.issn.2095-2783.2018.02.013BAI Ping, ZHANG Wei, and LI Cong. Using rank-based Merkle Hash Tree into homomorphic authentication during cloud[J]. China Sciencepaper, 2018, 13(2): 181–185. doi: 10.3969/j.issn.2095-2783.2018.02.013 CATALANO D, MARCEDONE A, and PUGLISI O. Authenticating computation on groups: New homomorphic primitives and applications[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taipei, China, 2014: 193–212. doi: 10.1007/978-3-662-45608-8_11. BONEH D, FREEMAN D, KATZ J, et al. Signing a linear subspace: Signature schemes for network coding[C]. The 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, USA, 2009: 68–87. doi: 10.1007/978-3-642-00468-1_5. JOO C and YUN A. Homomorphic authenticated encryption secure against chosen-ciphertext attack[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taipei, China, 2014: 173–192. doi: 10.1007/978-3-662-45608-8_10. YANG Yatao, ZHANG Shuang, YANG Junming, et al. Targeted fully homomorphic encryption based on a double decryption algorithm for polynomials[J]. Tinghua Science and Technology, 2014, 19(05):478–485. doi: 10.1109/TST.2014.6919824. FIORE D, MITROKOTSA A, NIZZARDO L, et al. Multi-key homomorphic authenticators[C]. The 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016: 499–530. doi: 10.1007/978-3-662-53890-6_17. LAI R W F, TAI R K H, WONG H W H, et al. Multi-key homomorphic signatures unforgeable under insider corruption[C]. The 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, Australia, 2018: 465–492. doi: 10.1007/978-3-030-03329-3_16. ALAGIC G, DULEK Y, SCHAFFNER C, et al. Quantum fully homomorphic encryption with verification[C]. The 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017: 438–467. doi: 10.1007/978-3-319-70694-8_16. UNIV SEOUL NAT R and DB FOUND. Additive homomorphic encryption and decryption method based on the CO-ACD problem and apparatus using the same[P]. South Korea, KR20160017226A, 2016. CAMENISCH J L and LEHMANN A. Signature scheme for homomorphic message encoding functions[P]. US, 20180234254, 2018. CHEN Wenbin, LEI Hao, and YANG Qinqin. Method, apparatus, and system for authenticating fully homomorphic message[P]. US, 20160119346, 2016. UNIV MOHAMMED V RABAT. Quaternion-based, efficient fully-homomorphic cryptosystem[P]. Morocco, WO2018124869A1, 2018. LAINE K, PLAYER R L, and CHEN Hao. Rational number arithmetic in homomorphic encryption[P]. US, 20180131506, 2018. GENTRY C B, HALEVI S, and SMART N P. Homomorphic evaluation including key switching, modulus switching, and dynamic noise management[P]. US, 10057057, 2018. MANIATAKOS M, KONSTANTINOU C, and KELIRIS A. Systems and methods for privacy-preserving functional IP verification utilizing fully homomorphic encryption[P]. US, 20160254912A1, 2016. HOFFSTEIN J and SILVERMAN J H. Homomorphic encryption[P]. US, 20180212750, 2018. 西安电子科技大学. 基于同态加密算法的个人图像安全检索方法[P]. 中国, 108418995A, 2018.Xidian University. Homomorphic encryption algorithm-based individual image safe retrieving method[P]. China, 108418995A, 2018. 南京邮电大学, 江苏省新通智能交通科技发展有限公司. 一种云存储中基于同态加密的密文检索方法[P]. 中国, 108011713A, 2018.Nanjing University of Posts and Telecommunications, Jiangsu Xintong Intelligent Transportation Technology Development Co., Ltd. Ciphertext retrieval method based on homomorphic encryption in cloud storage[P]. China, 108011713A, 2018. 深圳市全同态科技有限公司, 胡和平. 一种全同态加密的密文查询方法和系统[P]. 中国, 106953722A, 2017.Shenzhen Quantong Technology Co., Ltd and HU Heping. Fully homomorphic encryption cryptograph query method and system[P]. China, 106953722A, 2017. HUAWEI TECH CO LTD. System and method for searching over encrypted data using homomorphic encryption[P]. China, EP3264669A1, 2018. 电子科技大学. 一种基于向量同态加密的隐私保护的线性SVM模型训练算法[P]. 中国, 108521326A, 2018.University of Electronic Science and Technology of China. Linear SVM model training algorithm for privacy protection based on vector homomorphic encryption[P]. China, 108521326A, 2018. 陈智罡. 基于全同态加密的认证方法和用户设备以及认证服务器[P]. 中国, 107819587A, 2018.CHEN Zhigang. Authentication method based on homomorphic encryption, user equipment and authentication server[P]. China, 107819587A, 2018. GILAD-BACHRACH R, DOWLIN N, LAINE K, et al. CryptoNets: Applying neural networks to encrypted data with high throughput and accuracy[C]. The 33rd International Conference on Machine Learning, New York City, USA, 2016: 201–210. 上海凭安征信服务有限公司. 一种基于加法同态加密的隐藏分散贷款额获取贷款总和的方法[P]. 中国, 107330678A, 2017.Shanghai Ping An Credit Service Co., Ltd. Method of hiding scattered loan sum and acquiring loan sum based on based on addition homomorphic encryption[P]. China, 107330678A, 2017. PATEL S and YUNG M M M. Systems and methods for a multiple value packing scheme for homomorphic encryption[P]. US, 20160359617, 2016. BACON D F, BENT G A, BERGAMASCHI F A, et al. Efficient two party oblivious transfer using a leveled fully homomorphic encryption[P]. US, 20170147835, 2017. UNIV SEOUL NAT R and DB FOUND. Method for calculating edit distance between DNA genomic sequence through homomorphic encryption[P]. South Korea, KR20170096387A, 2017. 西安邮电大学. 一种基于同态加密的智能电网用户售电方法[P]. 中国, 107172043A, 2017.Xi’an University of Posts & Telecommunications. Intelligent power grid user power-selling method based on homomorphic encryption[P]. China, 107172043A, 2017. DOW A, DOW E M, GILCHRIST J P, et al. Distributed computing utilizing homomorphic encryption[P]. US, 20160380761A1, 2016. SAMSUNG SDS CO LTD. Apparatus for generating barcode using homomorphic encryption and method thereof[P]. South Korea, KR20170048767A, 2017. 北京洋浦伟业科技发展有限公司. 基于同态加密算法保护程序代码安全的方法和装置[P]. 中国, 107124261A, 2017.Beijing Yangpu Weiye Technology Development Co., Ltd. Method and apparatus for protecting security of program code based on homomorphic encryption algorithm[P]. China, 107124261A, 2017. 南京汽车集团有限公司. 基于同态加密的信息安全传输装置、传输方法及存储方法[P]. 中国, 107682379A, 2018.Nanjing Automobile Group. Information safety transmission device and method based on homomorphic encryption and storage method[P]. China, 107682379A, 2018. BRAKERSKI Z, GENTRY C, and VAIKUNTANATHAN V. (Leveled) fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory, 2014, 6(3): 13. doi: 10.1145/2633600 HALEVI S and SHOUP V. HElib—An implementation of homomorphic encryption[EB/OL]. https://github.com/shaih/HElib/. GENTRY C, HALEVI S, and SMART N P. Homomorphic evaluation of the AES circuit[C]. The 32nd Annual Cryptology Conference, Santa Barbara, USA, 2012: 850–867. doi: 10.1007/978-3-642-32009-5_49. FAN J and VERCAUTEREN F. Somewhat practical fully homomorphic encryption[J]. IACR Cryptology ePrint Archive, 2012, 2012: 144. BRAKERSKI Z. Fully homomorphic encryption without modulus switching from classical GapSVP[C]. The 32nd Annual Cryptology Conference, Santa Barbara, USA, 2012: 868–886. doi: 10.1007/978-3-642-32009-5_50. BAJARD J C, EYNARD J, HASAN M A, et al. A full RNS variant of FV like somewhat homomorphic encryption schemes[C]. The 3rd International Conference on Selected Areas in Cryptography, St. John’s, Canada, 2016: 423–442. doi: 10.1007/978-3-319-69453-5_23. CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[C]. The 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017: 377–408. doi: 10.1007/978-3-319-70694-8_14. 期刊类型引用(2)
1. 董鹏鹏,曹瑞,张光明,丁卓航. 载波频偏和相关信道对二维索引调制的影响. 信息技术与信息化. 2024(04): 138-141+145 . 百度学术
2. 王红星 ,张力凡 ,陆发平 ,康家方 ,刘传辉 ,张磊 . 基于优化多重索引的椭圆球面波函数多载波索引调制解调方法. 电子与信息学报. 2022(12): 4185-4193 . 本站查看
其他类型引用(0)
-