This thesis studies the implementation aspects of polynomial multiplication in lattice-based cryptosystems, including Dilithium, Kyber, Saber, NTRU, and NTRU Prime. As hardware gradually evolves and numerous platforms are in use today, systematic surveys and studies with numerical justification of the merits and drawbacks of implementation techniques require significant effort. This thesis systematically covers the relevant mathematical background, various optimization techniques, and implementation aspects of polynomial multiplication, and relates them to optimized implementations across various platforms. Part I covers the mathematical background, including the basics of algebra, modular arithmetic, fast homomorphisms, embedding techniques, optimizations in the choice of polynomial moduli, and vectorization. Part II provides a general guide to optimizations for modular multiplications, quotients, and fast transformations. Part III presents several case studies and relates the mathematical techniques to platform-specific, optimized implementations of lattice-based cryptosystems.
Vincent Hwang is a fourth-year PhD student at the Max Planck Institute for Security and Privacy, Bochum, Germany, under the supervision of Peter Schwabe. He obtained a bachelor's degree (2021) and a master's degree (2022) from the Department of Computer Science and Information Engineering at National Taiwan University, Taipei, Taiwan. His main research focuses are assembly optimization in cryptographic engineering across various platforms, formal verification of assembly-optimized programs, and, recently, elliptic-curve discrete logarithms on data-center-level GPUs. He coauthored/authored eleven papers on assembly optimization of polynomial multiplications, a survey paper on the same topic, and three papers on formal verification. He is enthusiastic about turning high-level constructs in cryptography into highly optimized assembly programs.