KaratSaber: new speed records for Saber polynomial multiplication using efficient Karatsuba FPGA architecture

Zheng Yan Wong, Denis C.K. Wong, Wai Kong Lee, Kai Ming Mok, Wun She Yap, Ayesha Khalid

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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 × faster compared to the state-of-the-art SPMA Saber architecture at the expense of 4.96 × 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 × higher throughput by only utilizing 1.92 × additional hardware; thus gaining a 10.44% improvement in area-time efficiency.

Original languageEnglish
Pages (from-to)1830-1842
Number of pages13
JournalIEEE Transactions on Computers
Volume72
Early online date19 Jan 2023
DOIs
Publication statusPublished - Jul 2023

Keywords

  • Computer architecture
  • Convolution
  • Cryptography
  • FPGA
  • Hardware
  • Karatsuba
  • lattice-based cryptography
  • NIST
  • post-quantum cryptography
  • public key cryptography
  • Saber
  • Throughput
  • Transforms

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'KaratSaber: new speed records for Saber polynomial multiplication using efficient Karatsuba FPGA architecture'. Together they form a unique fingerprint.

Cite this