1. bookVolume 6 (2021): Issue 1 (January 2021)
Journal Details
License
Format
Journal
First Published
01 Jan 2016
Publication timeframe
2 times per year
Languages
English
access type Open Access

NTRU Over Galois Rings

Published Online: 30 Oct 2020
Page range: 499 - 506
Received: 26 Jul 2019
Accepted: 19 Sep 2019
Journal Details
License
Format
Journal
First Published
01 Jan 2016
Publication timeframe
2 times per year
Languages
English
Abstract

As a cryptosystem, Nth Truncated Polynomial Ring (NTRU) is established on the fast and easy calculation. Improving the security is aimed by enlarging a ring where the processes execute and enhancing the number of a private key and a public key. In this study, NTRU takes over the Galois rings and is analysed by adding a new private key.

Keywords

MSC 2010

Introduction

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 cryptosystem

NTRU is established on the polynomial convolution ring R=Z[x]xN1 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, gR is performed according to the following rule.

f=i=0N1fixi=(f0,f1,,fN1) f = \sum_{i=0}^{N-1} f_i x^i= (f_0,f_1,\ldots, f_{N-1}) g=j=0N1gjxj=(g0,g1,,gN1) g = \sum_{j=0}^{N-1} g_j x^j = (g_0,g_1,\ldots, g_{N-1})

If f * g = h, then hk = Σi+jk(modN) figj.

Before beginning, we inform about parameters of the system.

N – size parameter

Large modulo q

Small modulo p

A polynomial f indicates that the inverses according to mod p and modq are available

A polynomial g indicates that it does not need to be invertible

Error polynomial r

Message polynomial m

df : a distribution of coefficients of the polynomial f

dg: a distribution of coefficients of the polynomial g

dr: the number of 1 s and −1 s in coefficients of the specified polynomial

Lf : polynomials in ℤ[x]/(xN − 1) whose coefficients provide d f

Lg: polynomials in ℤ[x]/(xN − 1) whose coefficients provide dg

Lr: polynomials in Z[x]/(xN − 1) whose coefficients provide dr.

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

Using Notations

