An Extensive Study of Flexible Design Methods for the Number Theoretic Transform
An Extensive Study of Flexible Design Methods for the Number Theoretic Transform
复制标题
DOI：
10.1109/tc.2020.3017930
复制
发表时间：
2020-08
影响因子：
3.7
通讯作者：
A. Mert;Emre Karabulut;Erdinç Öztürk;E. Savaş;Aydin Aysu
中科院分区：
文献类型：
--
作者：
A. Mert;Emre Karabulut;Erdinç Öztürk;E. Savaş;Aydin Aysu
高效的格基密码系统使用多项式环和数论变换(NTT)来降低多项式乘法的计算复杂度。因此，NTT已成为各种密码构造中的主要算术组件(从而成为计算瓶颈)，如散列函数、密钥封装机制、数字签名和同态加密。尽管在以前的工作中存在几种针对NTT的硬件设计，但它们都是为特定的NTT参数或并行化水平固定的孤立设计实例。本文对NTT实现的柔性设计方法进行了广泛的研究。为此，我们评估了三种情况：(1)参数硬件设计，(2)高级综合(HLS)设计方法，以及(3)针对可重构硬件设备的软核处理器上编译的软件实现设计。我们评估实现多个NTT参数和/或处理元素的设计，展示每个案例的设计细节，并提供彼此和先前工作的公平比较。在Xilinx Virtex-7现场可编程门阵列上，与HLS和基于处理器的设计方法相比，该方法的平均硬件设计成本分别为4.4倍、4.4倍和73.9倍、22.5倍、22.5倍和19.3倍。令人惊讶的是，在某些情况下，HLS工具产生的解决方案不如基于处理器的方法有效。
Efficient lattice-based cryptosystems operate with polynomial rings with the Number Theoretic Transform (NTT) to reduce the computational complexity of polynomial multiplication. NTT has therefore become a major arithmetic component (thus computational bottleneck) in various cryptographic constructions like hash functions, key-encapsulation mechanisms, digital signatures, and homomorphic encryption. Although there exist several hardware designs in prior work for NTT, they all are isolated design instances fixed for specific NTT parameters or parallelization level. This article provides an extensive study of flexible design methods for NTT implementation. To that end, we evaluate three cases: (1) parametric hardware design, (2) high-level synthesis (HLS) design approach, and (3) design for software implementation compiled on soft-core processors, where all are targeted on reconfigurable hardware devices. We evaluate the designs that implement multiple NTT parameters and/or processing elements, demonstrate the design details for each case, and provide a fair comparison with each other and prior work. On a Xilinx Virtex-7 FPGA, compared to HLS and processor-based methods, the results show that the parametric hardware design is on average $4.4\times$4.4× and $73.9\times$73.9× smaller and $22.5\times$22.5× and $19.3\times$19.3× faster, respectively. Surprisingly, HLS tools can yield less efficient solutions than processor-based approaches in some cases.