Exploring the Hardware Design Space for Practical Lattice-Based Post-Quantum Cryptography

Abstract

As quantum computing advances threaten to undermine classical encryption schemes, cryptography must evolve to maintain secure communication. Modern cryptographic standards will soon be replaced by recent Post-Quantum Cryptography (PQC) standards developed to mitigate the risks posed by quantum computing. However, this transition introduces increased computational overhead, creating a heightened demand for efficient hardware accelerators to achieve practical performance. Among PQC propositions, lattice-based schemes are considered leading contenders due to their robust mathematical security foundations. Nevertheless, their practical deployment is hindered by performance bottlenecks, notably the computational cost of polynomial multiplication, which drives key generation, encryption, and decryption.

This thesis addresses this challenge by investigating the optimisation of polynomial multiplication in lattice-based schemes through hardware acceleration. It reviews both time-domain (e.g., schoolbook, Karatsuba, Toom–Cook) and frequency-domain (e.g., Number Theoretic Transform (NTT)) methods, identifying modular arithmetic as the primary bottleneck.

To tackle this, the thesis presents two constant Barrett modular multiplication algorithms: the constant Barrett and a novel Truncated Modulus-Size Constant Barrett (TMSCB) variant. Complexity analysis and FPGA implementations demonstrate that the proposed TMSCB algorithm achieves up to a 2.8$\times$ reduction in area--time product compared to classical Barrett and up to a 1.4$\times$ reduction compared to constant Barrett at larger operand sizes, while reducing register usage by approximately 16.7\%. These algorithms are then integrated into scalable NTT hardware accelerators for ML-DSA and Falcon schemes. The designs exploit DSP slice efficiency, achieving execution-time reductions of up to 46.7\% and hardware area savings of up to 35.4\%, while improveing speed and resource utilisation. In addition, a parametric and scalable schoolbook-based polynomial multiplier is proposed for time-domain multiplication, exploiting coefficient splitting and truncation for power-of-two moduli and achieving execution-time reductions of 36--51\%.

Overall, this research enhances the practicality of post-quantum cryptographic hardware by optimising polynomial multiplication, enabling high-performance and deployable implementations.