f is a polynomial in Z[x](xN1) {\raise0.7ex\hbox{${Z\left[ x \right]}$}\!\mathord{\left/{\vphantom {{Z\left[ x \right]} {\left( {{x^N} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{x^N} - 1} \right)}$}} ,

fp is a reduced form of f by mod p (secret key) in Z[x](p,xN1) {\raise0.7ex\hbox{${Z\left[ x \right]}$} \!\mathord{\left/{\vphantom {{Z\left[ x \right]} {\left( {p,\;{x^N} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {p,\;{x^N} - 1} \right)}$}} ,

fq is a polynomial whose coefficients reduced by mod q in Z[x](q,xN1) {\raise0.7ex\hbox{${Z\left[ x \right]}$} \!\mathord{\left/{\vphantom {{Z\left[ x \right]} {\left( {q,\;{x^N} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {q,\;{x^N} - 1} \right)}$}} ,

g is a polynomial in Z[x](q,xN1) {\raise0.7ex\hbox{${Z\left[ x \right]}$}\!\mathord{\left/{\vphantom {{Z\left[ x \right]} {\left( {q,\;{x^N} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {q,\;{x^N} - 1} \right)}$}} (it constitutes the public key with fq),

fp−1 is the inverse of fp in the ring,

fq−1 is the inverse of in the ring Z[x](q,xN1) {\raise0.7ex\hbox{${Z\left[ x\right]}$} \!\mathord{\left/{\vphantom {{Z\left[ x \right]} {\left( {q,\;{x^N} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {q,\;{x^N} - 1} \right)}$}} , and

an encoded message e is a polynomial in Z[x](p,xN1) {\raise0.7ex\hbox{${Z\left[ x\right]}$} \!\mathord{\left/{\vphantom {{Z\left[ x \right]} {\left( {p,\;{x^N} - 1}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {p,\;{x^N} - 1} \right)}$}} .

Key Generation

To generate a NTRU key, we choose randomly fLf and gLg. 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 fq1f1(modq)andfp1f1(modp). f_q^{ - 1} \star f \equiv 1\;\left( {mod\;q} \right) \mathrm{\; and\;} f_p^{ - 1} \star f\equiv 1\;\left( {mod\;p}\right).

Encryption

hpfq1g(modq) h \equiv pf_q^{ - 1} \star g\;\left( {mod\;q}\right) is the public key.

The message m is encoded with the secret keys such as f, fp1 f_p^{ - 1} and the public key h by computing erh+m(modq). e \equiv r \star h + m\;\left( {mod\;q}\right).

Decryption

The cipher message is decoded in the following form afe(modq) a \equiv f \star e\;\left( {mod\;q}\right) by using the secret key. At this stage, it is checked whether the coefficients of a are in an interval (q2,q2] \left( { - \frac{q}{2},\;\frac{q}{2}} \right] . The process is finished by computing c=fp1a(modp). c = f_p^{ - 1} \star a\;\left( {mod\;p}\right).

To work decoding correctly, the absolute values of coefficients of a polynomial prg + fm should not exceed q2 a = f \star e\;\left( {mod\;q} \right) = f \star \left( {r \star h + m}\right)\;\left( {modq} \right) = f\star r \star h + f \star m\;\left( {mod\;q}\right) . Also, it may be supposed that a reduction cannot be done by mod q since large coefficients are chosen [10].

Why the decryption works?

Mathematically, since a=fe(modq)=f(rh+m)(modq)=frh+fm(modq) h \equiv pf_q^{ - 1} \star g, hpfq1g, a = \left[ {\left( {f \star r \star \left( {pf_q^{ - 1} \star g} \right)} \right) + \left( {f \star m} \right)}\right]mod\;q a=[(fr(pfq1g))+(fm)]modq a = \left[ {\left( {pr \star g} \right) + \left( {f \star m} \right)}\right]\;mod\;q and a=[(prg)+(fm)]modq f_q^{ - 1} \star f \equiv 1\;\left( {mod\;q} \right). because fq1f1(modq). c = f_p^{ - 1} \star a\;\left( {mod\;p} \right) = p\left( {f_q^{ - 1} \star r\star g} \right) + \left( {f_p^{ - 1} \star f \star m} \right)\;\left( {mod\;p}\right) = 0 + \left( {1 \star m} \right) = m\;\left( {mod\;p} \right) c=fp1a(modp)=p(fq1rg)+(fp1fm)(modp)=0+(1m)=m(modp) GR\left( {p,\;r} \right) = GF\left( {{p^r}} \right) = {F_{{p^r}}} so that the message m is found correctly.

As can be seen, the coefficients of these polynomials are chosen small because a convolution product of two n-order polynomials, namely f and g in the ring NTRU, necessitates n2 processes. In previous studies, choosing an invertible polynomial f is done in the form of f = 1 + pF where F is an arbitrary polynomial because f mod p ≡ 1 and its inverse are easily computable. The statement in Equation (8) is properly chosen in terms of mod q. Thus, we say that NTRU grounds on speed and processing easily. It also gives the security flaws inherently. NTRU processes are executed in Zp [x] ve Zq [x] [11]. Moving the system into a larger set contributes to the system. It is clear that Zpk [x] is a larger set. Also, it is a special type of Galois rings. Proposed new parameters and private keys are selected from this ring.

NTRU over Galois ringsAlgebraic structure of Galois rings

Galois rings are obtained from Galois extensions of a ring, and they are denoted by GR(pn, r) where p is a prime number, n and r are positive integers. Some explicit examples are as follows:

If n = 1, then we find an extension r of the field ZpFp. GR(p,r)=GF(pr)=Fpr {\raise0.7ex\hbox{${{Z_{{p^n}}}\left[ x \right]}$} \!\mathord{\left/{\vphantom {{{Z_{{p^n}}}\left[ x \right]} {\left( {f\left( x \right)}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {f\left( x \right)} \right)}$}}

If r = 1, then GR(pn, 1) = Zpn

The Galois rings GR(pn, 1) are isomorphic to the quotient ring Zpn[x](f(x)) GR\left( {{p^n},\;r} \right) \cong{\raise0.7ex\hbox{${Z\left[ x \right]}$} \!\mathord{\left/{\vphantom {{Z\left[ x \right]} {\left( {{p^n},\;f\left( x \right)}\right)}}}\right.}\!\lower0.7ex\hbox{${\left( {{p^n},\;f\left( x \right)} \right)}$}} . f (x) ∈ Zpn [x] is a monic, basic irreducible polynomial. Equally, if f (x) ∈ Z [x] is chosen a r th-order monic, irreducible by mod p, then GR(pn,r)Z[x](pn,f(x)) \mu \left( f \right) = 0. . This ring is local, and its single maximal ideal is pGR(pn, r).

Moreover, all the ideals of this ring are principal ideals, and it is in the following form: (pi) = piGR(pn, r) 0 ≤ in [11].

Lemma 1

[12] ZmZp1ei × Zp2ei × ... × Zpnei where m = Π piei, ei ≥ 1, pi are distinct prime numbers. The mapping gives isomorphism in the form of ϕ : i → (a1, a2, ..., as), iZm and iaj (mod pjej), j = 1, 2, ..., s.

When mpn, Zm is not a local ring or a chain ring, but it is a semi-local ring because it is written in the form of a direct product of local rings. Note that all the non-unitary elements of Zpn are nilpotent, and so it belongs to the class of Artin rings. Zm does not have such a structure for mpn.

Proposition 1

[12] Let f (x) = a0 + a1x + ... + anxn be a polynomial in Zpk [x]. The following conditions are equivalent:

f is a unitary.

μ (f) is a unitary in Zp [x].

a0Zpk is a unitary, and a1, ..., an are nilpotent.

Proposition 2

[12] Let f (x) = a0 + a1x + ... + anxn be a polynomial in Zpk [x]. The following conditions are equivalent:

f is nilpotent. μ(f)=0. m \in {\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)}$}}

a0, a1, ..., an are nilpotent elements.

f is a zero-divisor.

The canonical homomorphism μ transforms a polynomial to Zp [x] by reducing the coefficients of a polynomial in Zpk [x] in terms of mod p.

The Proposed Cryptosystem

If an integer pk is replaced with modulo p in the classical NTRU processes, then we again obtain (pk, q) = 1. If modulo is pk, 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 = p1α1 p2α2 ... prαr for mZ if p1α1pk and p1α1 p2α2 ... prαrq are substituted, Zm [x] ≅ Zpk [x] × Zq [x] so that it can be processed in an algebraic structure of the ring Zpk [x] due to (p1α1, p2α2 ... prαr) = 1.

Again, let the message polynomial mZp[x](xn1) 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 mZpk[x](xn1) h\equiv pf_q^{ - 1} \star g\;\left( {mod\;q} \right) , and let the public key hpfq1g(modq) h \equiv{p^k}f_q^{ - 1} \star g\;\left( {mod\;q} \right) be transformed to hpkfq1g(modq) e \equiv r \star {p^k}f_q^{ - 1}\star g + m\;\left( {mod\;q} \right) . The statement erh+m (mod q) becomes erpkfq1g+m(modq) e \star f \equiv r \star {p^k}f_q^{ - 1}\star f \star g + f \star m\;\left( {mod\;q} \right) . efrpkfq1fg+fm(modq) e \star f \equiv r\star {p^k} \star g + f \star m\;\left( {mod\;q} \right) and efrpkg + fm (mod q). Because pk → ∞ if k → ∞, it is preserved as effm(modpk) e \star f \equiv f \star m\;\left( {mod\;{p^k}} \right) effpk1m(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 fm (mod q) becomes fm mod pk indicates that the coefficients of polynomial fm are not reduced by mod pk.

Since (pk, 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, fk is substituted instead of the polynomial f being a secret key. If (fk)−1 = (f−1)k, then the system becomes h(pfq1)kg(modq) h \equiv {(pf_q^{ - 1})^k} \star g\;\left( {mod\;q} \right) where hpk(fq1)kg(modq) h \equiv{p^k}{(f_q^{ - 1})^k} \star g\;\left( {mod\;q} \right) . The statement erh + m (mod q) becomes erpk(fq1)kg+m(modq)efkrpkg+mfk(modq)efk(fpk1)krpkg(fpk1)k+m(modpk)0+m(modpk)em(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 fxi for 1 ≤ in − 1 by applying rotations to a secret key f.

Since fxn = f ⋆ 1 = f, this rotation should be finished in n − 1 steps. Then, the polynomial hpfq1g(modq) h \equiv pf_q^{ - 1} \star g\;\left( {mod\;q}\right) , that is a public key, becomes hpk(fq1)kgxni(modq) h \equiv {p^k}{(f_q^{ - 1})^k} \star g \star {x^{n - i}}\;\left( {mod\;q} \right) . erh+m(modq)rpk(fq1)kgxni+m(modq)efkxirpkg+fkmxi(modq)fkmxi(modpk)efk(fpk1)kxixnim(modpk)em(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 fgh (mod q) holds, that is, the statement fgxi hxi (mod q) holds for each 0 ≤ in, it is predicted that regarding a wide range of rotations of the private key has also a securty-building effect. Zpk[x](xn1)Zpk[x](x1)×Zpk[x](xn1+xn2++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) = xq−1 + xq−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 Zpk. If the polynomial Φq (x) is irreducible in Zp, then it is also irreducible in Zpk. Then Zpk[x](xq1+xq2++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](x1)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 Zpk is also a Galois ring, the ring Zpk[x](xn1) {\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](xn1)Zpk[x](x1)×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 Zpk containing all roots of the polynomial Φq (x) = xq−1 + xq−2 + ... + x + 1. For pkZ satisfying these conditions, it can be written Φq(1)=(xα1)(xα2)(xαq1) {\Phi _q}\left( 1 \right) = \left( {x - {\alpha _1}} \right)\left( {x - {\alpha_2}} \right) \ldots \left( {x - {\alpha _{q - 1}}} \right) where αiZpk, 1 ≤ iq − 1. Since αiαj, 1 ≤ i, jq − 1, (xαi, xαj) = 1 and Zpk[x](Φq(x))Zpk[x](xα1)×Zpk[x](xα2)××Zpk[x](xαq1). {\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 Zpk[x](xn1)Zpk[x](x1)×Zpk[x](xα1)××Zpk[x](xαq1) {\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](xn1)Zpk[x](x1)×Zpk[x](xα1)××Zpk[x](xαq1)φ(f)(f(1),f(α1),f(α2),,f(αq1)). \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 pk, that is, the images under canonical homomorphism φ¯(f)(f(1),f(α1),f(α2),,f(αq1))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 fZpk[x](xn1) 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](xn1) 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 (β, pk)= 1. ϕ (f), which is an isomorphic image of chosen polynomial f in this form, is invertible. If we write a number mZ+ as m=p1s1pkp2s2pisiq 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](xn1)Zpk[x](xn1)×Zq[x](xn1) {\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 pk → ∞ 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=fq1g(modq) h = f_q^{ - 1} \star g\;\left( {mod\;q}\right) be a public key where fZpk[x](xn1) 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 gZq[x](xn1) 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 mZpk[x](xn1) 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 epkrfq1g+φ(m)(modq) e \equiv{p^k}r \star f_q^{ - 1} \star g\; + \varphi \left( m \right)\;\left( {mod\;q}\right) . efpkrg+fφ(m)(modq)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). effpk1φ(m)(modpk)eφ(m)(modpk)(eZpk[x](xn1))φ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).}

The Choosing of Private Key Polynomial F

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

Lemma 2

Let p ≥ 3 be a prime number and n ∈. If (f (x), p) = 1, then fp (x) ≡ 1 (mod pn+1) if and only if f (x) ≡ 1 (mod pn).

Proof

(⇐) Let f (x) ≡ 1 (mod pn). Then pn | f (x) − 1, in fact p | f (x) − 1 and it means that f (x) ≡ 1 (mod p). Thus, fp1(x)+fp2(x)++f(x)+11+1++1p0(modp), {f^{p - 1}}\left( x \right) + {f^{p - 2}}\left( x \right) + \ldots + f\left( x \right) + 1 \equiv 1 + 1 + \ldots + 1 \equiv p \equiv 0\;\left( {mod\;p}\right), i.e., p | fp−1 (x) + fp−2 (x) + ... + f (x) + 1. Hence pn+1|(f(x)1)(fp1(x)+fp2(x)++f(x)+1)=fp(x)1fp(x)1(modpn+1). {p^{n + 1}}\mid \left( {f\left( x \right) - 1} \right)\left( {{f^{p - 1}}\left(x \right) + {f^{p - 2}}\left( x \right) + \ldots + f\left( x \right) + 1}\right) = {f^p}\left( x \right) - 1 \Rightarrow {f^p}\left( x \right) \equiv 1\;\left( {mod\;{p^{n + 1}}} \right). (⇒) Let's prove it by mathematical induction over n. Assume that fp (x) ≡ 1 (mod p2) for n = 1. Then fp(x)=f(x).fp1(x)=f(x).(1+kp)1+lp2f(x)1(modp) {f^p}\left( x \right) = f\left( x \right).{f^{p - 1}}\left( x \right) = f\left(x \right).\left( {1 + kp} \right)1 + l{p^2} \Rightarrow f\left( x \right) \equiv1\;\left( {mod\;p} \right) and the claim is verified. Now, let the assumption be verified for n ∈. Suppose that f (x) ≡ 1 (mod pn+2). We obtain from the hypothesis that fp (x) ≡ 1 (mod pn+1) ⇔ f (x) ≡ 1 (mod pn). Since fp(x)=(1+kpn)p=1+pkpn+j=2p(pj)kjpnj=1+pkpn+lp2n+1+kppnp, \matrix{{f^p}\left( x \right) = {\left( {1 + k{p^n}} \right)^p} = 1 + pk{p^n} + \mathop\sum \limits_{j = 2}^p \left( {\begin{array}{*{20}{c}}p\\j\end{array}} \right){k^j}{p^{nj}}\cr = 1 + pk{p^n} + l{p^{2n + 1}} + {k^p}{p^{np}},} p|(pj) p\mid \left( {\begin{array}{*{20}{c}}p\\j\end{array}} \right) and 2n + 1 ≥ n + 2, npn + 2 (p ≥ 3) by writing f (x) = 1 + kpn, we obtain 1fp(x)1+kpn+1(modpn+2)pn+2|(1+kpn+1)1=kpn+1p|k. \matrix{1 \equiv {f^p}\left( x \right) \equiv 1 + k{p^{n + 1}}\;\;\left( {mod\;{p^{n +2}}} \right) \cr {p^{n + 2}}\mid \left( {1 + k{p^{n + 1}}} \right) - 1 = k{p^{n + 1}} \Rightarrow p\mid k.}

Because f (x) = 1 + kpn, it follows f (x) ≡ 1 (mod pn+1) and the proof given by mathematical induction.

The proposed NTRU scheme

Old New
public key Secret key public key Secret key
p, q, h, N f, fp1 f_p^{ - 1} , g pk, qt, h, N f, fpk1 f_{{p^k}}^{ - 1}
p = 3 f = 1 + pF p = 337 g,xk−1
q = 59 q = 5923 f = 88 + pF
N = 11 N = 113 ggk
h=fq1g h = f_q^{ - 1} \star g h=fqt1gk h = f_{{q^t}}^{ - 1} \star {g^k}
Discussion and Conclusion

By transforming the set of chosen invertible polynomial Zpk[x](xn1) {\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 fh = g, the public key h is made slightly more complex. By substituting hxk=fq1gxk h \star {x^k} = f_q^{ - 1} \star g \star {x^k} instead of h=fq1g h = f_q^{ - 1} \star g , an appropriate kth rotation of public key is chosen. Since ZmZpα × Zqβ for mZ so that m = pαqβ, (p, q) = 1, a homomorphism ϕ is defined by φ:ZmZpα×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](xn1) {\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](xn1) {\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 Zp ve Zq of classical NTRU system perform in the Galois rings Zpk ve Zqr. 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.

The proposed NTRU scheme

Old New
public key Secret key public key Secret key
p, q, h, N f, fp1 f_p^{ - 1} , g pk, qt, h, N f, fpk1 f_{{p^k}}^{ - 1}
p = 3 f = 1 + pF p = 337 g,xk−1
q = 59 q = 5923 f = 88 + pF
N = 11 N = 113 ggk
h=fq1g h = f_q^{ - 1} \star g h=fqt1gk h = f_{{q^t}}^{ - 1} \star {g^k}

Hoffstein, J., Pipher, J. and Silverman, J. H. (1996). NTRU: A new high speed public key cryptosystem. Crypto 96, preprint. Available at http://www.ntru.com/articles HoffsteinJ. PipherJ. SilvermanJ. H. 1996 NTRU: A new high speed public key cryptosystem Crypto 96 preprint. Available at http://www.ntru.com/articles Search in Google Scholar

Jaulmes, É. and Joux, A. (2000). A chosen-ciphertext attack against NTRU. Advances in Cryptology Conference-Crypto 2000. JaulmesÉ. JouxA. 2000 A chosen-ciphertext attack against NTRU Advances in Cryptology Conference-Crypto 2000 Search in Google Scholar

Gentry, C. Cryptoanalysis of the revised NTRU signature scheme. GentryC. Cryptoanalysis of the revised NTRU signature scheme Search in Google Scholar

Gentry, C. (2001). Key recoverge and message attcaks on NTRU-Composite. Springer Verlag. GentryC. 2001 Key recoverge and message attcaks on NTRU-Composite Springer Verlag Search in Google Scholar

Banks, W. D. (2002). A variant of NTRU with non invertible polynomials. Springer Verlag. BanksW. D. 2002 A variant of NTRU with non invertible polynomials Springer Verlag Search in Google Scholar

Gaborit, P. and Sole, P. (2002). CTRU, a polynomial analogue of NTRU. Inria. GaboritP. SoleP. 2002 CTRU, a polynomial analogue of NTRU Inria Search in Google Scholar

Coglianese, M. and Goi, B. M. (2005). MaTRU: A new of NTRU based cryptosystem. Springer Verlag. CoglianeseM. GoiB. M. 2005 MaTRU: A new of NTRU based cryptosystem Springer Verlag Search in Google Scholar

Jarvis, K. and Nevins, M. (2015). ETRU: NTRU over the Eisenstein integers. Springer. JarvisK. NevinsM. 2015 ETRU: NTRU over the Eisenstein integers Springer Search in Google Scholar

Hoffstein, J., Pipher, J. and Silverman, J. H. (2009). Choosing parameters for NTRUEncrypt. Springer Verlag. HoffsteinJ. PipherJ. SilvermanJ. H. 2009 Choosing parameters for NTRUEncrypt Springer Verlag Search in Google Scholar

Hoffstein, J., Pipher, J., Shanck, J. M. and Whyte, W. (2015). Choosing parameters for NTRU. Springer Verlag. HoffsteinJ. PipherJ. ShanckJ. M. WhyteW. 2015 Choosing parameters for NTRU Springer Verlag Search in Google Scholar

Wan, Z. X. (2011). Finite fields and Galois rings. World Scientific Publishing Company. WanZ. X. 2011 Finite fields and Galois rings World Scientific Publishing Company Search in Google Scholar

McDonald, B. R. (1973). Finite rings with identity. University of Oklahama Publishing. McDonaldB. R. 1973 Finite rings with identity University of Oklahama Publishing Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo