Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.


New Efficient Characteristic Three Polynomial Multiplication Algorithms and Their Applications to NTRU Prime

September 21, 2022


Esra Yeniaras


In this talk, I will introduce four new polynomial multiplication algorithms in characteristic three fields and show that they are more efficient than the current state-of-the-art methods. We show that the new 4-way and 5-way split algorithms provide a 48.6% reduction in the arithmetic complexity for multiplication over F9 and a 26.8% reduction for multiplication over F3 for the input size 1280. We apply the proposed methods to NTRU Prime decapsulation, submitted to NIST PQC Standardization Process by Bernstein et al. and by implementing in C we observe a 26.85% speedup for stnrup653 and a 35.52% speedup for sntrup761 in the characteristic three polynomial multiplication step of the NTRU Prime decapsulation.

This talk is based on joint work with Murat Cenk, appearing at the Journal of Cryptographic Engineering and presented at SECITC’21.

Suggested readings:, doi:10.1007/s13389-021-00282-7,

Presented at

Crypto Reading Club talk on 2022-Sep-21

Parent Project

See: Crypto Reading Club

Related Topics

Security and Privacy: cryptography

Created September 05, 2022, Updated March 22, 2023