本文提出了一种名为 Sparse Roots of Unity (SPRU) 的新型引导（bootstrapping）算法，用于 CKKS 全同态加密方案。CKKS 是一种支持近似算术的同态加密方案，广泛应用于隐私计算和密文机器学习。在 CKKS 中，密文噪声会随着同态运算而增长，因此需要引导操作来刷新密文、控制噪声并扩展计算深度。原始的 CKKS 引导方法通过同态计算一个近似模约减的多项式来实现，该多项式逼近模 q 的约减操作，但这种方法的乘法深度较大，导致效率受限。与此不同，SPRU 引导直接利用复数单位根来嵌入模 q 的加法群结构，而单位根上的乘法可以在 CKKS 方案中近乎原生地执行，从而避免了高深度的多项式近似。这种设计显著降低了引导所需的乘法深度，进而允许使用更小的环维度，提高了整体效率。作者在 OpenFHE C++ 库中实现了 SPRU 引导，实验表明对于槽数较少的密文，与原始方法相比，引导延迟最多可降低 5 倍。这一成果对于同态加密的实际部署具有重要意义，尤其是在需要在资源受限或低延迟环境中执行深度计算的应用中。论文的核心贡献包括：提出 SPRU 引导的完整算法框架、给出理论分析、提供实现和性能基准。适合同态加密研究者、隐私计算工程师以及关注高性能密文计算的安全从业者阅读。

该论文提出了一种快速摊销自举（amortized bootstrapping）方法，用于同态加密（FHE）方案，旨在实现小密钥尺寸和多项式噪声开销。传统的FHE方案通常利用SIMD（单指令多数据）技术并行处理多个消息，但其安全性依赖于超多项式近似因子的格问题的难度，这是一种较强的假设。另一方面，一些轻量级FHE方案具有更快的自举速度，但不支持SIMD，且其安全性仅基于低阶多项式近似因子的格问题，这是一种更弱的假设。为了兼顾两者的优点，Micciancio和Sorrell（ICALP'18）提出了一种摊销自举方法，可以同时处理多个消息，使得每个消息的复杂度达到亚线性，并允许基于多项式近似因子的格问题构建FHE。本文在此基础上进一步优化，实现了更小的密钥和多项式噪声开销，从而在保持安全性的同时提升了效率。实验表明，该方法在密钥尺寸和噪声管理方面具有优势，适用于需要高效同态加密的场景。该研究对于密码学理论特别是同态加密的实际应用具有重要意义。

全同态加密（FHE）是许多实际应用中的强大原语。最近，Li和Micciancio在Eurocrypt'21上提出了IND-CPA-D安全模型，该模型通过允许攻击者访问针对诚实生成密文的解密预言机来加强标准IND-CPA安全。Jung等人（CCS'24）和Checri等人（Crypto'24）已表明，即使是精确FHE方案（如FHEW/TFHE/BGV/BFV），由于自举失败的存在，也可能不满足IND-CPA-D安全；但此类攻击可以通过设置可忽略的自举失败概率来缓解。另一方面，Liu和Wang（Asiacrypt'24）提出了松弛功能自举（Relaxed Functional Bootstrapping），该技术实现了数量级的性能提升，并允许在自举过程中进行免费函数求值。这些效率优势使其成为许多应用中的竞争性选择。然而，本文证明了攻击者能够在10分钟内恢复所有现有松弛功能自举构造的底层密钥，对于某些构造甚至不到1分钟。该攻击即使在自举失败概率可忽略的情况下仍然有效。此外，作者提出了一种通用修复方法，能够缓解IND-CPA-D模型中所有基于模切换错误的现有攻击。该修复通过构造一种基本上无开销的新模切换过程实现。最后，作者指出IND-CPA-D即使在被动攻击者模型下可能也不够充分，因此将该模型扩展为带随机性的IND-CPA-D（IND-CPA-DR）。实验表明攻击高效且修复有效，为FHE系统在更强安全模型下的实际部署提供了指导。