[NTRU+] NTRU+ update (version 2.2)

[김종현]

Dear all,

We would like to upload a revised version (denoted as version 2.2) of the NTRU+, including the revised specification and updated implementations.

Specification: [link]

Implementations: [link]

You can also download the above files in the Github:

https://github.com/ntruplus/ntruplus/tree/KpqC-Round2-(version-2.2)

The primary changes to the specification are as follows: 

1. Definition of Hash Function

Following comments by Dr. Seongkwang Kim indicating that AES256CTR is not suitable for in stantiating the random oracle model (https://groups.google.com/g/kpqc-bulletin/c/C-mtPvzo3QA/m/vuQ0sis6AgAJ), we revised how we instantiate the hash functions G, H_KEM, and H_PKE in the specification by replacing AES256CTR with SHAKE256. 

2. Changes in the Key Generation

To enhance efficiency, we separated the sampling of the invertible polynomials f and g: first, we sample f until it is invertible, then we sample g until it is invertible. This sequential sampling minimizes unnecessary rejections. 

3. Changes in the NTT Structures

 To improve the efficiency of key generation, we modified the NTT structures for ${\KEM, \PKE}{576, 768, 1152}$ to factor the ring as $\prod_{i=0}^{n/4-1} \mathbb{Z}_q[x] / \langle x^4 - \zeta_i \rangle$.  

4. Spreadness of PKE′ = ACWC2[PKE, SOTP, G]

We re-analyzed the spreadness of the PKE′ = ACWC2[PKE, SOTP, G] in Section 3.2.

5. Parameter Adjustment in NTRU+PKE

To conservatively set the parameters, we modified the maximum message length supported by NTRU+PKE to 32 bytes for all parameter sets NTRU+PKE{576, 768, 864, 1152}.

6. Revisions to the Definition of PKE

In response to comments by Prof. Sven Schäge through private email communication, we updated the definitions related with PKE.

7. Revision to Lemma  

In response to comments by Prof. Joohee Lee presented at the 8th KpqC workshop, we updated the proofs of Lemma 4.3. Specifically, Prof. Joohee Lee noted that the precondition for applying the rigidity of PKE in Lemma 4.3 was not fully satisfied. 

Changes to the implementation are as follows: 

1. Source Code for the Hash Functions

 We replaced the source code of SHA256 and additionally used the source code for SHAKE256, adapted from https://github.com/kpqc-cryptocraft/KpqClean_ver2. 

2. Changes in the Key Generation

To improve the efficiency of key generation, we adopted an early abort approach when checking the invertibility of a polynomial. 

When checking the invertibility of a polynomial, we need to verify that it is invertible in all rings Z_q[x]/⟨x^d − \zeta_i⟩. For efficiency, we abort as soon as we find the first ring in which the polynomial is not invertible.

One may wonder whether this type of early abort could leak information about the randomness used to sample the polynomial. 

However, since the rejected polynomial is not reused as part of the secret key, we believe this approach is secure, provided that the underlying randombytes function is forward-secure. 

3. Changes in Ring Multiplication and Inversion

To improve the efficiency of key generation, we adopted lazy Montgomery reduction in the implementation of ring operations (multiplication and inversion) in \prod_{i=0}^{n/d−1} Z_q[x]/⟨x^d −w⟩ for d = 3, 4. 

Also, to enhance the efficiency of the modular inversion using Fermat’s Little Theorem, a −1 ≡ a q−2 (mod q), we leveraged the binary structure of q − 2 = 3455 = 110101111111(2), inspired by the fast modular inversion in Curve25519.

Thank you.

Best regards,  
NTRU+ Team