💻 computer science

Vectorized SQIsign Implementation Using AVX-512

本文提出了首个全面的 SQIsign 数字签名方案 AVX-512 向量化实现，在实现较参考实现显著性能加速的同时，通过英特尔即将推出的 AVX10 指令集架构展示了这些优化的长期可行性。

原作者： Weize Wang, Chutong Wang, Yu Wu, Qifan Xue, Jieyu Zheng, Yunlei Zhao

发布于 2026-08-17

📖 1 分钟阅读☕ 轻松阅读

原作者： Weize Wang, Chutong Wang, Yu Wu, Qifan Xue, Jieyu Zheng, Yunlei Zhao

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图给一位朋友发送一条秘密信息，但你知道一个来自未来的超级智能机器人可能正在偷听。为了确保安全，你需要一把连那个机器人也无法破解的锁。这就是“后量子密码学”（post-quantum cryptography）的世界，这是一个致力于构建即使面对强大的量子计算机也能生存下来的数字锁的科学领域。其中最受期待的新型数字锁之一被称为 SQIsign。它就像是一个基于形状扭转和旋转（在数学上称为椭圆曲线）的神奇谜题，这种方式极其紧凑，但也极其难以破解。问题在于，虽然这个谜题小到可以装进你的口袋，但解开它却需要很长时间，就像是用一把小剪刀去解开一个巨大的毛线球。

为了让这些数字锁在日常使用中变得实用，我们需要更快地解开这个谜题。这正是这篇论文发挥作用的地方。研究人员实际上是在问：“我们如何让剪刀切断毛线的速度更快？”他们发现了一种可以使用现代计算机芯片中名为 AVX-512 的特殊工具集的方法。你可以把普通的计算机处理器想象成一位一次只能切一根蔬菜的厨师，而 AVX-512 工具则像是一把神奇的菜刀，只需挥动一次，就能同时切开八根蔬菜。这篇论文展示了如何重新组织整个 SQIsign 谜题，以便让这种“一次处理八个”的工具几乎可以用于过程中的每一个步骤，将一个缓慢、乏味的工作变成一个闪电般快速的任务。

“一次处理八个”神奇菜刀的力量

这篇论文的核心是对 SQIsign 数字签名方案的大幅加速。作者们（来自复旦大学的一个团队）构建了第一个能够充分利用 AVX-512 指令集的 SQIsign 版本，特别是利用了一个被称为 IFMA（整数融合乘加）的强大特性。

为了理解这为什么重要，想象你是一名正在制作成千上万块饼干的面包师。旧的方法（“参考实现”）是揉面、擀皮、切割、烘焙，一次只做一个饼干。即使你动作很快，过程也很慢。SQIsign 算法就像一个非常复杂的食谱，需要大量的搅拌和擀制。研究人员意识到，与其一次做一个饼干，不如重新组织他们的厨房，利用单一动作同时制作八个饼干。

他们通过重新设计算法的“数学厨房”实现了这一点。他们提取了基本构建模块——比如加法和乘法巨大的数字（这些是密码学谜题的原料）——并对其进行了重写，使其完美契合到 AVX-512 的“一次处理八个”的通道中。他们不仅停留在基础数学层面，还将这种加速应用到了整个操作链中，包括：

椭圆曲线运算： 形状的扭转与旋转。
配对计算： 一种用于验证形状是否匹配的特殊数学方法。
同源评估： 将一个形状转化为另一个形状的实际过程。

结果：加速谜题

当他们将这种新的“一次处理八个”厨房投入测试时，结果令人印象深刻。他们在 NIST 安全等级 I（这是保护数据的基准安全等级）下测量了速度相对于标准版 SQIsign 的表现。

签名（Signing）： 在创建数字签名（锁定信息）时，他们的新方法快了 2.69 倍。
验证（Verification）： 在检查签名是否有效（解锁信息）时，它快了 3.18 倍。

他们还将他们的工作与另一种被称为 Qlapoti 的技术（这就像是另一种组织食材的方式）相结合，以获得这些结果。论文指出，验证过程获得的提升比签名过程更大，因为签名过程仍然需要处理涉及另一种数学类型（四元数代数）的繁重工作，而他们尚未对该部分进行向量化。然而，完全依赖于他们所优化的数学部分的验证环节，看到了最大的加速效果。

拆穿“过时”的迷思

