A Generalization of NTRUEncrypt

Zhiyong Zheng, Fengxia Liu, Huang Wenlin, Jie Xu, Tian KunFinancial 2023 · DOI · OpenAlex

Abstract: The main purpose of this chapter is to give a more general construction of NTRU based on ideal matrices and $q$-ary lattice theory. To understand our construction, first we discuss a more general form of the ordinary cyclic code, namely $\phi$-cyclic code, which firstly appeared in (Lopez-Permouth et al., 2009; Shi et al., 2020); thus, we give a more generalized NTRUEncrypt from replacing finite field by real number field $\mathbb{R}$.

Introduction

NTRUEncrypt stands as a cornerstone of lattice-based public-key cryptography, recognized for its efficiency and potential resilience in a post-quantum landscape. Traditionally, NTRU is defined over the polynomial ring $\mathbb{Z}[x]/\langle x^n - 1 \rangle$. While this structure allows for fast computation via circulant matrices, it also imposes a rigid algebraic constraint. This paper explores a mathematical generalization, extending the NTRU framework to support any suitable monic polynomial $\phi(x)$, thereby introducing a more flexible class of "$\phi$-cyclic" codes and "ideal matrices."

Methodology: Beyond Circulant Matrices

The core of this generalization lies in redefining the underlying algebraic structures that facilitate encryption and decryption.

1. $\phi$-Cyclic Codes and Ideal Matrices

In standard NTRU, cyclic codes correspond to ideals in the ring $F_q[x]/\langle x^n - 1 \rangle$. The authors generalize this to $\phi$-cyclic codes, which are invariant under a linear transformation $\tau_\phi$ dictated by the coefficients of a chosen polynomial $\phi(x)$. These codes are shown to be equivalent to the ideals of the quotient ring $F_q[x]/\langle \phi(x) \rangle$.

To represent polynomial multiplication within these generalized rings, the authors introduce ideal matrices. These serve as the functional equivalent of circulant matrices. Crucially, the authors prove that these ideal matrices commute ($H^*(f)H^*(g) = H^*(g)H^*(f)$), a property essential for the consistency of the decryption process.

2. Convolutional Modular Lattices

The security of NTRU relies on the difficulty of finding short vectors in specific lattices. The authors define a new class of $q$-ary lattices that are closed under the transformation defined by $\phi(x)$. The secret key is embedded as a "short" vector within this lattice, while the public key is represented using the Hermite Normal Form (HNF) to ensure a canonical and compact basis.

Key Insights

  • Algebraic Flexibility: The security of the NTRU primitive is not strictly tied to the polynomial $x^n - 1$. Any ring where "short" elements can be defined and multiplication can be represented by structured matrices can potentially host an NTRU-like system.
  • The Role of Separable Polynomials: The authors emphasize the use of separable polynomials (those without multiple roots). This property ensures the existence of unit-like elements within the ideals, simplifying the algebra and ensuring system reliability.
  • Theoretical Convergence: The work bridges classical algebraic coding theory (polycyclic codes) with modern lattice cryptography, demonstrating how structural insights from coding theory can refine cryptographic constructions.

Results and Decryption Correctness

The paper provides formal proofs (Theorems 1, 2, and 3) establishing that:

  1. Ideal matrices correctly represent ring arithmetic.
  2. The constructed lattice $\Lambda_q(A)$ is a valid convolutional modular lattice containing the secret key pair $(f, g)$.
  3. Decryption is mathematically sound. If parameters such as the density of secret vectors ($d_f$) are chosen so that intermediate coordinates remain within the bounds of $q/2$, the original message $m$ is perfectly recoverable via reduction modulo $p$.

Limitations and Future Directions

As a theoretical foundation, this work opens several avenues for further research:

  • Cryptanalysis: While the construction is robust, its resistance to modern lattice reduction algorithms (like BKZ or LLL) across different choices of $\phi(x)$ remains to be empirically verified.
  • Performance: The computational efficiency of ideal matrices compared to circulant matrices (which benefit from FFT) needs benchmarking.
  • Continuous Fields: While the focus here is on integer coefficients, the abstract suggests potential extensions into the real number field $\mathbb{R}$, which could lead to entirely new classes of cryptographic primitives.

Summary updated

Abstract

Abstract The main purpose of this chapter is to give a more general construction of NTRU based on ideal matrices and q -ary lattice theory. To understand our construction, first we discuss a more general form of the ordinary cyclic code, namely $$\phi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϕ</mml:mi> </mml:math> -cyclic code, which firstly appeared in (Lopez-Permouth et al., 2009; Shi et al., 2020); thus, we give a more generalized NTRUEncrypt from replacing finite field by real number field $$\mathbb {R}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>R</mml:mi> </mml:math> .
BibTeX
@inproceedings{zheng2023generalization,
  author = {Zhiyong Zheng and Fengxia Liu and Huang Wenlin and Jie Xu and Tian Kun},
  title = {{A Generalization of NTRUEncrypt}},
  booktitle = {Financial},
  year = {2023},
  doi = {10.1007/978-981-99-2366-3\_6},
}
Figure