High-Speed RLWE-Oriented Polynomial Multiplier Utilizing Karatsuba Algorithm

Zheng-Yan Wong

doi:10.1109/TCSII.2020.3049002

2021-06-01

PRE

Zheng-Yan Wong

Denis Chee-Keong Wong *

Wai‐Kong Lee

Kai‐Ming Mok

DOI：10.1109/TCSII.2020.3049002

原文链接

原文求助

摘要

En 中文

Lattice-based cryptography (LBC) is one of the promising post-quantum candidates which offers good security and performance. The most time consuming operations in LBC is the polynomial multiplication, which can be performed through widely explored algorithms like schoolbook polynomial multiplication algorithm (SPMA) and Number Theoretic Transform (NTT). However, Karatsuba algorithm with better complexity compared to SPMA, is not widely studied for FPGA implementation of LBC. In this brief, we proposed an optimized SPMA-Karatsuba (SK) architecture with novel technique to implement the negacyclic convolution. The proposed architecture is more than 2.09 x faster in expense of 96.06% additional hardware resources compared to the state-of-the-art SPMA architecture. This shows that the combination of SPMA and Karatsuba algorithm can produce hardware architecture with higher speed yet maintain balanced area-time efficiency compared to SPMA-only architecture. This is especially useful for developing IoT edge nodes or gateway devices that require high speed but able to tolerate some additional hardware area.

Keyword:

SPMA

FPGA

public key cryptography

lattice-based cryptosystem

post-quantum cryptography