Finding inverses of polynomials are required to generate key pair in NTRU ( \(N^{th}\) degree Truncated polynomial Ring Units) accelerators for encryption and decryption, hashing and verification, key encapsulation and decapsulation. NTRU schemes which are towards Post Quantum Cryptography (PQC), typically need inverses of polynomials in quotient rings \(\mathbb {S}_*\) = \(\mathbb {Z}\) [x]/(*, \(\Phi _N\) ) \(\mathbb {R}_*\) = \(\mathbb {Z}\) [x]/(*, \(\Phi _1\) \(, \Phi _N\) ) with either binary {0, 1} or ternary {-1, 0, 1}/{0, 1, 2} or {-q/2, -q/2+1 ...q/2+1} coefficients where, q could be 2048, 4096, 8192 or some prime etc., \(\Phi _N\) is \((X^N-1)\) or \((X^N-X-1)\) and \(\Phi _1\) is \((X-1)\) . More specifically for the NTRU-HRSS, N=701, \(\Phi _N\) = \((X^N-1)\) , ternary p=3, q=8192 based coefficients for polynomials in \(\mathbb {S}\) and \(\mathbb {R}\) . Generally, inverses are computed in software, and hardware-based inversion units accelerate the key generation process and reduce latency during frequent key generation needs. This work presents the design and analysis of an efficient unified hardware unit for computing polynomial inverses in constant time for NTRU schemes in general and more focusing towards NTRU-HRSS701. The unit supports the finding of inverses in \(\mathbb {S}_2\) , \(\mathbb {S}_3\) , \(\mathbb {R}_2\) , \(\mathbb {R}_3\) , \(\mathbb {S}_q\) and \(\mathbb {R}_q\) . Different design approaches viz., with and without Counting Trailing Zeros (CTZ), single Montgomery modular multiplier (MMM) reuse, etc., to optimize either latency or area have been adopted and evaluated. The designed inversion unit has been integrated with an NTRU-HRSS701 hardware accelerator which specifically needs inverses in \(\mathbb {S}_3\) and \(\mathbb {R}_q\) which in-turn needs in \(\mathbb {R}_2\) , validated and tested using NIST test vectors for NTRU-HRSS701. Further, the computational complexity of the proposed hardware inversion unit has been investigated experimentally and found to be within the indicated theoretical estimates for the adopted Constant Time Almost Inverse Algorithm (CT-AIA) and AIA. We analyze the proposed architectures through simulation and synthesizing for the FPGA platform and present the results.
