A Generalization of NTRUEncrypt —Cryptosystem Based on Ideal Lattice

Zhiyong Zheng¹, Fengxia Liu², Wenlin Huang¹, Jie Xu¹, Kun Tian^1*

¹Engineering Research Center of Ministry of Education for Financial Computing and Digital Engineering, Renmin University of China, Beijing, China.
²Artificial Intelligence Research Institute, Beihang University, Beijing, China.

DOI: 10.4236/jis.2022.133010                

Abstract

The purpose of this article is to extend the theory of circulant matrix to general ideal matrix, and to construct more general NTRU cryptosystem combined with the  φ-cyclic code. To understand our construction, first we discuss a more general form of the ordinary cyclic code, namely  φ-cyclic code, which firstly appeared in [1] and [2], thus we give a more generalized NTRUEncrypt by replacing finite field with real number field R.

Keywords

φ-Cyclic Code, Ideal Matrices, Convolutional Modular Lattice, NTRU

1. Introduction

Lattice theory based cryptography is a representative technology of post quantum cryptography, which is recognized by the academic community as being able to resist quantum computing attacks. Cyclic code and the number theory research unit (NTRU) cryptosystem are two representatives of the post quantum cryptography. Both the two cryptosystems are based on the theory of circulant matrix. Cyclic code plays a central role in algebraic coding theory (see Chapter 6 of [3]). An important class of cyclic code named BCH code was discovered in 1960 [4]. After that, many other codes were developed based on cyclic code, such as polynomial code, Goppa code and so on [5]. The $\varphi$ -cyclic code was firstly introduced in [1], which was applied to McEliece and Niederriter’s cryptosystems.

NTRU cryptosystem is a new public key cryptosystem based on lattice hard problem proposed in 1996 by three digit theorists Hoffstein, Piper and Silverman of Brown University in the United States [6]. Its main feature is that the key generation is very simple, and the encryption and decryption algorithm is much faster than the commonly used RSA and elliptic curve cryptography. In particular, NTRU can resist quantum computing attacks and is considered to be a potential public key cryptography that can replace RSA in the post quantum cryptography era. The essence of NTRU cryptographic design is the generalization of RSA on polynomials, so it is called the cryptosystem based on polynomial rings. However, NTRU can give a completely equivalent form by using the concept of q-ary lattice, so NTRU is also a lattice based cryptosystem.

Many researchers have presented some variations of NTRU by changing its algebraic structure. In 2002, Gaborit introduced an NTRU-like cryptosystem called CTRU by replacing the base ring of the NTRU with a polynomial ring over a binary field $F_2\left[x\right]$ [7]. They proved that their system is successfully decrypted. In 2005, Kouzmenko showed that CTRU is weak under a time attack and proposed the GNTRU cryptosystem based on Gaussian integers $Z\left[i\right]$ [8]. In the same year, Coglianese introduced an analog to the NTRU cryptosystem called MaTRU [9]. MaTRU is based on a ring of all square matrices with polynomial entries. In 2009, Malekian introduced the QTRU cryptosystem based on quaternion algebra [10]. They also introduced the OTRU cryptosystem in 2010 based on Octonion algebra [11]. In 2016, Alsaidi proposed a public key cryptosystem BITRU based on binary algebra [12]. However, all of the above variations of NTRU have limitations. The purpose of this article is to extend the theory of circulant matrix to general ideal matrix, and to construct more general NTRU cryptosystem combined with the $\varphi$ -cyclic code. The motivation of this research is to adapt the distributed scenario of blockchain architecture and apply the post quantum cryptography in it.

2. $\varphi$ -Cyclic Code

Let $F_q$ be a finite field with $q$ elements and $q$ be a power of a prime number, $F_q\left[x\right]$ be the polynomial ring of $F_q$ with variable $x$. Let $F_q^n$ be the $n$ -dimensional linear space over $F_q$, and $a=\left(a_0,a_1,\cdots ,a_{n-1}\right)\in F_q^n$ be a fixed vector in $F_q^n$ with $a_0\ne 0$, the associated polynomial of $a$ given by

$\varphi \left(x\right)={\varphi }_a\left(x\right)=x^n-a_{n-1}{x}^{n-1}-\cdots -a_{1}x-a_0\in F_q\left[x\right],a_0\ne 0.$ (1.1)

Let $\langle \varphi \left(x\right)\rangle$ be the principal ideal generated by $\varphi \left(x\right)$ in $F_q\left[x\right]$. There is a one to one correspondence between $F_q^n$ and the quotient ring $R=F_q\left[x\right]/\langle \varphi \left(x\right)\rangle$, given by

$c=\left(c_0,c_1,\cdots ,c_{n-1}\right)\in F_q^n\rightleftarrows c\left(x\right)=c_0+c_{1}x+\cdots +c_{n-1}{x}^{n-1}\in R.$ (1.2)

In fact, this correspondence is also an isomorphism of Abel groups. One may extend this correspondence to subsets of $F_q^n$ and $R$ by

$C\subset F_q^n\rightleftarrows C\left(x\right)=\left\{c\left(x\right)|c\in C\right\}\subset R.$ (1.3)

If $C\subset F_q^n$ is a linear subspace of $F_q^n$ of dimension $k$, then $C$ is called a linear code in coding theory and written by $C=[n,k]$ as usual. Each vector $c=\left(c_0,c_1,\cdots ,c_{n-1}\right)\in C$ is called a codeword of length $n$. Obviously, $C=\left[n,0\right]$ and $C=\left[n,n\right]$ are two trivial codes. Another one is called constant codes, which is almost trivial given by

$C=\left\{\left(b,b,\cdots ,b\right)|b\in F_q\right\},\text{and}C=\left[n,1\right].$

According to the given polynomial $\varphi \left(x\right)={\varphi }_a\left(x\right)$, we may define a linear transformation ${\tau }_{\varphi }$ in $F_q^n$,

${\tau }_{\varphi }\left(c\right)={\tau }_{\varphi }\left(\left(c_0,c_1,\cdots ,c_{n-1}\right)\right)=\left(a_0{c}_{n-1},c_0+a_1{c}_{n-1},\cdots ,c_{n-2}+a_{n-1}{c}_{n-1}\right)$ (1.4)

It is easily seen that ${\tau }_{\varphi }:F_q^n\to F_q^n$ is a linear transformation.

Definition 1.1. Let $C\subset F_q^n$ be a linear code. It is called a $\varphi$ -cyclic code, if

$\forall c\in C\Rightarrow {\tau }_{\varphi }\left(c\right)\in C.$ (1.5)

In other words, a linear code $C$ is a $\varphi$ -cyclic code, if and only if $C$ is closed under linear transformation ${\tau }_{\varphi }$. Clearly, if $a=\left(1,0,\cdots ,0\right)$, and ${\varphi }_a\left(x\right)=x^n-1$, then the $\varphi$ -cyclic code is precisely the ordinary cyclic code (see Chapter 6 of [1]).

Remark The $\varphi$ -cyclic code we give here is polycyclic code in fact, which firstly appeared in [1] [2], but we mainly concern for its application to McEliece and Niederriter’s cryptosystems. We first show that there is a one to one correspondence between $\varphi$ -cyclic codes in $F_q^n$ and ideals in $R=F_q\left[x\right]/\langle \varphi \left(x\right)\rangle$.