论文中一个有趣的注脚是对一个常见误解的纠正。有些人认为 AVX-512 技术正在走向过时，或者仅适用于特定的、昂贵的服务器计算机。作者们对此提出了强烈的反驳。他们指出，英特尔已经宣布了一项名为 AVX10（特别是 10.2 版本）的新标准，该标准预计将在 2026 年底广泛部署。这一新标准将把这些强大的“一次处理八个”的能力带到未来处理器的性能核和效率核中。这意味着他们开发的加速技术不仅仅是针对今天超级计算机的临时补救措施，而是一个长期的解决方案，将在未来的计算机上持续有效，确保这些加密锁既快速又实用。

为什么这很重要

这篇论文不仅仅展示了一种更快的数学计算方法；它还为如何让基于同源的密码学（一种非常有前景的后量子安全类型）在现实世界中真正可用提供了蓝图。通过展示 SIMD 向量化（即“一次处理八个”的方法）是加速过程的关键且此前被低估的方式，他们为其他研究人员将类似的技巧应用于不同密码学谜题打开了大门。

作者们谨慎地指出，他们的工作独立于其他近期的算法改进。这意味着，如果有人发明了更好的“饼干面团食谱”（一种新算法），他们发明的“一次处理八个”的菜刀仍然可以用来更快地切割饼干。这是一种乘法效应的胜利：你可以在获得更好算法的同时，也享受到他们更高效硬件利用带来的好处。

简而言之，这篇论文通过打磨，让一个很有前景但运行缓慢的数字锁变得光彩夺目，证明了只要拥有正确的工具和一点创造性的重新组织，我们可以让未来的数字世界既安全又高效。

技术摘要：基于 AVX-512 的向量化 SQIsign 实现

问题陈述

SQIsign 是提交给 NIST 后量子密码标准化进程中唯一的基于同源（isogeny-based）的数字签名方案。虽然它基于超奇异椭圆曲线的端同态环问题，提供了紧凑的密钥和签名尺寸，但其目前的实际部署受到计算密集型签名过程的阻碍。性能瓶颈主要存在于“曲线侧”（curve-side）计算中，这包括在大型素数域 ( $\mathbb{F}_p$ ) 及其二次扩展域 ( $\mathbb{F}_{p^2}$ ) 上的广泛算术运算、椭圆曲线操作（点倍倍/点倍减及标量乘法），以及在主极化阿贝尔曲面（PPAS）上更高维度的同源求值。现有的参考实现过度依赖标量算术，通常利用 GNU 多精度算术库（GMP）处理四元数代数组件，这限制了吞吐量。

方法论

本文介绍了首个针对 SQIsign “曲线侧”组件进行全面向量化的实现，该实现利用了 AVX-512 整数融合乘加（IFMA）指令集架构。作者系统地重新设计了计算栈，以利用所有主要算法层中的 SIMD（单指令多数据）并行性，同时明确指出四元数代数组件（IdealToIsogeny）在本文中仍保持为标量且未进行优化。

核心技术策略

有限域算术 ( $\mathbb{F}_p$ 和 $\mathbb{F}_{p^2}$ ):
- 表示法： 实现采用了基数为 $2^{51}$ 的表示法来处理域元素，将其分解为五个 51 位肢（limbs）。选择该尺寸是为了使其能够适配 64 位通道中的低 52 位，从而在执行 IFMA 操作时防止溢出，并为延迟归约（deferred reduction）预留空间。
- 并行化： 在 $\mathbb{F}_p$ 层采用了 $(8 \times 1)$ -路并行化策略，在单个 512 位 ZMM 寄存器中同时处理八个独立的域元素。
- 扩展： 对于 $\mathbb{F}_{p^2}$ ，作者实现了三种不同的并行化模式—— $(8 \times 1 \times 1)$ 、 $(4 \times 2 \times 1)$ 和 $(2 \times 4 \times 1)$ ——以根据特定的算法需求（例如批处理操作 vs. 内部组件并行性）平衡吞吐量和寄存器压力。
- 指令： 设计利用了 vpmadd52luq 和 vpmadd52huq 指令，以执行八路并行的 $52 \times 52$ 位乘法，并具备融合乘加能力，显著减少了用于蒙哥马利乘法（Montgomery multiplication）和进位传播的指令计数。
椭圆曲线操作：
- 点倍倍（Point Doubling）： 作者针对 $x$ -仅坐标（蒙哥马利曲线）和全射影坐标（Jacobian 和 Modified Jacobian）优化了点倍倍操作。对于 $x$ -仅坐标，他们在向量化上下文中始终省略归一化步骤以维持数据流，而仅在同时对多个点进行倍倍操作时才应用归一化，以最大化并行性。
- 标量乘法： 该实现向量化了蒙哥马利阶梯（Montgomery ladder）、三点阶梯（three-point ladder）以及二维阶梯（LadderBiscalar）。一项关键贡献是重新设计的四路向量化策略，用于 xDBLADD 函数，该策略能够适配用于同源密码学中的通用 $(A_{24}:C_{24})$ 参数格式，避免了以往向量化尝试中的特殊形式依赖。
- 配对（Pairings）： 本文解决了用于基生成（basis generation）的 Tate-Lichtenbaum 配对计算问题。通过将一次点倍倍与两次微分加法（differential additions）融合，作者创建了一个 cubicalDBLADDADD 算法，通过三个四路并行乘法和一个四路并行平方运算来生成所需的配对。
同源求值：
- 维度 1 & 2： 作者应用了批处理策略进行同源求值。他们不再顺序处理点，而是将多个点的坐标交织在 AVX-512 通道中，以饱和 SIMD 乘法器。这种方法被应用于椭圆曲线上的 4-同源以及阿贝尔曲面（PPAS）上的 $(2,2)$ -同源，并使用了 $\theta$ -坐标算术。
架构上下文：
- 本文解决了关于 AVX-512 过时的误解，指出英特尔即将推出的 AVX10 架构（修订版 10.2，计划于 2026 年底发布）将使这些能力在性能核和效率核中实现标准化，从而确保长期可行性。

