基于NTRU的多密钥同态加密算法设计技术资料及实验代码

Ducas和van Woerden (ASIACRYPT 2021) 最近对NTRU格提出的攻击表明，对于大于所谓疲劳点 n^{2.484+o(1)} $ 的模数q，NTRU的安全性明显低于(环)LWE。与通常位于NTRU格安全区域（即 q < n^{2.484+o(1)}）的基于NTRU的PKE不同，现有的基于NTRU的多密钥全同态加密(MK-FHEs)需要 q = O(n^k)（对于 k 个密钥），其安全性可能受到这些攻击的显著影响。项目首先提出了一种基于（矩阵）NTRU的MK-FHE方案，支持超常数数量 k 的密钥，且不使用过度拉伸的NTRU参数。我们的方案本质上是遵循TFHE/FHEW的两层框架，结合了两个组件：（1）一个简单的第一层基于矩阵NTRU的加密，天然支持多密钥NAND操作，且模数 q = O(k \cdot n^{1.5})仅与密钥数量 k 线性相关；（2）一个关键的第二层基于NTRU的加密，支持单密钥密文和多密钥密文之间的高效混合乘积，用于门自举。该数据集对于项目提出的上述技术进行了实验验证，实验结果表明，在相同的100比特安全级别下，对于 k = 8 ，项目提出的MK-FHE方案可以在笔记本电脑上在0.54秒内自举一个密文，并且自举密钥大小仅为13.89MB，这分别比Chen、Chillotti和Song (ASIACRYPT 2019) 提出的MK-FHE方案（其依赖于环LWE假设的第二层加密）快2.2倍且小7.4倍。相关实验室结果有力支撑了项目任务二研究指标的完成。