KaratSaber: New Speed Records for Saber Polynomial Multiplication using Efficient Karatsuba FPGA Architecture
- 19 January 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. PP (00189340) , 1-13
Abstract
SABER is a round 3 candidate in the NIST Post-Quantum Cryptography Standardization process. Polynomial convolution is one of the most computationally intensive operation in Saber Key Encapsulation Mechanism, that can be performed through widely explored algorithms like the schoolbook polynomial multiplication algorithm (SPMA) and Number Theoretic Transform (NTT). While SPMA multiplier has a slow latency performance, the NTT-based multiplier usually requires large hardware. In this work, we propose KaratSaber, an optimized Karatsuba polynomial multiplier architecture with a balanced hardware efficiency (throughput-per-slice, TPS) compared to NTT and SPMA based designs. KaratSaber employs several techniques for an efficient design: a parallel grid input technique for efficient pre-processing stage in Karatsuba-based polynomial multiplier, a novel instruction code result-mapping technique catering the negacyclic operations improves the post-processing stage efficiency, a double multiplicand shifter-based multiplier doubles the throughput at the multiplication stage. Combining these three techniques, the proposed KaratSaber architecture is 7.47 $\times$ faster compared to the state-of-the-art SPMA Saber architecture at the expense of 4.96 $\times$ additional hardware resources; making KaratSaber 46.04% more area-time efficient. When compared to LWRPro, a recent Karatsuba Saber architecture, KaratSaber architecture achieves a 2.11 $\times$ higher throughput by only utilizing 1.92 $\times$ additional hardware; thus gaining a 10.44% improvement in area-time efficiencyKeywords
This publication has 14 references indexed in Scilit:
- LWRpro: An Energy-Efficient Configurable Crypto-Processor for Module-LWRIEEE Transactions on Circuits and Systems I: Regular Papers, 2021
- High-Speed RLWE-Oriented Polynomial Multiplier Utilizing Karatsuba AlgorithmIEEE Transactions on Circuits and Systems II: Express Briefs, 2021
- An Efficient and Parallel R-LWE CryptoprocessorIEEE Transactions on Circuits and Systems II: Express Briefs, 2020
- An energy efficient FPGA partial reconfiguration based micro-architectural technique for IoT applicationsMicroprocessors and Microsystems, 2020
- Optimized Schoolbook Polynomial Multiplication for Compact Lattice-Based Cryptography on FPGAIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2019
- A Karatsuba Algorithm Based Accelerator for Pairing Computation2019
- Saber: Module-LWR Based Key Exchange, CPA-Secure Encryption and CCA-Secure KEM2018
- Pseudorandom Functions and Lattices2012
- A Karatsuba-Based Algorithm for Polynomial Multiplication in Chebyshev FormIEEE Transactions on Computers, 2010
- Algorithms for quantum computation: discrete logarithms and factoring2002