本文研究分圆环上的格问题计算复杂性。具体而言，作者证明了在二维全秩自由子模上，以 ℓ2-范数定义的判定型最短向量问题（SVP）是 NP-完全的。设 q 为模 4 余 3 的素数，ζ_q 为本原 q 次单位根，K=Q(ζ_q)，环 O_K=Z[ζ_q]。固定模秩为 2，但作为 Z-格，秩为 2(q-1)，随 q 增长。主要障碍是 O_K 作用下的封闭性：模块中任一非零向量蕴含其所有 O_K 标量倍，其中一些可能更短，从而干扰判定。作者提出三个关键思路克服该障碍：1) 将 Bennett-Peikert Reed-Solomon 格映射到主分圆理想，并利用 Wan 的点计数估计证明该理想的陪集含大量二进制系数表示；2) 基于二次高斯和的“检查器”将 X3C（精确覆盖三集）方程转化为规范化平方范数；3) 检查器与第二模坐标结合，利用理想陪集分离界限排除 O_K 作用产生的所有非预期向量。每个构造实例包含素数 q≡3 mod 4、两个非零行列式的积分生成元、以及一个整数平方阈值。该构造还通过多项式时间 Turing 归约给出 search-SVP 的 NP-难性。该工作属于密码学与计算复杂性理论交叉领域，对基于格的密码学（尤其 cyclotomic 结构）安全性分析有理论意义。适合对格基密码、计算复杂性理论、代数数论感兴趣的科研人员阅读。

该论文提出了一种自主密码分析工作流，利用智能代理自动生成、测试并优化假设，最终由人类研究人员进行审查。自主阶段返回可复现的候选结果，包括精确的验证证据（witnesses）、对照实验（controls）、代码和运行记录。研究人员据此判断证据是否足以确认一个构造的破坏、缺陷或覆盖空白。论文总结了两种反复出现的失败模式：一是公共代数映射或输入表示无意中暴露了构造必须隐藏的关系，例如乘以零、多项式乘积的边界系数、商、特征标、Schur 平方以及无边界可变长度字节编码；二是模拟器、误差定律或参数认证使用了与声明不同的分布。多个目标同时存在这两种问题。每个失败结果都有精确的证据和区分性对照，每个声明的边界都有证明。另有三个目标未被攻破，但实际可保证的安全强度低于通用解读。总体而言，八个已发布的构造在声明参数或声明条件下被攻破，包括：一个 Ring-LWR 承诺方案以概率 1 对所有消息开放；一个密文泄露了两行 middle-product 加密；一个格基电子投票协议失去了收据不可伪造性；一个可更新加密的置换恢复攻击通过线性代数扩展至旧解密密钥；一个显式正规基将 degree-63 实例分解为七个 degree-9 实例；一个非格设置下的签名哈希将两个可打印等长消息映射到同一摘要；一个可重随机化方案的接受比特成为其解密噪声的阈值预言机。此外，一个群环决策声明和一个多元 MinRank 加固方案在假设或核算层面失败，而非完全构造性破坏。每个失败都发生在支撑其假设的上一层。该研究为密码学构造的自动化验证提供了新范式，并揭示了多个实际系统中潜在的安全弱点。适合密码学研究者、安全审计人员以及依赖格基密码、投票协议、可更新加密等方案的工程团队阅读。

量子复制保护是一种利用量子力学的不可克隆原理，将函数的功能编码在量子态中，使得任何恶意方都无法将该量子态拆分成两个仍能同时正常运行的量子态的技术。此前标准模型下的多项研究只支持独立采样的挑战，而对于更接近实际语义的“相同挑战”或“相关挑战”情形一直缺乏可行方案，这也阻碍了点函数等基础对象的复制保护设计。本文作者首先对复制保护的安全性定义进行了强化，并提出了一组新的、更强的安全概念。对于单解密器加密（SDE），他们定义了“相关挑战安全性”，证明了它蕴含所有先前的SDE安全概念（包括相同挑战安全性），并说明 Kitagawa 与 Yamakawa（TCC 2025）的著名构造在仅有不可区分混淆（iO）和单向函数存在的假设下，即可满足该新安全性。然后，他们将视角扩展到一般功能，提出了“相关挑战不可克隆穿刺混淆”（UPO）模型，允许挑战点与穿刺位之间任意相关，同时允许分割前后附加辅助信息，并且只需每个挑战点各自具备条件均匀性及λ^c次平均条件最小熵，因此可处理完全相同的挑战。在假设后量子iO与量子困难LWE的前提下，作者为输入长度不小于λ^c的多项式规模带密钥电路构造了相关UPO，直接解决了Ananth等人及Çakan-Goyal等提出的开放问题。最终，他们获得了标准模型下点函数、k点函数、计算-比较程序的首个复制保护，以及一般可穿刺功能的相同挑战复制保护。该工作为量子复制保护的理论基础补齐了关键拼图，并将推动量子安全软件保护的发展。

本文针对同态加密（HE）方案中模数消耗问题展开研究。BGV、BFV 和 CKKS 等主流同态加密方案在进行每次乘法运算时，都会消耗一定量的密文模数，这限制了可执行的同态计算深度。自举（Bootstrapping）虽然可以恢复模数并使计算继续，但自举过程耗时且需要额外的大量模数预算。因此，如何降低乘法运算的模数消耗，成为提升 BGV、BFV 和 CKKS 方案实用性的关键研究方向，已有众多相关工作。本文由该领域知名学者（包括 Cheon 等）联合撰写，提出了一种用于 CKKS 方案的同态多精度乘法（Homomorphic Multiple Precision Multiplication）方法，其核心目标是减少模数消耗。通过将乘法分解为多个精度较低的部分并分别进行同态运算，可以在不牺牲最终结果精度的前提下，有效控制模数预算的使用。该方法有望降低自举的频率或规模，从而减少整体计算开销。文章作为学术研究，重点在于理论方案的设计与分析，并未提供具体的实验性能数据或实际部署细节。适合关注同态加密算法优化、隐私计算底层协议改进的研究人员和高级开发人员阅读。

本文提出一种求解最短向量问题（SVP）的随机化算法。SVP 是格密码学中的核心困难问题，其求解复杂度直接关系到基于格的密码方案（如 NTRU、LWE）的安全性评估。此前由 Aggarwal、Dadush、Regev 和 Stephens-Davidowitz 在 STOC'15 上给出的最佳算法需要 2^{n+o(n)} 的时间和空间。本文通过利用周期高斯函数在半最短向量处的 Hessian 矩阵特性，显著改进了复杂度：经典环境下时间复杂度为 2^{0.6039n+o(n)}，量子环境下为 2^{0.5411n+o(n)}，空间复杂度为 2^{0.5n+o(n)}。核心思想是：对于最短向量 v，在 v/2 处的 Hessian 矩阵存在一个与 v 方向接近的特征向量，借助预处理的有界距离解码（BDD）算法可以恢复 v。由于函数关于格 L 具有周期性，候选中点可由商格 L/2L 中的奇偶类索引。算法通过离散高斯采样估计对应 Hessian，从而搜索最短向量的奇偶类。作者还引入了随机子格陪集和多种采样技术来优化复杂度，这些优化方法本身可能具有独立价值。该论文属于理论算法研究，对格密码分析具有潜在影响，但当前仅基于摘要，尚未验证实验实现或实际攻击场景。

本文研究学习带误差问题（LWE）中秘密向量的恢复问题，特别关注秘密具有低汉明重量的情况。LWE是后量子密码学的基础假设，其安全性依赖于给定样本恢复秘密的困难性。传统方法通常假设秘密均匀分布，但在许多实际场景（如FrodoKEM、Kyber等方案）中，秘密往往具有稀疏性。作者提出了一种从"完美提示"到"近似提示"的转变：即攻击者可以获得关于秘密的部分信息（如某些位的值或软信息），这些信息可能来自侧信道攻击或协议特性。核心贡献是设计了一种高效的秘密恢复算法，利用低汉明重量和近似提示，将问题转化为求解近似最短向量问题（apprSVP）或使用格基约简技术。实验表明，当秘密汉明重量较低且提示质量较高时，算法能在多项式时间内恢复秘密，比传统格攻击更有效。该工作对LWE参数选择具有指导意义，提示需要避免低重量秘密或限制信息泄露。