NTRU Over Galois Rings

Nth Truncated Polynomial Ring (NTRU) was first introduced by J. H. Silverman, J. Hoffstein and J. Piper as a public key system data encryption in 1996 [1]. In the later years, it has been consistently developed by the same team. Reports and articles have been published on titles such as fast key generation and organizing attacks to the secret key [?]. NTRU, which is a ring-based system, is an asymmetric encryption method.

Some researchers have analysed the system cryptologically. Some interesting results can be found in [2,3,4]. Variants of the system have been suggested in the advancing years. Generalized NTRU schemes from the first suggestions is a study that proposes using two pieces instead of one public key [5]. Another suggestion is on the necessity of building on a finite field of the system by publishing under the name of CTRU [6] in 2002. The study named as MATRU [7] was analysed in the case where the ring is matrices. NNRU is a suggestion on the necessity that the ring should not be commutative in 2009. Also, the systems QTRU (2009) on quaternions and OTRU (2010) on octonions were purposed. Finally, the study, so-called ETRU, was propounded by replacing the ring with the Eisenstein integers [8].

This article is organized as follows: in Section 2, we provide some basic information about NTRU. In Section 3, we provide some notations used in the article. In Section 4, we describe the NTRU cryptosystem. In Section 5, we introduce the Galois rings. In Section 6, we examine the NTRU system on the Galois rings; accordingly, we propose a new cryptosystem. In the next section, we proved how the system works on the Galois rings. Finally, we discuss the advantages of this system.

NTRU is established on the polynomial convolution ring R=Z[x]xN−1 R = \frac{Z [x]}{x^N -1} . A polynomial in the ring R has integer coefficients and is at most N − 1 order. A convolution product of any two polynomials f, g ∈ R is performed according to the following rule.

If f * g = h, then h_k = Σ_{i+j≡k(modN)} f_ig_j.

Before beginning, we inform about parameters of the system.

In the following section, we provide some notations used in the whole article.

To generate a NTRU key, we choose randomly f ∈ L_f and g ∈ L_g. In addition, the polynomial f is an invertible by mod p and mod q. If suitable parameters are chosen, then f will be quite likely invertible [9].

That is (1) fq−1⋆f≡1(mod q) and fp−1⋆f≡1(mod p). f_q^{ - 1} \star f \equiv 1\;\left( {mod\;q} \right) \mathrm{\; and\;} f_p^{ - 1} \star f\equiv 1\;\left( {mod\;p}\right).

If an integer p^k is replaced with modulo p in the classical NTRU processes, then we again obtain (p^k, q) = 1. If modulo is p^k, for prime number p and k ≥ 2 are chosen, the processes can be executed in the Galois ring as a result of choosing suitable parameters. Because the representation is uniform so that m = p₁^α₁ p₂^α₂ ... p_r^α_r for m ∈ Z if p₁^α₁ → p^k and p₁^α₁ p₂^α₂ ... p_r^α_r → q are substituted, Z_m [x] ≅ Z_p^k [x] × Z_q [x] so that it can be processed in an algebraic structure of the ring Z_p^k [x] due to (p₁^α₁, p₂^α₂ ... p_r^α_r) = 1.

