基于AVX-512的BLS12-381最优Ate配对高速实现
摘要
椭圆曲线上的非退化双线性映射（通常称为配对）在短签名方案、零知识证明和远程认证协议等领域有广泛应用。在128位安全级别下，计算最先进的配对（如BLS12-381曲线上的最优Ate配对）成本极高，主要因其子操作（尤其是Miller循环和最终指数化）的高度复杂性。过去十年间，文献中出现了若干优化配对实现，但均未利用现代Intel和AMD CPU的向量（SIMD）扩展指令集（特别是AVX-512），这令人惊讶，因为此类指令集有望带来显著加速。因此，如何有效向量化最优Ate配对计算以及向量化实现的执行时间能达到何种水平，仍是待解决的问题。
本文通过引入精心优化的BLS12-381最优Ate配对AVX-512实现来解答上述问题。该实现的核心特点是使用8路整数融合乘加（IFMA）指令，能够以SIMD并行方式执行8个52×52位乘法。我们提出了新的向量化策略，并优化现有策略以加速扩展域Fp4、Fp6和Fp12中的算术运算及某些高层函数。此外，我们讨论了部分并行化瓶颈及其对执行时间的影响。
我们在Intel Core i3-1005G1（“Ice Lake”）CPU上对名为avxbls的配对软件进行基准测试，发现完整配对需要1,265,314个时钟周期（使用Granger-Scott分圆平方时）或1,195,236个时钟周期（使用压缩分圆平方时）。作为对比，广泛使用的blst库中的非向量化（即标量）x64汇编实现需要2,351,615个周期，速度慢1.86倍（或1.97倍）。avxbls同样以近似的倍数优于Longa的实现（CHES 2023）。这些结果的实际重要性因Intel最近宣布在所有未来CPU中支持包含IFMA指令的AVX10而进一步增强。
关键词
配对密码学、最优Ate配对、SIMD、AVX-512
作者单位
- 程浩：山东大学网络空间安全学院（青岛）、密码科学与数字经济安全全国重点实验室（青岛）、密码技术与信息安全教育部重点实验室（青岛）
- Georgios Fotiadis：=nil;基金会（塞浦路斯利马索尔）、卢森堡大学DCS和SnT（埃施苏尔阿尔泽特）
- Johann Großschädl：卢森堡大学DCS和SnT（埃施苏尔阿尔泽特）
- Daniel Page：布里斯托大学计算机科学学院（英国布里斯托）
技术指标
- 测试平台：Intel Core i3-1005G1（“Ice Lake”）CPU
- 完整配对周期数：1,265,314（标准分圆平方）/1,195,236（压缩分圆平方）
- 加速比：较blst库提升1.86-1.97倍
创新点
- 首次实现基于AVX-512的BLS12-381配对计算向量化
- 利用IFMA指令实现8路并行52位乘法
- 提出扩展域运算的新型向量化策略
- 系统分析并行化瓶颈对性能的影响