Theorem 1. Let $C\subset F_q^n$ be a subset, then $C$ is a $\varphi$ -cyclic code, if and only if $C\left(x\right)$ is an ideal of $R$.

Proof: We use column notation for vector in $F_q^n$, then linear transformation ${\tau }_{\varphi }$ may be written as

${\tau }_{\varphi }\left(\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{n-1}\end{array}\right)=\left(\begin{array}{c}{a}_0{c}_{n-1}\\ c_0+a_1{c}_{n-1}\\ ⋮\\ c_{n-2}+a_{n-1}{c}_{n-1}\end{array}\right),\forall c=\left(\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{n-1}\end{array}\right)\in F_q^n.$

Let $T_{\varphi }$ be a $n\times n$ square matrix over $F_q$,

$T_{\varphi }=\left(\begin{array}{cccc}0& \cdots & 0& a_0\\ & & & a_1\\ & I_{n-1}& & ⋮\\ & & & a_{n-1}\end{array}\right)\in F_q^{n\times n}.$ (1.6)

where $I_{n-1}$ is the $\left(n-1\right)\times \left(n-1\right)$ unit matrix. The matrix expression of ${\tau }_{\varphi }$ as follows

${\tau }_{\varphi }\left(\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{n-1}\end{array}\right)=T_{\varphi }\left(\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{n-1}\end{array}\right)=\left(\begin{array}{c}{a}_0{c}_{n-1}\\ c_0+a_1{c}_{n-1}\\ ⋮\\ c_{n-2}+a_{n-1}{c}_{n-1}\end{array}\right).$ (1.7)

Suppose $C\subset F_q^n$ and $C\left(x\right)$ is an ideal of $R$, it is clear that $C$ is a linear code of $F_q^n$. To prove $C$ is a $\varphi$ -cyclic code, we note that for any polynomial $c\left(x\right)\in C\left(x\right)$, then $xc\left(x\right)\in C\left(x\right)$ if and only if ${\tau }_{\varphi }\left(c\right)\in C$, namely, if $c\left(x\right)\in C\left(x\right)$, then

$xc\left(x\right)\in C\left(x\right)\iff {\tau }_{\varphi }\left(c\right)\in C\iff T_{\varphi }c\in C.$ (1.8)

Therefore, if $C\left(x\right)$ is an ideal of $R$, then we have immediately that $C$ is a $\varphi$ -cyclic code of $F_q^n$.

Conversely, if $C\subset F_q^n$ is a $\varphi$ -cyclic code, then for all $k\ge 1$, we have

$\forall c\in C\Rightarrow T_{\varphi }^{k}c\in C,k\ge 1.$

It follows that

$\forall c\left(x\right)\in C\left(x\right)\Rightarrow x^{k}c\left(x\right)\in C\left(x\right),0\le k\le n-1,$

which implies $C\left(x\right)$ is an ideal of $R$. This is the proof of Theorem 1. $\square$

By Theorem 1, to find a $\varphi$ -cyclic code, it is enough to find an ideal of $R$. There are two trivial ideals $C\left(x\right)=0$ and $C\left(x\right)=R$, the corresponding $\varphi$ -cyclic codes are $C=\left[n,0\right]$ and $C=F_q^n$ respectively, which are called trivial $\varphi$ -cyclic code. To find non-trivial $\varphi$ -cyclic codes, we make use of homomorphic theorems, which is a standard technique in Algebra. Let $\pi$ be the natural homomorphism from $F_q\left[x\right]$ to its quotient ring $R=F_q\left[x\right]/\langle \varphi \left(x\right)\rangle$, $\ker \pi =\langle \varphi \left(x\right)\rangle$,

$\langle \varphi \left(x\right)\rangle \subset N\subset F_q\left[x\right]\stackrel{\pi }{\to }R=F_q\left[x\right]/\langle \varphi \left(x\right)\rangle ,$ (1.9)

where $N$ is an ideal of $F_q\left[x\right]$, which is containing $\ker \pi =\langle \varphi \left(x\right)\rangle$. Since $F_q\left[x\right]$ is a principal ideal domain, then $N=\langle g\left(x\right)\rangle$ is a principal ideal generated by a monic polynomial $g\left(x\right)\in F_q\left[x\right]$. It is easy to see that

$\langle \varphi \left(x\right)\rangle \subset \langle g\left(x\right)\rangle \iff g\left(x\right)|\varphi \left(x\right).$

It follows that all ideals $N$ satisfying (1.9) are given by

$\left\{\langle g\left(x\right)\rangle |g\left(x\right)\in F_q\left[x\right]\text{ismonicand}g\left(x\right)|\varphi \left(x\right)\right\}.$

We write by $\langle g\left(x\right)\rangle$ mod $\varphi \left(x\right)$, the image of $\langle g\left(x\right)\rangle$ under $\pi$, it is easy to check

$\langle g\left(x\right)\rangle \text{mod}\varphi \left(x\right)=\left\{h\left(x\right)g\left(x\right)|h\left(x\right)\in F_q\left[x\right]\text{and}\mathrm{deg}h\left(x\right)+\mathrm{deg}g\left(x\right)<n\right\},$ (1.10)

more precisely, which is a representative elements set of $\langle g\left(x\right)\rangle$ mod $\varphi \left(x\right)$, by homomorphism theorem in ring theory, all ideals of $R$ given by

$\left\{\langle g\left(x\right)\rangle \text{mod}\varphi \left(x\right)|g\left(x\right)\in F_q\left[x\right]\text{ismonicand}g\left(x\right)|\varphi \left(x\right)\right\}.$ (1.11)

Let $d$ be the number of monic divisors of $\varphi \left(x\right)$ in $F_q\left[x\right]$, we can get the following corollary immediately.

Corollary 1. The number of $\varphi$ -cyclic code in $F_q^n$ is $d$.

To compare the $\varphi$ -cyclic code and ordinary cyclic code, we see a simple example.

Example 1. Constant code $C$ is always a cyclic code for $1+x+\cdots +x^{n-1}|x^n-1$, and its generated polynomial is just $1+x+\cdots +x^{n-1}$. But constant code $C$ in $F_q^n$ is not always a $\varphi$ -cyclic code, it is a $\varphi$ -cyclic code if and only if $1+x+\cdots +x^{n-1}|\varphi \left(x\right)$, an equivalent condition for $1+x+\cdots +x^{n-1}|\varphi \left(x\right)$ is

$a_{n-1}=a_{n-2}=\cdots =a_1=b,\text{and}{a}_0=1+b.$

Definition 1.2. Let $C$ be a $\varphi$ -cyclic code and $C\left(x\right)=g\left(x\right)$ mod $\varphi \left(x\right)$. We call $g\left(x\right)$ is the generated polynomial of $C$, where $g\left(x\right)$ is monic and $g\left(x\right)|\varphi \left(x\right)$.