Again, let the message polynomial m∈Zp[x]​​(xn−1) m \in {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$}\!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} in the classical NTRU protocol be changed to m∈Zpk[x]​​(xn−1) h\equiv pf_q^{ - 1} \star g\;\left( {mod\;q} \right) , and let the public key h≡pfq−1⋆g(mod q) h \equiv{p^k}f_q^{ - 1} \star g\;\left( {mod\;q} \right) be transformed to h≡pkfq−1⋆g(mod q) e \equiv r \star {p^k}f_q^{ - 1}\star g + m\;\left( {mod\;q} \right) . The statement e ≡ r ⋆ h+m (mod q) becomes e≡r⋆pkfq−1⋆g+m(mod q) e \star f \equiv r \star {p^k}f_q^{ - 1}\star f \star g + f \star m\;\left( {mod\;q} \right) . e⋆f≡r⋆pkfq−1⋆f⋆g+f⋆m(mod q) e \star f \equiv r\star {p^k} \star g + f \star m\;\left( {mod\;q} \right) and e ⋆ f ≡ r ⋆ p^k ⋆ g + f ⋆ m (mod q). Because p^k → ∞ if k → ∞, it is preserved as e⋆f≡f⋆m(modpk) e \star f \equiv f \star m\;\left( {mod\;{p^k}} \right) e⋆f⋆fpk−1≡m(modpk)e=m \matrix{e \star f \star f_{{p^k}}^{ - 1} \equiv m\;\left( {mod\;{p^k}} \right) \cr e = m} if the number k is chosen as large as desired and the statement f ⋆ m (mod q) becomes f ⋆ m mod p^k indicates that the coefficients of polynomial f ⋆ m are not reduced by mod p^k.

Since (p^k, q) = 1 for each p, q that provides the condition (p, q) = 1 being the parameter of system, it can transform the classical parameter in the case k = 1. In response to the chosen number k, f^k is substituted instead of the polynomial f being a secret key. If (f^k)⁻¹ = (f⁻¹)^k, then the system becomes h≡(pfq−1)k⋆g(mod q) h \equiv {(pf_q^{ - 1})^k} \star g\;\left( {mod\;q} \right) where h≡pk(fq−1)k⋆g(mod q) h \equiv{p^k}{(f_q^{ - 1})^k} \star g\;\left( {mod\;q} \right) . The statement e ≡ r ⋆ h + m (mod q) becomes e≡r⋆pk(fq−1)k⋆g+m(mod q)e⋆fk≡r⋆pk⋆g+m⋆fk(mod q)e⋆fk⋆(fpk−1)k≡r⋆pk⋆g⋆(fpk−1)k+m(modpk)≡0+m(modpk)e≡m(modpk) \matrix{e \equiv r \star {p^k}{(f_q^{ - 1})^k} \star g\; + m\;\left( {mod\;q} \right)\cr e \star {f^k}{\rm{\;}} \equiv r \star {p^k} \star g\; + m \star {f^k}\;\left({mod\;q} \right)\cr e \star {f^k} \star {(f_{{p^k}}^{ - 1})^k}{\rm{\;}} \equiv r \star {p^k} \star g\star {(f_{{p^k}}^{ - 1})^k}\; + m\;\left( {mod\;{p^k}} \right)\cr \equiv 0\; + m\;\left( {mod\;{p^k}} \right)\cr e \equiv m\;\left( {mod\;{p^k}} \right)}

e = m, and if the order of secret key in the multiplicative group is chosen large, it can present a different encryption protocol. The polynomial f may be chosen as a generator polynomial.

An another choosing of key could be getting new keys in the form of f ⋆ xⁱ for 1 ≤ i ≤ n − 1 by applying rotations to a secret key f.

