车小亮，周昊楠，杨晓元，周潭平，刘龙飞，李宁波

(1.武警工程大学 密码工程学院，陕西 西安 710086；2.网络和信息安全武警部队重点实验室，陕西 西安710086)

LOPEZ-ALT等[1]首次提出了多密钥全同态加密(Multi-Key Fully Homomorphic Encryption，MKFHE)的概念，它支持对不同用户(不同密钥)的密文进行任意的同态运算，且运算之后的结果由参与计算的所有用户联合解密，可用于安全多方计算[2]、隐私保护[3-4]等场景，具有重要的理论研究价值和应用价值。

LTV12方案是基于NTRU密码体制设计的首个MKFHE方案[1]，之后DORÖZ等对其全同态运算进行了优化，提出了DHS16方案[5]。CHONGCHITMATE等基于此类型的MKFHE构造了具有电路隐私特性的三轮动态安全多方计算协议的CO17方案[6]。CHE等利用比特丢弃技术和密文维度扩展方法构造了一类无需密钥交换的NTRU型多密钥全同态加密方案[7]。这些NTRU型MKFHE方案，密文量和密钥量相对较少，加解密速度快，但其安全性是基于多项式环上的非标准性假设，并且无法构造高效的联合解密协议，实际应用受限。2015年，CLEAR和MCGOLDRICK根据GSW13方案[8]提出了首个基于LWE问题的GSW(Gentry-Sahai-Waters)型MKFHE方案CM15[9]，给出了从GSW型FHE到MKFHE的转化模式。2016年，MUKHERJEE等简化了CM15方案，提出了满足一轮门限解密协议的MW16方案[10]。同年，PEIKERT等提出了满足多跳(multi-hop)功能的PS16方案[11]，BRAKERSHI等进一步缩减了密文的增长规模，提出了全动态(fully dynamic)的BP16方案[12]。这些GSW型MKFHE方案安全性高，运算过程无需进行密钥交换，但密文规模随用户数量增长较快，加解密速度较慢、同态运算效率不高。2016年亚密会上，CHILLOTTI等基于GSW13方案在T=(0，1]环上的变种TGSW，构造了全同态方案CGGI16[13]，具体呈现了全同态方案自举过程的运算效率，并于2017年编写了全同态加密软件库TFHE[14]。……