主讲人：王安宇

摘要：BGV是处理整数同态运算的主要全同态加密方案之一。自举算法是实现任意深度电路同态计算的前提。同态位数消除 (digit removal) 是BGV自举算法的关键步骤和性能瓶颈。现有的BGV同态位数消除方法具有O(p^(1/2))的计算复杂度，使得在大明文素数p下BGV自举算法的运行效率较低。

本报告介绍一种基于Z_p^e环上零化多项式性质的BGV自举算法优化。具体地，我们观察到BGV同态位数消除的输入的支撑集大小具有一个近似常数的上界B，这使得我们能够构造次数远小于p的零化多项式，从而显著降低同态位数消除的运行时间和容量消耗。在渐进上，我们的优化将单次同态位数消除的复杂度从O((pe)^(1/2))（Chen and Han, EUROCRYPT 2018）或O(p^(1/2)e^(1/4))（Geelen et al., EUROCRYPT 2023）降低到min(2B+1,(e(2B+1)/t)^(1/2))，这里p^e为明文模数。在实验上，我们基于HElib对p=17,127,257,8191,65537进行了实验测试，实现表明新自举算法的吞吐量比HElib的自举提升了1.38～151倍。该工作发表于EUROCRYPT 2024。

主讲人简介：王安宇，清华大学高等研究院副研究员，主要从事密码和编码理论的研究，在密码三大会议以及IEEE TIT、CHES等高水平刊物上发表多篇论文，获2023年亚密会最佳论文奖，是中国密码学会首届推荐入选中国科协“青年人才托举工程”的青年学者之一，曾获中国科学院信息工程研究所“引进优秀青年人才”专项经费支持，作为子课题负责人或项目骨干参与科技部国家重点研发计划、工信部工业互联网创新发展工程等课题。

主讲人照片：

邀请人：王明强 数学学院教授

报告时间：12月18日上午9：00-11:00，下午：14：30-16：30