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

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

（*通信作者电子邮箱smo_mrche@yeah.net）

0 引言

多密钥全同态加密（Multi-Key Fully Homomorphic Encryption，MKFHE）方案支持对不同用户的密文进行任意的同态运算，且运算之后的结果必须由参与计算的所有用户联合解密，可以较好地解决多用户密文进行同态计算的问题［1-2］。基于NTRU（Number Theory Research Unit）的多密钥全同态加密方案是基于多项式的加解密运算，密文和密钥量小，加解密结构简单，是公认的基于格的运算速度较快的加密方案之一，具有较强的实用性。

NTRU 型MKFHE 最初是由López-Alt 等［3］提出的，被称为LTV12（López-alt-Tromer-Vaikuntanathan）方案，其安全性基于2 的幂次多项式环上的LWE（Learning With Errors）问题［4］和DSPR（Decisional Small Polynomial Ratio）假设问题［3］。DSPR假设是非标准性假设，Stehlé 等［5］已经证明了在特定条件下DSPR 假设可以规约到RLWE（Ring Learning With Errors）困难问题。但2 的幂次分圆多项式环无法抵御子域攻击［6-7］，且可选环较少，致使NTRU 型同态加密方案的安全基础受到了威胁。2017 年，Yu 等［8］提出基于素数次分圆多项式环上的NTRU 方案，该类环可有效应对子域攻击威胁，但参数选取较大；同年，Yu等［9］又相继提出了基于素数幂次分圆多项式环的NTRU 方案，该类环能有效抵御子域攻击的同时，使得密文密钥等参数尺寸与2 的幂次分圆多项式环上参数尺寸选取在同一量级，且可选环较多。本文研究NTRU 型多密钥加密方案的解密结构的安全基础即是基于素数幂次分圆多项式环上的困难问题。

另外，LTV12方案在进行解密运算时运算复杂度高，产生的噪声大，计算效率具有很大提升空间。……