Lemma 1.1. Let $g\left(x\right)=g_0+g_{1}x+\cdots +g_{n-k-1}{x}^{n-k-1}+x^{n-k}$ be the generated polynomial of a $\varphi$ -cyclic code $C$, where $1\le k\le n-1$, and $g\left(x\right)|\varphi \left(x\right)$, then $C=\left[n,k\right]$ and a generated matrix for $C$ is the following block matrix

$G={\left(\begin{array}{c}g\\ {\tau }_{\varphi }\left(g\right)\\ {\tau }_{\varphi }^2\left(g\right)\\ \begin{array}{c}⋮\\ {\tau }_{\varphi }^{k-1}\left(g\right)\end{array}\end{array}\right)}_{k\times n},$ (1.12)

where $g=\left(g_0,g_1,\cdots ,g_{n-k-1},1,0,\cdots ,0\right)\in C$ is the corresponding codeword of $g\left(x\right)$, and ${\tau }_{\varphi }^i\left(g\right)={\tau }_{\varphi }^{i-1}\left({\tau }_{\varphi }\left(g\right)\right)$ for $1\le i\le n-1$.

Proof: By assumption, $C\left(x\right)=\langle g\left(x\right)\rangle$ mod $\varphi \left(x\right)$, then $\left\{g,{\tau }_{\varphi }\left(g\right),\cdots ,{\tau }_{\varphi }^{k-1}\left(g\right)\right\}\subset C$, we are to prove it is a basis of $C$. First, these vectors are linearly independent. Otherwise, we have

${\displaystyle \underset{i=0}{\overset{k-1}{\sum }}{b}_i{\tau }_{\varphi }^i\left(g\right)=0,\text{forsome}{b}_i\in F_q},$ (1.13)

and the corresponding polynomial is zero, namely

$\left({\displaystyle \underset{i=0}{\overset{k-1}{\sum }}{b}_i{x}^i}\right)g\left(x\right)=0.$

It follows that

${\displaystyle \underset{i=0}{\overset{k-1}{\sum }}{b}_i{x}^i=0\Rightarrow b_i=0\text{forall}i,0\le i\le k-1.}$

Next, if $c\in C$, and $c\left(x\right)\in C\left(x\right)$, by (1.10), there is a polynomial $b\left(x\right)=b_0+b_{1}x+\cdots +b_{k-2}{x}^{k-2}+x^{k-1}$ such that

$c\left(x\right)=b\left(x\right)g\left(x\right)=\left({\displaystyle \underset{i=0}{\overset{k-1}{\sum }}{b}_i{x}^i}\right)g\left(x\right),\text{where}{b}_{k-1}=1.$

Thus we have the corresponding codeword of $C(\; x\; )$

$c={\displaystyle \underset{i=0}{\overset{k-1}{\sum }}{b}_i{\tau }_{\varphi }^i\left(g\right).}$

This shows that $\left\{g,{\tau }_{\varphi }\left(g\right),\cdots ,{\tau }_{\varphi }^{k-1}\left(g\right)\right\}$ is a basis of $C$, and a generated matrix for $C$ is

$G={\left(\begin{array}{c}g\\ {\tau }_{\varphi }\left(g\right)\\ {\tau }_{\varphi }^2\left(g\right)\\ \begin{array}{c}⋮\\ {\tau }_{\varphi }^{k-1}\left(g\right)\end{array}\end{array}\right)}_{k\times n}.$

We have lemma 1.1 at once. $\square$

To describe a parity check matrix for a $\varphi$ -cyclic code, for any $c=\left(c_0,c_1,\cdots ,c_{n-1}\right)\in F_q^n$, we write

$\bar{c}=\left(c_{n-1},c_{n-2},\cdots ,c_1,c_0\right)\in F_q^n.$

Lemma 1.2. Suppose $C$ is a $\varphi$ -cyclic code with generated polynomial $g\left(x\right)$, where $g\left(x\right)|\varphi \left(x\right)$ and $\mathrm{deg}g\left(x\right)=n-k$. Let $h\left(x\right)g\left(x\right)=\varphi \left(x\right)$, where $h\left(x\right)=h_0+h_{1}x+\cdots +h_{k-1}{x}^{k-1}+x^k$. Then a parity check matrix for $C$ is

$H={\left(\begin{array}{c}\bar{h}\\ {\tau }_{\varphi }\left(\bar{h}\right)\\ ⋮\\ {\tau }_{\varphi }^{n-k-1}\left(\bar{h}\right)\end{array}\right)}_{\left(n-k\right)\times n}.$ (1.14)

Proof: Since $h\left(x\right)g\left(x\right)=\varphi \left(x\right)$, it means that $h\left(x\right)g\left(x\right)=0$ in $R=F_q\left[x\right]/\langle \varphi \left(x\right)\rangle$, thus we have

$g_0{h}_i+g_1{h}_{i-1}+\cdots +g_{n-k}{h}_{i-n+k}=0,\forall 0\le i\le n-1.$

It follows that $G{H}^{\prime }=0$, where $G$ is a generated matrix for $C$ given by (1.12). Therefore, $H$ is a parity check matrix for $C$. $\square$

A separable polynomial in Algebra means that it has no multiple roots in its splitting field. The following lemma shows that there is a unit element in any non-zero ideal of $R$, when $\varphi \left(x\right)$ is a separable polynomial.

Lemma 1.3. Suppose $\varphi \left(x\right)$ is a separable polynomial of $F_q$, and $C\left(x\right)=g\left(x\right)$ mod $\varphi \left(x\right)$ is an ideal of $R$ with $\mathrm{deg}g\left(x\right)\le n-1$, then there exists an element $d\left(x\right)\in C\left(x\right)$ such that

$c\left(x\right)d\left(x\right)=c\left(x\right),\text{forall}c\left(x\right)\in C\left(x\right).$

Proof: Let $h\left(x\right)g\left(x\right)=\varphi \left(x\right)$. Since $\varphi \left(x\right)$ is a separable polynomial, then gcd $\left(g\left(x\right),h\left(x\right)\right)=1$, and there are two polynomial $a\left(x\right)$ and $b\left(x\right)$ in $F_q\left[x\right]$ such that

$a\left(x\right)g\left(x\right)+b\left(x\right)h\left(x\right)=1.$

Let

$d\left(x\right)=a\left(x\right)g\left(x\right)=1-b\left(x\right)h\left(x\right)\in C\left(x\right).$

If $c\left(x\right)\in C\left(x\right)$, by (1.10), we write $c\left(x\right)=g\left(x\right)g_1\left(x\right)$, it follows that

$\begin{array}{c}c\left(x\right)d\left(x\right)\equiv a\left(x\right)g\left(x\right)g\left(x\right)g_1\left(x\right)\equiv \left(1-b\left(x\right)h\left(x\right)\right)g\left(x\right)g_1\left(x\right)\\ \equiv g\left(x\right)g_1\left(x\right)\equiv c\left(x\right)\left(\mathrm{mod}\varphi \left(x\right)\right).\end{array}$

Thus we have $c\left(x\right)d\left(x\right)=c\left(x\right)$ in $R$. $\square$