主要贡献

SQIsign 曲线侧操作的全面向量化： 本工作提供了首个使用 AVX-512IFMA 对 SQIsign “曲线侧”组件进行完整向量化的实现，涵盖了素数域算术、二次扩展、椭圆曲线操作（包括标量乘法和配对）以及一维和二维中的同源求值。四元数代数组件仍保持为标量。
x86-64 上的扩展向量化分析： 与以往基于 ARM 的向量化工作（如 De Feo 等人使用 NEON）不同，本研究在 x86-64 平台上探索了更广泛的功能范围，包括复杂的标量乘法策略和 $\theta$ -坐标操作。其算法设计被认为是架构无关的，为迁移到其他 SIMD 平台（如 ARM SVE 或 RISC-V）提供了基础。
可推广的优化： 开发的用于点倍倍、批处理标量乘法和向量化 $\theta$ -点算术的技术，被视为适用于其他利用高维阿贝尔簇的同源密码系统的通用方法论基础。

实验结果

该实现在运行 Ubuntu 24.04 的 Intel Core i7-11700F CPU (2.50GHz) 上进行了基准测试。结果与官方参考实现（针对使用 64 位肢的 Broadwell 优化）进行了对比。

性能提升：
- 密钥生成： 加速比在 $1.03\times$ 至 $1.28\times$ 之间。
- 签名： 加速比在 $1.08\times$ 至 $1.26\times$ 之间。
- 验证： 加速比在 $1.46\times$ 至 $1.84\times$ 之间。
结合 Qlapoti： 当与 Qlapoti 技术结合使用时，该实现在 NIST 安全等级 I 下实现了 $2.69\times$ 的签名加速 和 $3.18\times$ 的验证提升。
验证差异： 文中指出，验证过程的获益比签名过程更为显著，因为验证完全依赖于向量化的曲线侧操作，而签名仍涉及目前通过标量 GMP 执行的四元数代数操作（该组件并非本文优化的目标）。

重要性与声明

作者声称，这项工作证明了 SIMD 向量化是后量子同源密码方案中一个关键但尚未得到充分探索的优化维度。

与算法进步的独立性： 这些优化与近期的算法级改进（如 Qlapoti 或 Superglue）是正交的。这意味着通过向量化获得的性能增益是乘性的；未来的协议级创新可以在此向量化基础上叠加，从而产生复合的性能提升。
长期可行性： 通过强调 AVX-512 能力在未来英特尔架构（AVX10）中的标准化，本文认为这些优化技术并非临时解决方案，而是高效同源密码学的可持续路径。
普适性： 作者声称该方法论适用于各种同源构造（如 SQIsignHD、SQIsign2D-East、SQIPrime），因为它们都依赖于相同的底层原语（ $\mathbb{F}_{p^2}$ 算术、 $\theta$ 坐标和椭圆曲线操作），而这些正是优化的目标。

本文得出结论，虽然 SQIsign 的“四元数侧”仍然是标量瓶颈，但“曲线侧”的向量化显著缩小了理论紧凑性与实际部署效率之间的差距。