Since f ⋆ xⁿ = f ⋆ 1 = f, this rotation should be finished in n − 1 steps. Then, the polynomial h≡pfq−1⋆g(mod q) h \equiv pf_q^{ - 1} \star g\;\left( {mod\;q}\right) , that is a public key, becomes h≡pk(fq−1)k⋆g⋆xn−i(mod q) h \equiv {p^k}{(f_q^{ - 1})^k} \star g \star {x^{n - i}}\;\left( {mod\;q} \right) . e≡r⋆h+m(mod q)≡r⋆pk(fq−1)k⋆g⋆xn−i+m(mod q)⋮e⋆fk⋆xi≡r⋆pk⋆g+fk⋆m⋆xi(mod q)≡fk⋆m⋆xi(modpk)e⋆fk⋆(fpk−1)k⋆xi⋆xn−i≡m(modpk)e≡m(modpk)e=m \matrix{e \equiv r \star h + m\;\left( {mod\;q} \right) \cr \equiv r \star {p^k}{(f_q^{ - 1})^k} \star g \star {x^{n - i}} + m\;\left({mod\;q} \right) \cr \vdots \cr e \star {f^k} \star {x^i}{\rm{\;}} \equiv r \star {p^k} \star g\; + {f^k} \star m \star {x^i}\;\left( {mod\;q} \right) \cr \equiv {f^k} \star m \star {x^i}\;\left( {mod\;{p^k}} \right) \cr e \star {f^k} \star {(f_{{p^k}}^{ - 1})^k} \star {x^i} \star {x^{n - i}}{\rm{\;}} \equiv m\;\left( {mod\;{p^k}} \right) \cr e \equiv m\;\left( {mod\;{p^k}} \right) \cr e = m} so that the ith rotation of secret key acts also as a secret key.

Consequently, the numbers p ve q do not choose too small so that (p, q) = 1 in the classical key protocol, they may be enlarged as desired, and it is predicted that the calculations can make in the larger rings. Since every power of a polynomial f is also invertible when it is an invertible, it is foreseen that the invertible generator polynomials contribute to NTRU. Because the statement f ⋆ g ≡ h (mod q) holds, that is, the statement f ⋆ g ⋆ xⁱ h ⋆ xⁱ (mod q) holds for each 0 ≤ i ≤ n, it is predicted that regarding a wide range of rotations of the private key has also a securty-building effect. (10) Zpk[x]​​(xn−1)≅Zpk[x]​​(x−1)×Zpk[x]​​(xn−1+xn−2+…+1) {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} \cong{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - 1} \right)}$}} \times{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^{n - 1}} + {x^{n - 2}} + \ldots + 1} \right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^{n - 1}} + {x^{n - 2}} + \ldots + 1}\right)}$}} where (n, p) = 1. If a prime number q is chosen so that (p, q) = 1 is substituted instead of n, the cyclotomic polynomial Φ_q (x) = x^q−1 + x^q−2 + ... + x + 1 of qth order is obtained. This polynomial is irreducible in Z but all its roots are discrete in a suitably chosen ring Z_p^k. If the polynomial Φ_q (x) is irreducible in Z_p, then it is also irreducible in Z_p^k. Then Zpk[x]​​(xq−1+xq−2+…+x+1) {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x\right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^{q - 1}} + {x^{q - 2}} + \ldots + x + 1} \right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^{q - 1}} + {x^{q - 2}} + \ldots + x + 1}\right)}$}} becomes a Galois ring. By Zpk[x]​(x−1)≅Zpk {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x\right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - 1} \right)}$}} \cong {Z_{{p^k}}} and the fact that Z_p^k is also a Galois ring, the ring Zpk[x]​(xn−1) {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} is written as a direct product of Galois rings in the case that n is the prime q and (q, p) = 1. At this stage, a homomorphism ϕ can be found by defining in the following form φ:Zpk[x]​​(xn−1)→Zpk[x]​(x−1)×Zpk[x]​​(Φq(x))φ(f)→(f(1),fmodΦq(x)). \matrix{\varphi :{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} \to{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - 1} \right)}$}} \times{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{\Phi _q}\left( x \right)}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{\Phi _q}\left( x \right)} \right)}$}}\cr \varphi \left( f \right) \to \left( {f\left( 1 \right),\;f\;mod\;{\Phi _q}\left(x \right)} \right).}