Next, we discuss maximal $\varphi$ -cyclic code. Let $C\left(x\right)=g\left(x\right)$ mod $\varphi \left(x\right)$, and $g\left(x\right)$ be an irreducible polynomial in $F_q\left[x\right]$, we call the corresponding $\varphi$ -cyclic code $C$ a maximal $\varphi$ -cyclic code, because $\langle g\left(x\right)\rangle$ is a maximal ideal in $F_q\left[x\right]$.

Lemma 1.4. Let $C$ be a maximal $\varphi$ -cyclic code with generated polynomial $g\left(x\right)$, $\beta$ be a root of $g\left(x\right)$ in some extensions of $F_q$, then

$C\left(x\right)=\left\{a\left(x\right)|a\left(x\right)\in R\text{and}a\left(\beta \right)=0\right\}.$ (1.15)

Proof: If $a\left(x\right)\in C\left(x\right)$, by (1.10) we have $a\left(\beta \right)=0$ immediately. Conversely, if $a\left(x\right)\in F_q\left[x\right]$ and $a\left(\beta \right)=0$, since $g\left(x\right)$ is irreducible, thus we have $g\left(x\right)|a\left(x\right)$, and (1.15) follows at once. $\square$

An important application of maximal $\varphi$ -cyclic code is to construct an error-correcting code, so that we may obtain a modified McEliece-Niederriter’s cryptosystem. To do this, let $1\le m<\sqrt{n}$, and $F_{q^m}$ be an extension field of $F_q$ of degree $m$. Suppose $F_{q^m}=F_q\left(\theta \right)$, where $\theta$ is a primitive element of $F_{q^m}$ and $F_q\left(\theta \right)$ is the simple extension containing $F_q$ and $\theta$. Let $g\left(x\right)\in F_q\left[x\right]$ be the minimum polynomial of $\theta$, then $g\left(x\right)$ is an irreducible polynomial of degree $m$ of $F_q\left[x\right]$. It is well-known that $F_{q^m}$ is a Galois extension of $F_q$, so that all roots of $g\left(x\right)$ are in $F_{q^m}$. Let ${\beta }_1,{\beta }_2,\cdots ,{\beta }_m$ be all roots of $g\left(x\right)$, the Vandermonde matrix $V\left({\beta }_1,{\beta }_2,\cdots ,{\beta }_m\right)$ defined by

$H=V\left({\beta }_1,{\beta }_2,\cdots ,{\beta }_m\right)={\left(\begin{array}{ccccc}1& {\beta }_1& {\beta }_1^2& \cdots & {\beta }_1^{n-1}\\ 1& {\beta }_2& {\beta }_2^2& \cdots & {\beta }_2^{n-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\beta }_m& {\beta }_m^2& \cdots & {\beta }_m^{n-1}\end{array}\right)}_{m\times n},$ (1.16)

where ${\beta }_1=\theta$ and each ${\beta }_i$ is a vector of ${\left(F_q\right)}^m$. For arbitrary monic polynomial $h\left(x\right)\in F_q\left[x\right]$, $\mathrm{deg}h\left(x\right)=n-m$, let $\varphi \left(x\right)=h\left(x\right)g\left(x\right)$ and $C$ be a maximal $\varphi$ -cyclic code generated by $g\left(x\right)$. It is easy to verify that

$c\in C\iff c{H}^{\prime }=0.$

Therefore, $H$ is a parity check matrix for $C$. If we choose the primitive element $\theta$, so that any $d-1$ columns in $H$ are linearly independent, then the minimum distance of $C$ is greater than $d$, and $C$ is a t-error-correcting code, where $t=\left[\frac{d}{2}\right]$.

The public key cryptosystems based on algebraic coding theory were created by R. J. McEliece [13] and H. Niederriter [14], a suitable t-error-correcting code plays a key role in their construction. The error-correcting code $C$ should satisfy the following requirements:

1) $C$ should have a relatively large error-correcting capability so that a reasonable number of message vectors can be used;

2) $C$ should allow an efficient decoding algorithm so that the decryption can be carried out in a short time.

Our results supply a different way to choose an error-correcting code by selecting arbitrary irreducible polynomials $g\left(x\right)\in F_q\left[x\right]$ of degree $m$ and roots of $g\left(x\right)$ rather than an irreducible factor of $x^n-1$ and the roots of unit such as ordinary BCH code and Gappa code.

In fact, for any positive integer $m$, there is at least an irreducible polynomial $g\left(x\right)\in F_q\left[x\right]$ with degree $m$. Let $N_q\left(m\right)$ be the number of irreducible polynomials of degree $m$ in $F_q\left[x\right]$, then we have (see Theorem 3.25 of [15])

$N_q\left(m\right)=\frac{1}{m}{\displaystyle \underset{d|m}{\sum }u\left(\frac{m}{d}\right)q^d}=\frac{1}{m}{\displaystyle \underset{d|m}{\sum }u\left(d\right)q^{\frac{m}{d}}},$

where $u\left(d\right)$ is Mobius function.

Assuming one has selected two monic and irreducible polynomials $g\left(x\right)$ and $h\left(x\right)$ with $\mathrm{deg}g\left(x\right)=m$ and $\mathrm{deg}h\left(x\right)=n-m$, let $\varphi \left(x\right)=g\left(x\right)h\left(x\right)$, then one may obtain $\varphi$ -cyclic code $C$ generated by $g\left(x\right)$ or $h\left(x\right)$, which is more convenient and more flexible than the ordinary methods.

Remark It’s difficult to compare the error-correcting capability between $\varphi$ -cyclic code with existing cyclic codes of the same length and dimension. However, we believe that the advantages of $\varphi$ -cyclic code will become more clear when $q$ increases. We will discuss this carefully in another paper later.

3. A Generalization of NTRUEncrypt

The public key cryptosystem NTRU proposed in 1996 by Hoffstein, Pipher and Silverman, is the fastest known lattice based encryption scheme, although its description relies on arithmetic over polynomial quotient ring $Z\left[x\right]/\langle x^n-1\rangle$, it was easily observed that it could be expressed as a lattice based cryptosystem (see [16]). For the background materials, we refer to [3] [6] [17] [18] [19] and [20]. Our strategy in this section is to replace $Z\left[x\right]/\langle x^n-1\rangle$ by more general polynomial ring $Z\left[x\right]/\langle \varphi \left(x\right)\rangle$ and obtain a generalization of NTRUEncrypt, where $\varphi \left(x\right)$ is a monic polynomial of degree $n$ with integer coefficients.

In this section, we denote $\varphi \left(x\right)$ and $R$ by

$\varphi \left(x\right)=x^n-a_{n-1}{x}^{n-1}-\cdots -a_{1}x-a_0\in Z\left[x\right],R=Z\left[x\right]/\langle \varphi \left(x\right)\rangle ,a_0\ne 0.$ (2.1)

Let $H_{\varphi }\in Z^{n\times n}$ be a square matrix given by

$H=H_{\varphi }={\left(\begin{array}{cccc}0& \cdots & 0& a_0\\ & & & a_1\\ & I_{n-1}& & ⋮\\ & & & a_{n-1}\end{array}\right)}_{n\times n},$ (2.2)

