Saber算法的多项式乘法FPGA实现研究

Research on FPGA Implementation of Polynomial Multiplication for Saber Algorithm

在NIST后量子密码标准征集过程中,Saber算法凭借带宽低、灵活性高等特点,成为了较有竞争力的第三轮候选算法。作为Saber算法的核心部件,多项式乘法的硬件高效实现,能对Saber算法的实现起到加速作用。本文针对Saber算法,介绍分析了三种多项式乘法算法的原理,结合Karatsuba算法及经典schoolbook算法,提出了五种基于Toom-Cook算法的多项式乘法算法改进方案,利用简单的加减法运算代替复杂的乘法运算,核心部分采用循环迭代结构进行优化设计。最后在国产FPGA器件Titan系列PGT180H-7FFBG676上进行综合,给出了五种改进方案实现Saber算法256×256多项式乘法的性能分析。研究发现,1轮Toom-Cook-4 way算法结合5轮Karatsuba算法及schoolbook算法2×2全乘的融合算法,使用的硬件逻辑资源相对较少,提高了乘法运算的速度。

In the standard collection process of NIST post-quantum cryptography algorithm,Saber algorithm has become a promising third-round candidate algorithm due to the characteristics of low bandwidth and high flexibility.As the core component of the Saber algorithm,hardware implementing the polynomial multiplication with high-efficiency could accelerate the implementation of the Saber algorithm.In this paper,principles of three polynomial multiplication algorithms for the Saber algorithm are introduced and analyzed.Combined with the Karatsuba algorithm and the classical schoolbook algorithm,five improved schemes of polynomial multiplication algorithm based on the Toom-Cook algorithm are proposed,where simple addition and subtraction operations are used to replace the complex multiplication operations and the cyclic iterative structure is adopted in the core part for optimization design.Finally,based on the domestic FPGA device Titan series PGT180 H-7 FFBG676,performance analysis of implementing 256×256 polynomial multiplication in the Saber algorithm using the five improved schemes respectively is performed.Analysis results show that the fusion algorithm of 1-round Toom-Cook-4 way algorithm combined with 5-round Karatsuba algorithm and 2×2 schoolbook algorithm requires fewer hardware logic resources and improves the speed of multiplication.