NTRU+ version update v1.1

[김종현]

Dear all,

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

Those can be found at the following links;

Homepage: https://sites.google.com/view/ntruplus

GitHub: https://github.com/ntruplus/ntruplus

In terms of the specification, the primary changes are as follows:

1. Modifying the Inv function of SOTP to resist against Lee's Attacks

In June 2023, Joohee Lee announced a CCA attack against NTRU+, which is based on the ambiguity in the definition of the Inv function. Version 1.1 of NTRU+ addresses this issue by providing a clearer definition of the Inv function.

2. Modifying the Encap and Decap algorithms to consider multi-target attacks

In the previous version 1.0, the transformation from IND-CPA secure PKE to IND-CCA secure KEM did not consider the multi-target attacks.

To achieve the multi-target security in version 1.1, we have modified the way of generating the randomness used for IND-CPA PKE as r=H(m,F(pk)).

Accordingly, we also have changed the secret key into sk  = (f, h^-1, F(pk)), which increases the secret key size by 32 bytes in all parameters.

3. Modifying the structure of NTT for NTRU+576 and NTRU+1152

The rings used for NTRU+576 and NTRU+1152 can be factored all the way down to Prod_{i=0}^{n} Z_q[x]/<x-zeta_i>.

However, if we apply NTT all the way down to Prod_{i=0}^{n} Z_q[x]/<x-zeta_i>, it requires n modulus inversions during the key generation to compute f^-1.

To reduce this to n/2 modulus inversions, we have factored it into Prod_{i=0}^{n/2} Z_q[x]/<x^2-zeta_i> in the version 1.0.

In version 1.1, we can further reduce this to n/3 modulus inversions by applying NTT to Prod_{i=0}^{n/3} Z_q[x]/<x^3-zeta_i>.

Next, in terms of our implementation, the changes are as follows:

1. Modifying the Inv algorithm of SOTP to counter Lee's Attacks

2. Modifying the Encap and Decap algorithms to consider multi-target attacks

3. Modifying the structure of NTT for NTRU+576 and NTRU+1152

As a result, this modification allows for improving the key generation timings and reducing the size of precomputation tables.

4. Modifying the Radix-3 NTT Implementation

Implementing Radix-3 NTT naively requires 2n multiplications per layer.

In the previous implementation, we reduced this to 4n/3 multiplications, 

but by adapting the recent result (https://eprint.iacr.org/2022/726.pdf),

we can further reduce 4n/3 to n multiplications.  

5. Removing the dependencies on OpenSSL and AVX in Reference Implementation

The initial implementation used the code of NTTRU (https://github.com/gregorseiler/NTTRU), which uses AVX assembly codes for the implementation of AES-256-CTR.

Also, the initial implementation used the "rng.c" provided by NIST, which also had OpenSSL dependencies.

To remove those dependencies, we have referred to the code of CRYSTALS-Kyber (https://github.com/pq-crystals/kyber).

6. Reducing the size of the pre-computation table in the reference implementation

In the previous implementation, Performing NTT and Inverse NTT needed two separate precomputation tables.

The revised implementation has reduced it to one table by adapting the code of CRYSTALS-Kyber, with our additional manipulation to support the Radix-3 NTT layer.

Thank you.

Best regards,

NTRU+ Team