where $I_{n-1}$ is $\left(n-1\right)\times \left(n-1\right)$ unit matrix. Obviously, $\varphi \left(x\right)$ is the characteristic polynomial of $H$, and $H$ defines a linear transformation of ${ℝ}^n\to {ℝ}^n$ by $x\to Hx$, where $ℝ$ is real number field, $x$ is a column vector of ${ℝ}^n$. We may extend this transformation to ${ℝ}^{2n}$ and denote $\sigma$ by

$\sigma \left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\left(\begin{array}{c}H\alpha \\ H\beta \end{array}\right),\text{where}\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)\in {ℝ}^{2n}.$ (2.3)

Of course, $\sigma$ is again a linear transformation of ${ℝ}^{2n}\to {ℝ}^{2n}$.

According to [20], a $q$ -ary lattice is a lattice $L$ such that $q{Z}^n\subset L\subset Z^n$, where $q$ is a positive integer.

Definition 2.1. A $q$ -ary lattice $L$ is called convolutional modular lattice, if $L$ is in even dimension $2n$ satisfying

$\forall \left(\begin{array}{c}\alpha \\ \beta \end{array}\right)\in L\Rightarrow \sigma \left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\left(\begin{array}{c}H\alpha \\ H\beta \end{array}\right)\in L.$ (2.4)

In other words, a convolutional modular lattice is a $q$ -ary lattice in even dimension and is closed under the linear transformation $\sigma$.

Recalling the secret key $\left(\begin{array}{c}f\\ g\end{array}\right)$ of NTRU is a pair of polynomials of degree $n-1$, we may regard $f$ and $g$ as column vectors in $Z^n$. To obtain a convolutional modular lattice containing $\left(\begin{array}{c}f\\ g\end{array}\right)$, we need some help of ideal matrices. An ideal matrix generated by a vector $f$ is defined by

$H^{*}\left(f\right)=H_{\varphi }^{*}\left(f\right)={\left[f,Hf,H^{2}f,\cdots ,H^{n-1}f\right]}_{n\times n},$ (2.5)

which is a block matrix in terms of each column $H^{k}f\left(0\le k\le n-1\right)$. It is easily seen that $H^{*}\left(f\right)$ is a generalization of the classical circulant matrices (see [21]), in fact, let $\varphi \left(x\right)=x^n-1$, and $f\left(x\right)=f_0+f_{1}x+\cdots +f_{n-1}{x}^{n-1}\in Z\left[x\right]$, the ideal matrix $H_{\varphi }^{*}\left(f\right)$ generated by $f$ is given by

$H^{*}\left(f\right)=H_{\varphi }^{*}\left(f\right)=\left(\begin{array}{cccc}{f}_0& f_{n-1}& \cdots & f_1\\ f_1& f_0& \cdots & f_2\\ ⋮& ⋮& & ⋮\\ f_{n-1}& f_{n-2}& \cdots & f_0\end{array}\right),\varphi \left(x\right)=x^n-1,$

which is known as a circulant matrix. On the other hand, ideal matrix and ideal lattice play an important role in Ajtai’s construction of a collision resistant Hash function, the related materials we refer to [3] [22] [23] [24] [25] and [26].

First, we have to establish some basic properties for an ideal matrix $H^{*}\left(f\right)$, most of them are known when $H^{*}\left(f\right)$ is a circulant matrix.

Lemma 2.1. Suppose $H$ and $H^{*}\left(f\right)$ are given by (2.2) and (2.5) respectively, then for any $f\in {ℝ}^n$ we have

$H\cdot H^{*}\left(f\right)=H^{*}\left(f\right)\cdot H,\forall f\in {ℝ}^n.$

Proof: Since $\varphi \left(x\right)=x^n-a_{n-1}{x}^{n-1}-\cdots -a_{1}x-a_0$ is the characteristic polynomial of $H$, by Hamilton-Cayley theorem, we have

$H^n=a_0{I}_n+a_{1}H+\cdots +a_{n-1}{H}^{n-1}.$ (2.6)

Let

$b=\left(\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_{n-1}\end{array}\right),\text{and}H=\left(\begin{array}{cc}0& a_0\\ I_{n-1}& b\end{array}\right).$

By (2.5) we have

$\begin{array}{c}{H}^{*}\left(f\right)H=\left[f,Hf,\cdots ,H^{n-1}f\right]\left(\begin{array}{cc}0& a_0\\ I_{n-1}& b\end{array}\right)\\ =\left[Hf,H^{2}f,\cdots ,H^{n-1}f,a_{0}f+a_{1}Hf+\cdots +a_{n-1}{H}^{n-1}f\right]\\ =\left[Hf,H^{2}f,\cdots ,H^{n-1}f,H^{n}f\right]\\ =H\left[f,Hf,\cdots ,H^{n-1}f\right]=H\cdot H^{*}\left(f\right).\end{array}$

the lemma follows. $\square$

Lemma 2.2. For any $f=\left(\begin{array}{c}{f}_0\\ f_1\\ ⋮\\ f_{n-1}\end{array}\right)\in {ℝ}^n$ we have

$H^{*}\left(f\right)=f_0{I}_n+f_{1}H+\cdots +f_{n-1}{H}^{n-1}.$ (2.7)

Proof: We use induction on $n$ to show this conclusion. If $n=1$, it is trivial. Suppose it is true for $n$, we consider the case of $n+1$. For this purpose, we write $H=H_n$, $e_1,e_2,\cdots ,e_n$ the $n$ column vectors of unit in ${ℝ}^n$, namely

$e_1=\left(\begin{array}{c}1\\ 0\\ ⋮\\ 0\end{array}\right),e_2=\left(\begin{array}{c}0\\ 1\\ ⋮\\ 0\end{array}\right),\cdots \text{,}{e}_n=\left(\begin{array}{c}0\\ 0\\ ⋮\\ 1\end{array}\right),$

and

$H_{n+1}=\left(\begin{array}{cc}0& A_0\\ e_1& H_n\end{array}\right),$

where $A_0=\left(0,0,\cdots ,a_0\right)\in {ℝ}^n$ is a row vector. For any $k$, $1\le k\le n-1$, it is easy to check that

$H_n{e}_k=e_{k+1},H_n^k{e}_1=e_{k+1}\text{and}{H}_{n+1}^k=\left(\begin{array}{cc}0& A_0{H}_n^{k-1}\\ e_k& H_n^k\end{array}\right).$

Let $f=\left(\begin{array}{c}{f}_0\\ f_1\\ ⋮\\ \begin{array}{c}{f}_{n-1}\\ f_n\end{array}\end{array}\right)\in {ℝ}^{n+1}$, we denote $f^{\prime }$ by

$f^{\prime }=\left(\begin{array}{c}{f}_1\\ f_2\\ ⋮\\ f_n\end{array}\right)\in {ℝ}^n,\text{and}f=\left(\begin{array}{c}{f}_0\\ f^{\prime }\end{array}\right).$

By the assumption of induction, we have

$H_n^{*}\left(f^{\prime }\right)=\left[f^{\prime },H_n{f}^{\prime },\cdots ,H_n^{n-1}{f}^{\prime }\right]=f_1{I}_n+f_2{H}_n+\cdots +f_n{H}_n^{n-1}.$

It follows that

