Goppa codes over the p-adic integers and integers modulo pe

Finite Fields and Their Applications 84 (2022) 102097 Contents lists available at ScienceDirect Finite Fields and Their Applications www.elsevier.com/locate/ffa Goppa codes over the p-adic integers and integers modulo pe Markel Epelde Universidad del País Vasco -Euskal Herriko Unibertsitatea, Bizkaia, Spain a r t i c l e i n f o a b s t r a c t Article history: Received 11 October 2021 Received in revised form 22 April 2022 Accepted 27 July 2022 Available online 11 August 2022 Communicated by Sergey Rybakov MSC: 11T71 94B05 Keywords: Algebraic codes Goppa codes McEliece cryptosystem Goppa codes were defined by Valery D. Goppa in 1970. In 1978, Robert J. McEliece used this family of error-correcting codes in his cryptosystem, which has gained popularity in the last decade due to its resistance to attacks from quantum computers. In this paper, we present Goppa codes over the p-adic integers and integers modulo pe. This allows the creation of chains of Goppa codes over different rings. We show some of their properties, such as parity-check matrices and minimum distance, and suggest their cryptographic application, following McEliece’s scheme. © 2022 The Author. Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). In 1970, Valery D. Goppa defined a new class of error-correcting codes over a finite field Fq, nowadays known as Goppa codes [6]. If we consider qto a prime number p, from an algebraic point of view, Goppa codes are Zp-subspaces of Zn p. As error-correcting codes, there also exists a decoding algorithm for them, i.e., a method to find the closest codeword to a given element in Zn p, provided the distance between them is smaller than the error-correcting capability of the Goppa code. In 1978, Robert J. McEliece presented his cryptosystem [9], a method to encrypt a message by encoding an information vector E-mail address: [email protected]. https://doi.org/10.1016/j.ffa.2022.102097 1071-5797/© 2022 The Author. Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). 2M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 and adding errors artificially. For his cryptosystem, he suggested the use of binary Goppa codes and, while other approaches of code-based cryptosystems have been successfully attacked, his scheme remains mostly intact. Despite its drawbacks (such as its large key sizes), this scheme has regained popularity due to his quantum resistance and age [12]. In this paper, we define Goppa codes over the p-adic integers and Zpe, i.e., the ring of integers modulo pe, based on the original idea from Goppa, and we hint a potential cryptographic application of them. In 2005, Antonio A. de Andrade and Reginaldo Palazzo generalized Goppa codes to finite rings [1], but using a different approach. However, we will rely on the generalization of Goppa’s original introduction [6]. This definition was suggested by Markel Epelde et al. in 2020 for Z4[5] and, while de Andrade’s generalization of the decoding algorithm still works, our definition allows to show some additional properties. Both the definition and its basic consequences can be seen in Section 1. In Section 2, we describe the chains of Goppa codes and the relations between their paritycheck matrices. In Section 3, we show how to get isomorphic Goppa codes over different rings by changing one of the parameters of the code. Changing the other parameter leads to some other results in Section 4. Finally, their potential cryptographic application is shown in Section 5. Let us fix h ∈N∪{0}, let n ∈Nand let pbe a prime number. We will denote by Rpe=GR(pe, h)the Galois extension of degree hof Zpefor any e ∈N, and by Rp∞the Galois extension of degree hof the ring of p-adic integers Zp∞, i.e., Rp∞=a0+pa1+···+peae+··· | ai∈Fph,∀i∈N∪{0}. Observe that this ring is formed by formal infinite sums of elements in an extension of degree hof Zp. Let i, j∈N∪{∞}such that i ≥j. We denote by ψpi,pj:Rpi→Rpjthe natural projection of elements in Rpito Rpj, and by  ψpi,pjthe extension of ψpi,pjto n-tuples in Rn pi. Moreover, we define Ψpi,pj:Rpi[X] →Rpj[X]as the natural generalization of ψpi,pj to polynomials, i.e., satisfying Ψpi,pj(n k=0 akXk) =n k=0 ψpi,pj(ak)Xkfor a n ∈N. 1. Definition and basic properties Let us define Goppa codes over Zpe, generalizing Goppa’s original definition in [6]. Definition 1. Let e ∈N∪{∞}, L =(α1, ..., αn) ∈Rn peand g∈Rpe[X]of degree r<n such that ψpe,p(αi) =ψpe,p(αj)for i =jand g(αi)is a unit, i.e., ψpe,p(g(αi)) =0for every i ∈{1, ..., n}. The Goppa code of parameters Land gover Zpeis defined as Γpe(L, g)=c∈Zn pe| n  i=1 ci X−αi ≡0(modg(X)). Example 1. Let h =4, and let p =2, e =3and Rpe=Z8[α], where αis an element of multiplicative order ph−1 = 15. Let g(X) =X3+α4X2+α5Xand, for instance, M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 3 L=(1,α,α 4,α 3,α 5,α 11,α 14,α 2,α 8,α 13,α 9,α 12,α 6). Then Γ8(L, g)is the code generated by G=(2125520325336). This code has length 13, 8elements and minimum distance 7. Remark 1. Let α∈Rpeand g∈Rpe[X]such that g(α)is a unit. Then, (X−α)−1=−g(α)−1g(X)−g(α) X−α modulo g(X). The previous remark allows the proof of the following lemma. Lemma 1. Let e ∈N∪{∞}, let Γpe(L, g)be a Goppa code of length n, and C={c ∈ Zn pe| cH=0}, where H=⎛ ⎜ ⎜ ⎜ ⎜ ⎝ g(α1)−1g(α2)−1... g(αn)−1 α1g(α1)−1α2g(α2)−1... α ng(αn)−1 α2 1g(α1)−1α2 2g(α2)−1... α 2 ng(αn)−1 . . .. . ..... . . αr−1 1g(α1)−1αr−1 2g(α2)−1... α r−1 ng(αn)−1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠(1) and r=degg. Then, C⊆Γpe(L, g)and, if the leading coefficient of gis a unit or e =∞, the equality holds. Proof. Let g(X) =r i=0 giXiand c ∈Zn pe. Then, cH=0implies cHH g=0, where Hg=⎛ ⎜ ⎜ ⎜ ⎜ ⎝ gr00... 0 gr−1gr0... 0 . . .. . ........ . . g2g3... g r0 g1g2... g r−1gr ⎞ ⎟ ⎟ ⎟ ⎟ ⎠. Observe that, when the leading coefficient of gis a unit, the condition is equivalent since Hgis invertible. Since Zp∞is an integral domain, the condition is also equivalent if e =∞. This matrix equality represents the following equations 4M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 gr(c1g(α1)−1+···+cng(αn)−1)=0 gr−1(c1g(α1)−1+···+cng(αn)−1)+gr(c1α1g(α1)−1+···+cnαng(αn)−1)=0 . . . g1(c1g(α1)−1+···+cng(αn)−1)+g2(c1α1g(α1)−1+···+cnαng(αn)−1) +···+gr(c1αr−1 1g(α1)−1+···+cnαr−1 ng(αn)−1)=0 ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ , which can be written compiled into one polynomial equality. Namely, r−1  k=0 ⎛ ⎝ r−k  j=1 gk+j n  i=1 ciαj−1 ig(αi)−1⎞ ⎠Xk=0. Rearranging the terms, it follows that n  i=1 cig(αi)−1 r−1  k=0 Xk r−k  j=1 gk+jαj−1 i=0.(2) Note that r−1  k=0 Xk r−k  j=1 gk+jαj−1 i= r  j=1 gj j−1  k=0 αj−k−1 iXk= r  k=0 gkXk−αk i X−αi=g(X)−g(αi) X−αi . Since the degree of gis greater than the term on the left-hand side of (2), this equation can be written as n  i=1 cig(αi)−1g(X)−g(αi) X−αi≡0(modg(X)). Therefore, cH=0implies (and is equivalent to, when the leading coefficient of gis a unit or e =∞) n  i=1 ci X−αi ≡0(modg(X)),i.e., c∈Γpe(L, g). Remark 2. When c ∈Γpe(L, g)if and only if cH=0, we say that His a parity-check matrix for the code. However, this is an abuse of the term, since the entries of Hdo not necessarily belong to Zpe. In order to write a parity-check matrix in strict sense, we would have to expand each entry as a column formed by its coordinates with respect to a Zpe-basis of Rpe, and then remove the redundant rows of the matrix. Example 2. Substituting the entries of the matrix Hdefined as in (1)for the code in Example 1with their coordinates with respect to the Z2-basis {1, α, α2, α3}results in the parity-check matrix M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 5 H= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 4377447036314 0776175437367 6674757766245 5254734666053 4602051336166 0370705652550 6340347205747 5055471151125 4001431121321 0663021333231 6335626574276 5333507346047 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ . Recall that a code over a ring Ris said to be free if it is isomorphic to Rkfor some k. We now prove the following lemma. Lemma 2. The Goppa code Γp∞(L, g)is a free code, i.e., a free Rp∞-submodule of Rn p∞. Proof. By Lemma 1, Γp∞(L, g)is defined as the dual of the code with generator matrix Hin (1), and every dual code in Zp∞is free [4].  With Lemmata 1and 2, we can prove the following theorem, which consists of the basic properties of Goppa codes as defined in Definition 1. Theorem 1. Let e ∈N∪{∞}and let C=Γ pe(L, g)be a Goppa code. Then, (i) If e =∞, dimRp∞C≥n −h deg g. Otherwise, |C| ≥pe(n−hdeg g). (ii) For any j<e, C∩pjZn pe=pj ψ−1 pe,pe−j(Γpe−j( ψpe,pe−j(L), Ψpe,pe−j(g))), where  ψ−1 pe,pe−j(A)denotes the preimage of a subset A ⊆Zn pe−jthrough the projection map  ψpe,pe−j. In particular, C∩pe−1Zn peis isomorphic as a Fp-linear space to Γp( ψpe,p(L), Ψpe,p(g)), and to Γpj( ψpe,pj(L),Ψpe,pj(g)) ∩pj−1Zn pj. (iii) For any j∈N∪{∞} with j<e,  ψpe,pj(C)is a subcode of Γpj( ψpe,pj(L), Ψpe,pj(g))). As a consequence, if e =∞and for a j∈N, Γpj( ψpe,pj(L), Ψpe,pj(g)) ⊆pZn pj, then C={0}and n ≤h deg g. Moreover, if e ∈Nand Cis free, then Γpj( ψpe,pj(L), Ψpe,pj(g)) = ψpe,pj(Γpe(L, g)). Proof. Let r=degg, let Hbe as defined in (1)and let Hbe a parity-check matrix over Zpeof the code C={c ∈Zn pe| cH=0}.As a consequence of Remark 2, Hhas at most rh rows, |(C)⊥| ≤|Zpe|rh =perh. Hence, if e ∈N, |C| =|Zn pe|/|(C)⊥| ≥pe(n−rh). 6M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 Since, by Lemma 1, C⊆C, this proves the result. If e =∞, from Lemma 2it follows that Γpe(L, g)is a free code and, since from Lemma 1it follows that C=C, a parity-check matrix of Chas at most rh rows and its dimension must be greater than n −rh. For part (ii), pjc ∈Γpe(L, g) ∩pjZn peif and only if n i=1 pjci/(X−αi) ≡0(modg(X)) or, equivalently n i=1 ci/(X−αi) ≡0(modg(X)) and modulo pe−j. This is exactly the condition for cto be a lift of a codeword in Γpe−j( ψpe,pe−j(L), Ψpe,pe−j(g)). Taking j=e −1 establishes that the set of multiples of pe−1in a Goppa code is isomorphic as a Fp-linear space to its traditional Goppa code projection. Finally, let us prove (iii). By definition, c ∈Γpe(L, g)if and only if n i=1 ci X−αi≡ 0(modg(X)). This congruence is also true modulo pj, so  ψpe,pi(c) belongs to Γpj( ψpe,pi, Ψpe,pj(g)). In particular, if e =∞,  ψp∞,pj(C)is a free subcode of Γpj( ψpe,pj(L), Ψpe,pj(g)), so if C ={0}then Γpj( ψpe,pj(L), Ψpe,pj(g)) pZn pj. Moreover, if Γpe(L, g)is free for an e ∈N, then  ψpe,pj(Γpe(L, g)) is also free and a subcode of Γpj( ψpe,pj(L), Ψpe,pj(g)). Let kbe the dimension of C. Since  ψpe,pj(C)is free in Zpj, it has cardinality pjk. On the other hand, by part (ii) and since Cis free, | ψpe,pj(C)|=|C ∩ pe−jZn pe|=pjk. Since  ψpe,pj(C) ⊆Cand they have the same cardinality, the equality holds.  Example 3. 1. Let Cbe the code in Example 1. Observe that, as claimed in part (i) of the previous theorem, 8=|C| ≥ pe(n−hdeg g)=2 3(13−4·3) =8. Moreover, C4=Γ 4( ψ8,4(L), Ψ8,4(g)) and C2=Γ 2( ψ8,2(L), Ψ8,2(g)) are the codes generated by matrices G4=(2121120321332) and G2=(0101100101110), respectively. On the other hand, C∩4Zn 8and C4∩2Zn 4are generated by G3=( 0404400404440 ) and M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 7 G1=( 0202200202220 ), respectively. As stated in part (ii) of the previous theorem, C∩4Z13 8∼ =C4∩2Z13 4∼ =C2 as {0, 1}-linear spaces. Finally, since Cis free, not only are  ψ8,4(C)and  ψ8,2(C) subcodes of C4and C2, respectively, but the equality also holds here, as established in part (iii) of the theorem. 2. Let gbe the same as in Example 1, and let M=(1,α,α 4,α 3,α 5,α 11,α 14,α 2,α 8,α 13,α 9,α 12)∈Rn 8. Then, D=Γ 8(M, g)is the code generated by Q=( 040440040444 ). Now, 2 =|D| ≥812−4·3=1, satisfying part (i) of Theorem 1, and, according to part (ii), D=D∩4Z12 8∼ =D4∩2Z12 4∼ =D2, where D4=Γ 4( ψ8,4(M), Ψ8,4(g)) and D2=Γ 2( ψ8,2(M), Ψ8,2(g)) is generated by Q4=( 020220020222 ) and Q2=( 010110010111 ). Moving to part (iii),  ψ8,4(D) ={0}is included in D4and D2, and  ψ4,2(D4) ={0} is included in D2, but the projections and the codes are not identical. Finally, since D⊆4Z12 4, we know that Γ2∞(M, g) ={0}for any lift Mand gof Mand g, respectively. Remark 3. Part 1 of Example 3shows an instance of a Goppa code over Z8being a lift of the corresponding Goppa codes over Z4and Z2, and the code over Z4being a lift of the corresponding code over Z2. However, as we can see in part 2 of the same example, in general, the codes Γpe(L, g)over Zpeare not lifts of its equivalent over Zp, Γp( ψpe,p(L), Ψpe,p(g)). For instance, in that example the code over the 2-adic integers is trivial, whereas the codes over Z8, Z4and Z2have cardinality 2. In fact, none of them are lifts of the codes below. Corollary 1. Let e ∈N∪{∞} and let C=Γ pe(L, g)be a Goppa code. The minimum distance of Csatisfies d(C) ≥deg Ψpe,p(g) +1. Furthermore, if e =∞, Γp∞(L, g)satisfies d ≥deg g+1. 8M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 Proof. Let e ∈N. Observe that one can always find a (non-zero) codeword cof minimum weight such that c ∈C∩pe−1Zn e. In fact, if cis a multiple of psbut not a multiple of ps+1, then pe−s−1c ∈C∩pe−1Zn eand w(pe−s−1c) ≤w(c). According to part (ii) of Theorem 1, C∩pe−1Zn e=pe−1 ψ−1 pe,p(Cp), where Cp=Γ p( ψpe,p(L), Ψpe,p(g). Observe that C0is a traditional Goppa code, having minimum weight d(C0) ≥deg Ψpe,pg+1. If e =∞, let Hbe as defined in (1)and let c ∈Γpe(L, g)be a non-zero codeword. Then, by Lemma 1cH=0so there exist w(c) linearly dependent columns in H. However, any r×rsubmatrix of Hreduces to a Vandermonde matrix with a non-zero determinant, so w(c) ≥r+1. Therefore, if x, y∈Γpe(L, g)are two distinct codewords, d(x, y) =w(x −y) ≥r+1.  2. Parity-check matrix In this section, we show the relation between Goppa codes of the same parameters over different rings and their parity-check matrices. First, we present the following lemma, the proof of which can be found in [8]. Lemma 3. Let e ∈N, and let fbe a regular polynomial in Zpe[X]. Then, there exist a polynomial f∗∈Zpe[X]and q∈Zpe[X]such that Ψpe,p(f) =Ψ pe,p(f∗), f(X) = q(X)f∗(X)and the leading coefficient of f∗is a unit. We can also show the following relation between Goppa codes with similar polynomial parameters. Lemma 4. Let e ∈N∪{∞} and let Γpe(L, g)be a Goppa code. Then, if there exists polynomial g∗(X)such that its leading coefficient is a unit, gis a multiple of g∗and Ψpe,p(g∗) =Ψ pe,p(g), then Γpe(L, g) ⊆Γpe(L, g∗). Moreover, if e ∈N, the equality holds. Proof. Let g∗, q∈Rpe[X]be such that the leading coefficient of g∗(X)is a unit, g∗(X)q(X) =g(X)and Ψpe,p(g∗) =Ψ pe,p(g). Therefore, for some unit uin Zpe, Ψpe,p(q) =ψpe,p(u) =0, so q(X) =u +pm(X). This implies that, if e ∈N, q(X)is a unit, its inverse being 1 −pu−1m(X) +p2u−2m(X)2+···+(−1)e−1pe−1u1−em(X)e−1. Therefore, Γpe(L, g) =Γ pe(L, q·g∗)and c ∈Γpe(L, g)iff n  i=1 ci X−αi ≡0(modq(X)g∗(X)). Multiplying the term in the left-hand side by n i=1(X−αi), it follows that c ∈Γpe(L, q· g∗)if and only if q(X)g∗(X) divides M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 9 n  i=1 ci 1≤j≤n j=i (X−αi). Therefore, if c ∈Γpe(L, g)then g∗(X) divides this term. In fact, if q(X)g∗(X) divides the term then also g∗(X) divides this term. Since (g∗(X), X−αi) =1for every i ∈{1, ..., n}, this is equivalent to c ∈Γpe(L, g∗). Observe that this code is well defined, since for all i ∈{1, ..., n}, ψpe,p(g∗(αi)) =ψpe,p(g(αi)) =0.  With this information, we can give an explicit expression for a parity-check matrix of every Goppa code. Theorem 2. Let e ∈N∪{∞}and let C=Γ pe(L, g)be a Goppa code. (i) If e =∞, Has in (1)is a parity-check matrix for C. (ii) If e ∈Nand g∗∈Rpe[X]is the polynomial satisfying the conditions in Lemma 4, then H∗=⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ g∗(α1)−1g∗(α2)−1... g∗(αn)−1 α1g∗(α1)−1α2g∗(α2)−1... α ng∗(αn)−1 α2 1g∗(α1)−1α2 2g∗(α2)−1... α 2 ng∗(αn)−1 . . .. . ..... . . αr∗−1 1g∗(α1)−1αr∗−1 2g∗(α2)−1... α r∗−1 ng∗(αn)−1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (3) is a parity-check matrix for C, where r∗=degg∗. Proof. The first part is straightforward from Lemma 1. Let e ∈N. By Lemmata 3and 4, there exists g∗∈Rpe[X]with a unit as leading coefficient such that C=Ψ pe,p(g∗) and Γpe(L, g) =Γ pe(L, g∗). Since the leading coefficient of g∗is a unit, by Lemma 1, H∗ is a parity check matrix for C. Example 4. Let us consider the parameters in Example 1, and let f(X) =2α14X4+(1 + 2α3)X3+3α4X2+α5X. Since the leading coefficient of gis a unit, Ψ8,2(g) =Ψ 8,2(f) and f(X) =(1 +2α14X)g(X), from Lemma 4it follows that Γ8(L, f) =Γ 8(L, g)and H from Example 2is a parity-check matrix for Γ8(L, f). Remark 4. We have presented a parity-check matrix for any Goppa code Γpe(L, g). This allows the use of the efficient decoding algorithm from [1], based on the parity-check matrix, in our context. Let us see how the relations between the parity-check matrices for different values of e. In order to prove that, we introduce a topological result. 16 M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 are exact copies of the original Γpe(L, g)and multiples of pj−e. Moreover, by part (iii) of Theorem 1, the code over the p-adic integers must be trivial.  4. Changes in the polynomial In the previous section, we have studied the changes in the Goppa codes by modifying L. Now, let us change the Goppa polynomial. First, let us recall the following result for Goppa codes found in [7]. Lemma 8. Let g∈R2[X]be a square-free polynomial. Then, Γ2(L, g) =Γ 2(L, g2). Now, we can prove the following result for p =2. This theorem is the generalization of its quaternary version, shown in [5]. Theorem 5. Let g∈R2e[X]be a square-free polynomial with a unit as its leading coefficient, let Γ2e(L, g)be a Goppa code, and g2∈R2e[X]such that deg g2≤deg g. Then, Γ2e(L, g)=Γ 2e(L, g +2 e−1g2). Proof. Let us prove Γ2e(L, g) ⊆Γ2e(L, g+2 e−1g2)for any polynomial g2satisfying deg g2≤deg g. Let c ∈Γ2e(L, g). According to Theorem 1,  ψ2e,2(c) ∈ Γ2( ψ2e,2(L), Ψ2e,2(g)). Since gis square-free, Ψ2e,2(g)is also square-free, and by Lemma 8,  ψ2e,2(c) ∈Γ2( ψ2e,2(L), Ψ2e,2(g)2). By Lemma 1and since the leading coefficient of gis a unit, this happens when n  i=1 ciαj−1 ig(αi)−2=0 (mod2) for all j∈{1, ...2 deg g}. Equivalently, n  i=1 ciαk+j−1 ig(αi)−2=0 (mod2) for all j∈{1, ..., deg g}and k∈{0, 1, ..., deg g}. The equations above can be written as r  k=0 ak n  i=1 ciαk iαj−1 ig(αi)−2=0 (mod2) for all j∈{1, ..., deg g}and ai∈R2eor, equivalently, n  i=1 ciαj−1 ig(αi)−2g2(αi)=0 (mod2) M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 17 for all j∈{1, ..., deg g}and g2∈Rpe[X]such that deg g2≤deg g. Here, we have taken g2(X) =r k=0 akXk. Since c ∈Γ2e(L, g), by Lemma 1and since the leading coefficient of gis a unit, n i=1 ciαj−1 ig(αi)−1=0for all j∈{1, ..., deg g}, so this is equivalent to n  i=1 ciαj−1 ig(αi)−1+2 e−1 n  i=1 ciαj−1 ig(αi)−2g2(αi)=0 for all j∈{1, ..., deg g}and g2satisfying the hypothesis. Finally, by Lemma 6, the expression above can be written as n  i=1 ciαj−1 ig(αi)−1(1 −2e−1g(αi)−1g2(αi)) = 0 for all j∈{1, ..., deg g}and g2satisfying the conditions of the theorem. Since the leading coefficient of g+2 e−1g2is also a unit, this is equivalent to c ∈Γ2e(L, g+2 e−1g2).  Corollary 4. Let e ∈N, g∈R2e[X]and let g∗∈R2e[X]be the polynomial that, by Lemma 3, has the same projection as gand has a unit as its leading coefficient. Let g2∈R2e[X]such that deg g2≤deg g∗. If Ψ2e,2(g)is square-free, Γ2e(L, g)=Γ 2e(L, g∗+2 e−1g2). If qis the polynomial satisfying q(X)g∗(X) =g(X), then Γ2e(L, g)=Γ 2e(L, g +2 e−1qg2). Proof. The proof follows directly from Theorem 5. Example 7. Let us consider again Example 1. Observe that g(X) =X(X2+α4X+α5), and X2+α4X+α5has no roots in R8, so gis square-free in R8. By the previous theorem, we can check that Γ8(L, (1 +4α2)X3+α4X2+(α5+4α)X+4) is generated by the same generator matrix Gfrom Example 1. 5. Applications to cryptography Goppa codes are the core of the original McEliece cryptosystem [9]. This cryptographic scheme, as well as Niederreiter’s [11], can be generalized to rings. Definition 3. Let e ∈N∪{∞}, n ∈Nand C⊆Zn pebe a Zpe-linear code with generator matrix G, error-correcting capacity t ≥t0and an efficient decoding algorithm D. We define the ZpeMcEliece cryptosystem as follows. The secret key is formed by G, D, a random permutation matrix Pand a random nonsingular matrix S. The pair (G, t0) forms the public key, where G=SGP. We define the encryption function as E(m) = 18 M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 mG+z, where z∈Zn peis a randomly generated error satisfying w(z) ≤δ. The decryption process consists of: first, multiplying the ciphertext by P−1, then apply the decoding algorithm Dand finally solving linear equation systems. The security of the McEliece cryptosystem is based both on the NP-hardness of the decoding problem of random linear codes over Zpe, and the indistinguishability of the code C, i.e., one should not be able to separate Cfrom a random Zpe-linear code. Regarding the former, Elwyn R. Berlekamp, McEliece and Henk C.A. van Tilborg proved the difficulty of the problem in [2]for the case pe=2. This proof can be generalized to Zpe-linear codes [13]. On the other hand, the original McEliece cryptosystem uses binary Goppa codes, and this family of codes still seems to be the most reliable today. When e ∈N, one can prove that the distinguishability problem for the binary Goppa codes can be reduced to the distinguishability of pe-ary Goppa codes. In fact, both distinguishability problems are equivalent. Theorem 6. Let e ∈N. The distinguishability problems for Goppa codes over Zpand Zpe are equivalent. Proof. Let us assume there exists a distinguisher Dfor Goppa codes over Zpe, i.e., a polynomial time algorithm to distinguish the code. Let C=pe−1 ψ−1 pe,p(Γp(L, g)). According to Corollary 3, Cis a Goppa code over Zpefor some Leand gesuch that  ψpe,p(Le) =L and Ψpe,p(ge) =g. Applying Dto Cidentifies C, hence distinguishing Γp(L, g). Now, let us assume there exists a distinguisher Dfor p-ary Goppa codes, i.e., a polynomial time algorithm to distinguish a Goppa code over Zp. Let Cthe p-ary code isomorphic to Γpe(L, g) ∩pe−1Zn pe. According to Theorem 1, Cis a Goppa code of parameters  ψpe,p(L) and Ψpe,p(g). Applying Dto Cidentifies C, hence also distinguishing Γpe(L, g).  This result rises the potential cryptographic interest of Goppa codes. In fact, if p = 2, the security of every Goppa code reduces to the security of the original McEliece cryptosystem, which is considered by far one of the safest cryptographic schemes, even resisting attacks by a quantum computer [12]. 6. Conclusions and future work In this paper, we have presented Goppa codes over the p-adic integers and integers modulo a power of p. We have proved their basic properties, and some isomorphisms between Goppa codes over different rings. Finally, while we leave the possible applications of Goppa codes over the p-adics as future work, we have shown a possible cryptographic application of these codes over the integers modulo pe. This is interesting due to the raising popularity of code-based cryptography as one of the few quantum-resistant families of cryptographic schemes. M. Epelde / Finite Fields and Their Applications 84 (2022) 102097 19 Acknowledgments This work is part of a virtual stay in the University of Scranton. The author wants to thank professor S. Dougherty for his suggestions and comments. The author also thanks the reviewers for their remarks. References [1] A.A. de Andrade, R. Palazzo Jr., Goppa and Srivastava codes over finite rings, Comput. Appl. Math. 24 (2) (2005), https://doi .org /10 .1590 /S0101 -82052005000200005. [2] E. Berlekamp, R. McEliece, H. van Tilborg, On the inherent intractability of certain coding problems (corresp.), IEEE Trans. Inf. Theory 24 (3) (1978), https://doi .org /10 .1109 /TIT .1978 .1055873. [3] M. Cruz-López, A. Murillo-Salas, A recurrent random walk on the p-adic integers, Braz. J. Probab. Stat. 30 (1) (2016) 145–154, https://doi .org /10 .1214 /14 -BJPS265. [4] S. Dougherty, Y.H. Park, Codes over the p-adic integers, Des. Codes Cryptogr. 39 (1) (2006) 65–80, https://doi .org /10 .1007 /s10623 -005 -2542 -x. [5] M. Epelde, X. Larrucea, I.F. Rúa, On quaternary Goppa codes, Discrete Math. 343 (9) (September 2020), https://doi .org /10 .1016 /j .disc .2020 .111962. [6] V.D. Goppa, A new class of linear correcting codes, Probl. Pereda. Inf. 6(3) (1970) 24–30. [7] F.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, vol. 16, North-Holland Publ. Co, Amsterdam, 1981. [8] B.R. McDonald, Finite Rings with Identity, Pure and Applied Mathematics, vol. 28, M. Dekker, New York, ISBN 0824761618, 1974. [9] R.J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, Deep Space Network Progress Report 44, 1978. [10] J. Munkres, Topology, Prentice-Hall of India, New Dehli, ISBN 978-81-203-2046-8, 2004, p. 169. [11] H. Niederreiter, Knapsack type cryptosystems and algebraic coding theory, Probl. Control Inf. Theory 15 (1986). [12] Post-quantum cryptography standardization process, https://csrc .nist .gov /Projects /post -quantum - cryptography. [13] V. Weger, K. Khathuria, A.L. Horlemann, M. Battaglioni, P. Santini, E. Persichetti, On the hardness of the Lee syndrome decoding problem, preprint, https://doi .org /10 .48550 /arXiv .2002 .12785, 2020.