When we look for an invertible f for NTRU, the conditions f (1) ≠ = 0 and f mod Φ_q (x) = 0 should be provided. An another case is to construct the ring Z_p^k containing all roots of the polynomial Φ_q (x) = x^q−1 + x^q−2 + ... + x + 1. For p^k ∈ Z satisfying these conditions, it can be written Φq(1)=(x−α1)(x−α2)…(x−αq−1) {\Phi _q}\left( 1 \right) = \left( {x - {\alpha _1}} \right)\left( {x - {\alpha_2}} \right) \ldots \left( {x - {\alpha _{q - 1}}} \right) where α_i ∈ Z_p^k, 1 ≤ i ≤ q − 1. Since α_i ≠ α_j, 1 ≤ i, j ≤ q − 1, (x − α_i, x − α_j) = 1 and (11) Zpk[x]​(Φq(x))≅Zpk[x]​​(x−α1)×Zpk[x]​(x−α2)×…×Zpk[x]​​(x−αq−1). {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{\Phi _q}\left( x \right)}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{\Phi _q}\left( x \right)} \right)}$}} \cong{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - {\alpha _1}}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - {\alpha _1}} \right)}$}} \times{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - {\alpha _2}}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - {\alpha _2}} \right)}$}} \times \ldots \times{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - {\alpha _{q - 1}}}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - {\alpha _{q - 1}}}\right)}$}}.

Then (12) Zpk[x]​​(xn−1)≅Zpk[x]​​(x−1)×Zpk[x]​(x−α1)×…×Zpk[x]​​(x−αq−1) {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} \cong{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - 1} \right)}$}} \times{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - {\alpha _1}}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - {\alpha _1}} \right)}$}} \times \ldots \times{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - {\alpha _{q - 1}}}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - {\alpha _{q - 1}}}\right)}$}} and a homomorphism ϕ may be defined as φ:Zpk[x]​​(xn−1)→Zpk[x]​​(x−1)×Zpk[x]​​(x−α1)×…×Zpk[x]​​(x−αq−1)φ(f)→(f(1),f(α1),f(α2),…,f(αq−1)). \matrix{\varphi :{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} \to{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - 1} \right)}$}} \times{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - {\alpha _1}}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - {\alpha _1}} \right)}$}} \times \ldots \times{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {x - {\alpha _{q - 1}}}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {x - {\alpha _{q - 1}}} \right)}$}} \cr \varphi \left( f \right) \to \left( {f\left( 1 \right),\;f\left( {{\alpha _1}}\right),\;f\left( {{\alpha _2}} \right),\; \ldots ,\;f\left( {{\alpha _{q - 1}}}\right)} \right).}

If the polynomials ϕ (f) compute by mod p^k, that is, the images under canonical homomorphism φ¯(f)→(f(1),f(α1),f(α2),…,f(αq−1))modpk \bar \varphi \left( f \right) \to \left({f\left( 1 \right),\;f\left( {{\alpha _1}} \right),\;f\left( {{\alpha _2}}\right),\; \ldots ,\;f\left( {{\alpha _{q - 1}}} \right)} \right)mod\;{p^k} are taken, it can be treated as φ¯(f)∈Zpk[x] \bar \varphi \left( f \right) \in {Z_{{p^k}}}\left[x \right] .