$\begin{array}{c}{H}_{n+1}^{*}\left(f\right)=\left[\left(\begin{array}{c}{f}_0\\ f^{\prime }\end{array}\right),H_{n+1}\left(\begin{array}{c}{f}_0\\ f^{\prime }\end{array}\right),\cdots ,H_{n+1}^n\left(\begin{array}{c}{f}_0\\ f^{\prime }\end{array}\right)\right]\\ =f_0{I}_n+f_1{H}_{n+1}+\cdots +f_n{H}_{n+1}^n.\end{array}$

We complete the proof of lemma 2.2. $\square$

We always suppose that $\varphi \left(x\right)\in Z\left[x\right]$ is a separable polynomial and $w_1,w_2,\cdots ,w_n$ are complex number roots of $\varphi \left(x\right)$, of which are different from each other. The Vandermonde matrix $V_{\varphi }$ generated by $\left\{w_1,w_2,\cdots ,w_n\right\}$ is

$V_{\varphi }=\left(\begin{array}{cccc}1& 1& \cdots & 1\\ w_1& w_2& \cdots & w_n\\ ⋮& ⋮& & ⋮\\ w_1^{n-1}& w_2^{n-1}& \cdots & w_n^{n-1}\end{array}\right),\text{anddet}\left(V_{\varphi }\right)\ne 0.$

Lemma 2.3. Let $f\left(x\right)=f_0+f_{1}x+\cdots +f_{n-1}{x}^{n-1}\in ℝ\left[x\right]$, then we have

$H^{*}\left(f\right)=V_{\varphi }^{-1}\text{diag}\left\{f\left(w_1\right),f\left(w_2\right),\cdots ,f\left(w_n\right)\right\}{V}_{\varphi },$ (2.8)

where $\text{diag}\left\{f\left(w_1\right),f\left(w_2\right),\cdots ,f\left(w_n\right)\right\}$ is the diagonal matrix.

Proof: By Theorem 3.2.5 of [21], for $H$, we have

$H=V_{\varphi }^{-1}\text{diag}\left\{w_1,w_2,\cdots ,w_n\right\}{V}_{\varphi }.$ (2.9)

By lemma 2.2, it follows that

$H^{*}\left(f\right)=V_{\varphi }^{-1}\text{diag}\left\{f\left(w_1\right),f\left(w_2\right),\cdots ,f\left(w_n\right)\right\}{V}_{\varphi }.$ $\square$

Now, we summarize some basic properties for ideal matrix as follows.

Theorem 2. Let $f\in {ℝ}^n$, $g\in {ℝ}^n$ be two column vectors and $H^{*}\left(f\right)$ be the ideal matrix generated by $f$, then we have:

(i) $H^{*}\left(f\right)H^{*}\left(g\right)=H^{*}\left(g\right)H^{*}\left(f\right)$.

(ii) $H^{*}\left(f\right)H^{*}\left(g\right)=H^{*}\left(H^{*}\left(f\right)g\right)$.

(iii) $\det \left(H^{*}\left(f\right)\right)={\displaystyle \underset{i=1}{\overset{n}{\prod }}f\left(w_i\right)}$.

(iv) $H^{*}\left(f\right)$ is an invertible matrix if and only if $\varphi \left(x\right)$ and $f\left(x\right)$ are coprime, i.e. $\gcd \left(\varphi \left(x\right),f\left(x\right)\right)=1$.

Proof: (i) and (ii) follow from lemma 2.2 immediately, (iii) and (iv) follow from lemma 2.3. Here we only give an equivalent form of (ii). Let

$f\ast g=H^{*}\left(f\right)g.$ (2.10)

then by (ii) we have

$H^{*}\left(f\ast g\right)=H^{*}\left(f\right)H^{*}\left(g\right).$ (2.11)

$\square$

To construct a convolutional modular lattice containing vector $\left(\begin{array}{c}f\\ g\end{array}\right)$, let $\left(\begin{array}{c}f\\ g\end{array}\right)\in Z^{2n}$, ${\left(H^{*}\left(f\right)\right)}^{\prime }$ be the transpose of $H^{*}\left(f\right)$, and

$A=\left[{\left(H^{*}\left(f\right)\right)}^{\prime },{\left(H^{*}\left(g\right)\right)}^{\prime }\right]={\left(\begin{array}{cc}\begin{array}{c}{f}^{\prime }\\ f^{\prime }{H}^{\prime }\\ f^{\prime }{\left(H^{\prime }\right)}^2\\ \begin{array}{c}⋮\\ f^{\prime }{\left(H^{\prime }\right)}^{n-1}\end{array}\end{array}& \begin{array}{c}{g}^{\prime }\\ g^{\prime }{H}^{\prime }\\ g^{\prime }{\left(H^{\prime }\right)}^2\\ \begin{array}{c}⋮\\ g^{\prime }{\left(H^{\prime }\right)}^{n-1}\end{array}\end{array}\end{array}\right)}_{n\times 2n},$ (2.12)

$A^{\prime }=\left(\begin{array}{c}{H}^{*}\left(f\right)\\ H^{*}\left(g\right)\end{array}\right)={\left(\begin{array}{c}\begin{array}{cccc}f& Hf& \cdots & H^{n-1}f\end{array}\\ \begin{array}{cccc}g& Hg& \cdots & H^{n-1}g\end{array}\end{array}\right)}_{2n\times n}.$ (2.13)

We consider $A$ and $A^{\prime }$ as matrices over $Z_q$, i.e. $A\in Z_q^{n\times 2n}$, $A^{\prime }\in Z_q^{2n\times n}$, a $q$ -ary lattice ${\Lambda }_q\left(A\right)$ is defined by (see [20])

${\Lambda }_q\left(A\right)=\left\{y\in Z^{2n}|\text{thereexists}x\in Z^n\Rightarrow y\equiv A^{\prime }x\left(\mathrm{mod}q\right)\right\}.$ (2.14)

Under the above notations, we have

Theorem 3. For any column vectors $f\in Z^n$ and $g\in Z^n$, then ${\Lambda }_q\left(A\right)$ is a convolutional modular lattice, and $\left(\begin{array}{c}f\\ g\end{array}\right)\in {\Lambda }_q\left(A\right)$.

Proof: It is known that ${\Lambda }_q\left(A\right)$ is a $q$ -ary lattice, i.e.

$q{Z}^{2n}\subset {\Lambda }_q\left(A\right)\subset Z^{2n}.$

We only prove that ${\Lambda }_q\left(A\right)$ is fixed under the linear transformation $\sigma$ given by (2.4). If $y\in {\Lambda }_q\left(A\right)$, then $y\equiv A^{\prime }x\left(\mathrm{mod}q\right)$ for some $x\in Z^n$, by lemma 2.1, we have

$\sigma \left(y\right)\equiv \left(\begin{array}{c}H{H}^{*}\left(f\right)x\\ H{H}^{*}\left(g\right)x\end{array}\right)=\left(\begin{array}{c}{H}^{*}\left(f\right)Hx\\ H^{*}\left(g\right)Hx\end{array}\right)\equiv A^{\prime }Hx\left(\mathrm{mod}q\right).$

