International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Verified NTT Multiplications for NISTPQC KEM Lattice Finalists: Kyber, SABER, and NTRU

Authors:
Vincent Hwang , Academia Sinica, Taipei, Taiwan; National Taiwan University, Taipei, Taiwan
Jiaxiang Liu , Shenzhen University, Shenzhen, China
Gregor Seiler , IBM Research Zurich, Zurich, Switzerland
Xiaomu Shi , Shenzhen University, Shenzhen, China
Ming-Hsien Tsai , National Applied Research Labs, Taipei, Taiwan
Bow-Yaw Wang , Academia Sinica, Taipei, Taiwan
Bo-Yin Yang , Academia Sinica, Taipei, Taiwan
Download:
DOI: 10.46586/tches.v2022.i4.718-750
URL: https://tches.iacr.org/index.php/TCHES/article/view/9838
Search ePrint
Search Google
Presentation: Slides
Abstract: Postquantum cryptography requires a different set of arithmetic routines from traditional public-key cryptography such as elliptic curves. In particular, in each of the lattice-based NISTPQC Key Establishment finalists, every state-ofthe-art optimized implementation for lattice-based schemes still in the NISTPQC round 3 currently uses a different complex multiplication based on the Number Theoretic Transform. We verify the NTT-based multiplications used in NTRU, Kyber, and SABER for both the AVX2 implementation for Intel CPUs and for the pqm4 implementation for the ARM Cortex M4 using the tool CryptoLine. e extended CryptoLine and as a result are able to verify that in six instances multiplications are correct including range properties.We demonstrate the feasibility for a programmer to verify his or her high-speed assembly code for PQC, as well as to verify someone else’s high-speed PQC software in assembly code, with some cooperation from the programmer.
BibTeX
@article{tches-2022-32383,
  title={Verified NTT Multiplications for NISTPQC KEM Lattice Finalists: Kyber, SABER, and NTRU},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 4},
  pages={718-750},
  url={https://tches.iacr.org/index.php/TCHES/article/view/9838},
  doi={10.46586/tches.v2022.i4.718-750},
  author={Vincent Hwang and Jiaxiang Liu and Gregor Seiler and Xiaomu Shi and Ming-Hsien Tsai and Bow-Yaw Wang and Bo-Yin Yang},
  year=2022
}