An invertible polynomial f∈Zpk[x]​​(xn−1) f \in {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x\right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} is in the form of f = β + ps (x), f=β+ps(x),s(x)∈Zpk[x]​​(xn−1) f =\beta + ps\left( x \right),\;s\left( x \right) \in{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} and (β, p_k)= 1. ϕ (f), which is an isomorphic image of chosen polynomial f in this form, is invertible. If we write a number m ∈ Z⁺ as m=p1s1pkp2s2…pisiq m = \mathop {\mathop {{p_1}^{{s_1}}} }\limits_{{p^k}}\mathop {\mathop {{p_2}^{{s_2}} \ldots {p_i}^{{s_i}}} }\limits_q in a canonical form, Zm[x]​​(xn−1)≅Zpk[x]​(xn−1)×Zq[x]​​(xn−1) {\raise0.7ex\hbox{${{Z_m}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_m}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} \cong{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} \times{\raise0.7ex\hbox{${{Z_q}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_q}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} and because m → ∞ for p^k → ∞ and q → ∞, to examine an algebraic structure of the ring NTRU coverging to infinite as a direct product of Galois rings is beneficial.

As a result of all these evidences, we can add an isomorphism ϕ to a NTRU process as a secret key. Let h=fq−1⋆g(mod q) h = f_q^{ - 1} \star g\;\left( {mod\;q}\right) be a public key where f∈Zpk[x](xn−1) f \in {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x\right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} and g∈Zq[x]​(xn−1) g \in{\raise0.7ex\hbox{${{Z_q}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_q}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} . Let m∈Zpk[x]​(xn−1) m \in{\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} and an error polynomial r (x) be arbitrarily chosen. Let the message be hidden as e≡pkr⋆fq−1⋆g+φ(m)(mod q) e \equiv{p^k}r \star f_q^{ - 1} \star g\; + \varphi \left( m \right)\;\left( {mod\;q}\right) . e⋆f≡pkr⋆g+f⋆φ(m)(mod q)≡f⋆φ(m)(modpk) e \star f \equiv {p^k}r \star g\; + f \star \varphi \left( m \right)\left({mod\;q} \right)\equiv f \star \varphi \left( m \right)\left( {mod\;{p^k}} \right) (let a suitable parameter k be chosen). e⋆f⋆fpk−1≡φ(m)(modpk)e≡φ(m)(modpk)(e∈Zpk[x]​(xn−1))φ−1(e)≡m(modpk). \matrix{e \star f \star {f_{{p^k}}}^{ - 1} \equiv \varphi \left( m \right)\left({mod\;{p^k}} \right) \cr e \equiv \varphi \left( m \right)\left( {mod\;{p^k}} \right) \cr \left( {e \in {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$}\!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}}} \right) \cr {\varphi ^{ - 1}}\left( e \right) \equiv m\;\left( {mod\;{p^k}} \right).}

Now we provide a lemma that specifies the choosing of private key polynomial f for the NTRU system moving into Galois rings.

By transforming the set of chosen invertible polynomial Zpk[x]​​(xn−1) {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} , a greater number of private key generation is aimed to be given. Also, by exponentiating the specified kth power of private key polynomials g and f in the statement f ⋆ h = g, the public key h is made slightly more complex. By substituting h⋆xk=fq−1⋆g⋆xk h \star {x^k} = f_q^{ - 1} \star g \star {x^k} instead of h=fq−1⋆g h = f_q^{ - 1} \star g , an appropriate kth rotation of public key is chosen. Since Z_m ≅ Z_p^α × Z_q^β for m ∈ Z so that m = p^αq^β, (p, q) = 1, a homomorphism ϕ is defined by φ:Zm→Zpα×Zqβφ(f)=(fmodpα,fmodqβ) \matrix{\varphi :{Z_m} \to {Z_{{p^\alpha }}} \times {Z_{{q^\beta }}} \cr \varphi \left( f \right) = \left( {f\;\;mod\;{p^\alpha },\;f\;\;mod\;{q^\beta }}\right)} and it is applied to the chosen message polynomial. The inverse of isomorphism ϕ is added to the secret key set. By taking the message polynomials m from the ring Zpk[x]​​(xn−1) {\raise0.7ex\hbox{${{Z_{{p^k}}}\left[ x \right]}$}\!\mathord{\left/{\vphantom {{{Z_{{p^k}}}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} instead of Zp[x]​(xn−1) {\raise0.7ex\hbox{${{Z_p}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_p}\left[ x \right]} {\left( {{x^n} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^n} - 1} \right)}$}} , the further sets of concealable polynomial are obtained. It is suggested that the processes executing in the fields Z_p ve Z_q of classical NTRU system perform in the Galois rings Z_p^k ve Z_q^r. Because p^α → ∞ for α → ∞ and m → ∞, it is predicted that the modulos p ve q can be chosen as large as desired from the public keys.