It means that $\sigma \left(y\right)\in {\Lambda }_q\left(A\right)$ whenever $y\in {\Lambda }_q\left(A\right)$. Let

$e=\left(\begin{array}{c}1\\ 0\\ ⋮\\ 0\end{array}\right)\in Z^n\Rightarrow H^{*}\left(f\right)e=f,\text{and}{H}^{*}\left(g\right)e=g.$

We have $\left(\begin{array}{c}f\\ q\end{array}\right)\in {\Lambda }_q\left(A\right)$, and Theorem 3 follows. $\square$

Since ${\Lambda }_q\left(A\right)\subset Z^{2n}$, then there is a unique Hermite Normal Form of basis $N$, which is an upper triangular matrix given by

$N=\left(\begin{array}{cc}{I}_n& H^{*}\left(h\right)\\ 0& q{I}_n\end{array}\right),\text{where}h\equiv {\left(H^{*}\left(f\right)\right)}^{-1}g\left(\mathrm{mod}q\right).$ (2.15)

Next, we consider parameters system of NTRU. To choose the parameters of NTRU, let $d_f$ be a positive integer and ${\left\{p,0,-p\right\}}^n\subset Z^n$ be a subset of $Z^n$, of which has exactly $d_f+1$ positive entries and $d_f$ negative ones, the remaining $n-2d_f-1$ entries will be zero. We take some assumption conditions for choice of parameters as follows:

(i) $\varphi \left(x\right)=x^n-a_{n-1}{x}^{n-1}-\cdots -a_{1}x-a_0\in Z\left[x\right]$ with $a_0\ne 0$, and $\varphi \left(x\right)$ is separable polynomial, $n,p,q,d_f$ are positive integers with $n$ prime, $1<p<q$ and gcd $\left(p,q\right)=1$.

(ii) $f\left(x\right)$ and $g\left(x\right)$ are two polynomials in $Z\left[x\right]$ of degree $n-1$, the constant term of $f\left(x\right)$ is 1, and

$f\left(x\right)-1\in {\left\{p,0,-p\right\}}^n,g\in {\left\{p,0,-p\right\}}^n.$

(iii) $H^{*}\left(f\right)$ is invertible modulo $q$.

(iv) $d_f<\left(\frac{q}{2}-1\right)/4p-\frac{1}{2}$.

Under the above conditions, by lemma 2.2 we have

$H^{*}\left(f\right)\equiv I_n\left(\mathrm{mod}p\right),\text{and}{H}^{*}\left(g\right)\equiv 0\left(\mathrm{mod}p\right).$ (2.16)

Now, we state a generalization of NTRU as follows.

· Private key. The private key in generalized NTRU is a short vector $\left(\begin{array}{c}f\\ q\end{array}\right)\in Z^{2n}$. The lattice associated with a private key is ${\Lambda }_q\left(A\right)$, which is a convolutional modular lattice containing private key.

· Public key. The public key of the generalized NTRU is the HNF basis $N$ of ${\Lambda }_q\left(A\right)$, which is given by (2.15).

· Encryption. An input message is encoded as a vector $m\in {\left\{1,0,-1\right\}}^n$ with exactly $d_f+1$ positive entries and $d_f$ negative ones. Here the reason for restricting $d_f+1$ positive and $d_f$ negative entries of vector $m$ is to improve the efficiency of encryption and decryption and it’s not necessary. The vector $m$ is concatenated with a randomly chosen vector $r\in {\left\{1,0,-1\right\}}^n$ also with exactly $d_f+1$ positive entries and $d_f$ negative ones, to obtain a short error vector $\left(\begin{array}{c}m\\ r\end{array}\right)\in {\left\{1,0,-1\right\}}^{2n}$. Let

$\left(\begin{array}{c}c\\ 0\end{array}\right)=N\left(\begin{array}{c}m\\ r\end{array}\right)\equiv \left(\begin{array}{c}m+H^{*}\left(h\right)r\\ 0\end{array}\right)\left(\mathrm{mod}q\right),$ (2.17)

where $h$ is given by (2.15). Then, the $n$ -dimensional vector $c$

$c\equiv m+H^{*}\left(h\right)r\left(\mathrm{mod}q\right),$

is the ciphertext.

· Decryption. Suppose the entries of $n$ -dimensional vector $c$ are belong to interval $\left[-\frac{q}{2},\frac{q}{2}\right]$, then ciphertext $c$ is decrypted by multiplying it by the secret matrix $H^{*}\left(f\right)$ mod $q$, it follows that

$H^{*}\left(f\right)c\equiv H^{*}\left(f\right)m+H^{*}\left(f\right)H^{*}\left(h\right)r\equiv H^{*}\left(f\right)m+H^{*}\left(g\right)r\left(\mathrm{mod}q\right).$ (2.18)

Here, we use the identity (ii) of Theorem 2, namely,

$H^{*}\left(f\right)H^{*}\left(g\right)=H^{*}\left(H^{*}\left(f\right)g\right).$

If the above conditions (iv) is satisfied, it is easily seen that the coordinates of vector $H^{*}\left(f\right)m+H^{*}\left(g\right)r$ are all bounded by $\frac{q}{2}$ in absolute value, or, with high probability, even for larger value of $d_f$. The decryption process is completed by reducing (2.18) modulo $p$, to obtain

$H^{*}\left(f\right)m+H^{*}\left(g\right)r\equiv m{I}_n\left(\mathrm{mod}p\right).$

Thus one gets plaintext $m$ from ciphertext $c$.

Example 2. Let $n=3$, $p=3$, $q=7$, $\varphi \left(x\right)=x^3+x^2+x+1$, $f\left(x\right)=3x^2+1$, $g\left(x\right)=3x^2$, i.e. the private key is $\left(\begin{array}{c}f\\ g\end{array}\right)$ with $f=\left(\begin{array}{c}1\\ 0\\ 3\end{array}\right)$, $g=\left(\begin{array}{c}0\\ 0\\ 3\end{array}\right)$. It is easy to get

$H^{*}\left(f\right)=\left(\begin{array}{ccc}1& -3& 3\\ 0& -2& 0\\ 3& -3& 1\end{array}\right),\text{and}{H}^{*}\left(g\right)=\left(\begin{array}{ccc}0& -3& 3\\ 0& -3& 0\\ 3& -3& 0\end{array}\right).$

By (2.15), we compute the public key $N$ as follows

$h=\left(\begin{array}{c}2\\ 0\\ -3\end{array}\right),H^{*}\left(h\right)=\left(\begin{array}{ccc}2& 3& -3\\ 0& 5& 0\\ -3& 3& 2\end{array}\right),\text{and}N=\left(\begin{array}{cc}{I}_3& H^{*}\left(h\right)\\ 0& 7I_3\end{array}\right).$

Assume the input message $m=\left(\begin{array}{c}1\\ 0\\ 0\end{array}\right)$, random vector $r=\left(\begin{array}{c}0\\ 1\\ 0\end{array}\right)$, by (2.17) we get the ciphertext

$c\equiv m+H^{*}\left(h\right)r\equiv \left(\begin{array}{c}-3\\ -2\\ 3\end{array}\right)\left(\mathrm{mod}7\right).$

By (2.18), we have

$H^{*}\left(f\right)c\equiv \left(\begin{array}{c}-2\\ -3\\ 0\end{array}\right)\left(\mathrm{mod}7\right).$

Since

$\left(\begin{array}{c}-2\\ -3\\ 0\end{array}\right)\equiv \left(\begin{array}{c}1\\ 0\\ 0\end{array}\right)\left(\mathrm{mod}3\right),$

one can get the plaintext $m=\left(\begin{array}{c}1\\ 0\\ 0\end{array}\right)$ from ciphertext $c$.

4. Conclusion

In this study, we first discuss a more general form of the ordinary cyclic code, namely $\varphi$ -cyclic code. Then we give a generalized construction of NTRU based on ideal matrix and q-ary lattice theory. Compared with other variations of NTRU, such as CTRU, GNTRU, QTRU and BITRU, our extended NTRU cryptosystem is constructed with general ideal matrix rather than some special algebraic structures. Our purpose is to apply post quantum cryptography in distributed scenarios of blockchain future.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Lopez-Permouth, S.R., Parra-Avila, B.R. and Szabo, S. (2009) Dual Generalizations of the Concept of Cyclicity of Codes. Advances in Mathematics of Communications, 3, 227-234. https://doi.org/10.3934/amc.2009.3.227
[2]	Shi, M., Li, X., Sepasdar, Z. and Solé, P. (2020) Polycyclic Codes as Invariant Subspaces. Finite Fields and Their Applications, 68, Article ID: 101760. https://doi.org/10.1016/j.ffa.2020.101760
[3]	Lint, J.H.V. (1999) Introduction to Coding Theory. Volume 86 of GTM. Springer-Verlag, Berlin.
[4]	Bose, R.C. and Ray-Chaudhuri, D.K. (1960) On a Class of Error Correcting Binary Group Codes. Information and Control, 3, 68-79. https://doi.org/10.1016/S0019-9958(60)90287-4
[5]	Goppa, V.D. (1970) A New Class of Linear Error-Correcting Codes. Problemy Peredachi Informatsii, 6, 24-30.
[6]	Hoffstein, J., Pipher, J. and Silverman, J.H. (1998) NTRU: A Ring Based Public Key Cryptosystem. In: Buhler, J.P., Ed., Algorithmic Number Theory, Lecture Notes in Computer Science, Vol. 1423, Springer, Berlin, 267-288. https://doi.org/10.1007/BFb0054868
[7]	Gaborit, P., Ohler, J. and Soli, P. (2002) CTRU, a Polynomial Analogue of NTRU. Hal Inria, RR 4621.
[8]	Kouzmenko, R. (2006) Generalizations of the NTRU Cryptosystem. Diploma Project, Ecole Polytechnique Federale de Lausanne.
[9]	Coglianese, M. and Goi, B. (2005) MaTRU: A New NTRU Based Cryptosystem. Springer Verlag, Berlin, 232-243. https://doi.org/10.1007/11596219_19
[10]	Malecian, E., Zakerolhsooeini, A. and Mashatan, A. (2011) QTRU: A Lattice Attack Resistant Version of NTRU PCKS Based on Quaternion Algebra. The ISC Intrtnational Journal of Information Security, 3, 29-42.
[11]	Malecian, E. and Zakerolhsooeini, A. (2010) OTRU: A Non-Associative and High Speed Public Key Cryptosystem. IEEE 15th CSI International Symposium on Computer Architecture and Digital Systems (CADS), Tehran, 23-24 September 2010, 83-90. https://doi.org/10.1109/CADS.2010.5623536
[12]	Alsaidi, M.G. and Yassein R. (2016) BITRU: Binary Version of the NTRU Public Key Cryptosystem via Binary Algebra. International Journal of Advanced Computer Science & Applications, 7, 1-6. https://doi.org/10.14569/IJACSA.2016.071101
[13]	Lyubashevsky, V. and Micciancio, D. (2006) Generalized Compact Knapsacks Are Collision Resistant. In: Bugliesi, M., Preneel, B., Sassone, V. and Wegener, I., Eds., Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 4052, Springer, Berlin, 144-155. https://doi.org/10.1007/11787006_13
[14]	Micciancio, D. and Regev, O. (2009) Lattice-Based Cryptography. In: Bernstein, D.J., Buchmann, J. and Dahmen, E., Eds., Post-Quantum Cryptography, Springer Berlin, 147-191. https://doi.org/10.1007/978-3-540-88702-7_5
[15]	Lidl, R. and Niederreiter, H. (1983) Finite Fields. In: Doran, R., Ismail, M., Lam, T.-Y. and Lutwak, E., Eds., Encyclopedia of Mathematics and Its Applications, Vol. 20, Cambridge University Press, Cambridge.
[16]	IEEE Computer Society. (2000) IEEE Standard Specifications for Public-Key Cryptography. IEEE Std 1363-2000, 1-228.
[17]	Coppersmith, D. and Shamir A. (1997) Lattice Attacks on NTRU. In: Fumy, W., Ed., Advances in Cryptology, Lecture Notes in Computer Science, Vol. 1233, Springer, Berlin, 52-61. https://doi.org/10.1007/3-540-69053-0_5
[18]	Hoffstein, J., Pipher, J., Schanck, J.M., Silverman, J.H., Whyte, W. and Zhang, Z. (2017) Choosing Parameters for NTRUEncrypt. In: Handschuh, H., Ed., Topics in Cryptology, Lecture Notes in Computer Science, Vol. 10159, Springer, Berlin, 3-18. https://doi.org/10.1007/978-3-319-52153-4_1
[19]	McEliece, R.J. (1978) A Public-Key Cryptosystem Based on Algebraic Coding Theory. DSN Progress Report, Jet Propulsion Laboratory, Pasadena, 42-44.
[20]	Micciancio, D. (2001) Improving Lattice Based Cryptosystems Using the Hermite Normal Form. In: Silverman, J.H., Ed., Cryptography and Lattices, Lecture Notes in Computer Science, Vol. 2146, Springer, Berlin, 126-145. https://doi.org/10.1007/3-540-44670-2_11
[21]	Davis, P.J. (1994) Circulant Matrices. 2nd Edition, Chelsea Publishing, New York.
[22]	Ajtai, M. (1996) Generating Hard Instances of Lattice Problems. Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, 22-24 May 1996, 99-108. https://doi.org/10.1145/237814.237838
[23]	Ajtai, M. and Dwork, C. (1997) A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, 4-6 May 1997, 284-293. https://doi.org/10.1145/258533.258604
[24]	Niederreiter, H. (1986) Knapsack-Type Cryptosystems and Algebraic Coding Theory. Problems of Control and Information Theory, 15, 159-166.
[25]	Plantard T. and Schneider, M. (2013) Creating a Challenge for Ideal Lattices. IACR Cryptology ePrint Archive, 39, 1-17.
[26]	Pradhan, P.K., Rakshit, S. and Datta, S. (2019) Lattice Based Cryptography: Its Applications, Areas of Interest and Future Scope. Proceedings of the Third International Conference on Computing Methodologies and Communication, Erode, 27-29 March 2019, 988-993. https://doi.org/10.1109/ICCMC.2019.8819706