title: Galois ring isomorphism problem
authors: Karan Khathuria
text: 
  Molecular Simulation of Electrode-Solution Interfaces
      Laura Scalfi,^1 Mathieu Salanne,^1,2 and Benjamin
  Rotenberg^1,2
      Aug. 2020
  ===================================================================
  
  
      Recently, Doröz et al. (2017) proposed a new hard problem, called the finite field isomorphism problem, and constructed a fully homomorphic encryption scheme based on this problem. 
      In this paper, we generalize the problem to the case of Galois rings, resulting in the Galois ring isomorphism problem. The generalization is achieved by lifting the isomorphism between the corresponding residue fields. As a result, this generalization allows us to construct cryptographic primitives over the ring of integers modulo a prime power, instead of a large prime number.
  
  
  
  § INTRODUCTION
  
  
  Finite fields have been studied extensively due to their numerous applications in different areas of mathematics and computer science, for example, combinatorics, number theory, design theory, coding theory, cryptography, etc. Finite fields are at the base of the theory of finite commutative rings. A direct generalization of finite fields is the Galois rings. The theory of finite fields and Galois rings are parallel and have many similarities. As a result, it becomes natural to extend and study the applications of finite fields to the case of Galois rings. Some of the known applications of Galois rings include: public-key cryptography over residue class rings of integers <cit.>, multisequence shift register synthesis over Galois rings <cit.>, digital signal processing <cit.> and algebraic coding theory <cit.>.
  
  
  
  In a recent paper <cit.>, Doroz et al. presented some new cryptographic applications of finite fields, by introducing a new hard problem called the finite field isomorphism (FFI) problem. Let p be a prime, let _p be the finite field with p elements, and let ϕ be an isomorphism between two distinct extensions of _p, say := _p[x]/(f(x)) and := _p[y]/(F(y)). We start from a `short' element a(x) (an element having small coefficients) in  and consider its image ϕ(a) in . Informally, the decisional FFI problem asks one to distinguish ϕ(a) from a random element in , without having the knowledge of the isomorphism ϕ. Whereas, the computational FFI problem asks one to find the isomorphism ϕ, given the representation of  and some images of short elements. 
  In the same paper, the authors developed a fully homomorphic encryption scheme based on the hardness assumption of the FFI problem. Later, in <cit.>, also a signature scheme was proposed relying on this assumption.
  
  In this work, we generalize the FFI problem to Galois rings. In particular, we define the Galois ring isomorphism (GRI) problem, that is analogous to the definition of the FFI problem with  and  being two distinct isomorphic Galois rings. In this case, the coefficients of elements in  and  live in /p^s, instead of /p. The analysis of the hardness of the FFI problem can simultaneously be extended to study the hardness of the GRI problem. Similar to the case of FFI problem, we describe some lattice based attacks to solve the GRI problem.
  
  With respect to practical applications of the GRI problem, we need efficient algorithms to construct and use isomorphisms between two Galois rings. This can be achieved by lifting the isomorphism between the corresponding residue fields. Galois rings are finite local rings having maximal ideal (p) and residue field _p^n, for some prime integer p. Therefore, an isomorphism between Galois rings naturally induces an isomorphism between the corresponding residue fields. Moreover, the isomorphisms between Galois rings are in one-to-one correspondence with the isomorphisms between the respective residue fields.   
  
  The main advantage of this generalization is that the applications of the FFI problem can directly be extended to the Galois rings. Hence, we get a fully homomorphic encryption scheme and a signature scheme over the rings of integers modulo a prime power. This is an advantage because it is generally more efficient to do operations modulo 2^64 than a 64-bit prime. This is because the arithmetic logic units (ALUs) in the CPU perform arithmetic operations on integer binary numbers, which implies the operations modulo 2^s can be performed trivially whereas operations modulo large prime number involve modular reductions. Moreover, using the Chinese remainder theorem, we can further generalize the results over any arbitrary integer modulo ring.
   
  
  The organization of the paper is as follows. In Section <ref>, we recall the finite field isomorphism problem and discuss its important aspects, namely hardness and construction of isomorphisms. In Section <ref>, we define the Galois ring isomorphism problem and we provide an algorithm to construct Galois ring isomorphism by lifting the isomorphisms between the corresponding residue fields. Then, in the same section, we discuss the hardness of the GRI problem and describe some lattice based techniques to solve it. In Section <ref>, we remark about further generalization of the problem by using the Chinese remainder theorem. Finally, in Section <ref>, we draw some concluding remarks and discuss further works. 
  
  
  
  
  
  § FINITE FIELD ISOMORPHISM PROBLEM
   
  
  
  In <cit.>, Doröz et al. proposed an encryption scheme based on a new (computationally) hard problem, called the finite field isomorphism problem. It relies on the difficulty of recovering a secret isomorphism between two finite fields. 
  
  Let _p be the finite field with p elements, where p is a prime number. Let  f(x) ∈_p[x] and F(y) ∈_p[y] be monic irreducible polynomials of degree n. Then := _p[x]/(f(x)) and := _p[y]/(F(y)) are isomorphic fields with p^n elements. Let ϕ be an isomorphism from  to .
  
  We will use the variable x and lower case letters for polynomials in  and the variable y with upper case letters for polynomials in . We will perform reductions mod p into the interval (-p/2,p/2].
  Let χ_β be a distribution that produces samples from  having coefficients bounded between -β and β, given 1 ≤β≤ p/2.
  
  
  Let , , ϕ, χ_β be as before and let a_1(x),…,a_k(x) be samples from χ_β with corresponding images A_1(y),…,A_k(y) in .
  
      
    * The computational FFI problem (CFFI) is: Given ,A_1(y),…,A_k(y), recover f(x) and/or the preimages a_1(x),…,a_k(x).
      
    * The decisional FFI problem (DFFI) is: Given , A_1(y),…,A_k(y) and B_1(y), B_2(y), where one of B_1(y), B_2(y) is the image of a sample from χ_β and the other one is taken uniformly from , distinguish, with a probability greater than 1/2, the element that was constructed using ϕ.
  
  
  
  The hardness of the FFI problem is based on the following experimental observation.
  
  <cit.>
  Let f(x)∈_p[x] and F(y)∈_p[y] be chosen uniformly from the set of monic irreducible polynomials of degree n. Let ,, ϕ and χ_β be defined as before. 
  Then the image in  of a collection of polynomials in  sampled from χ_β is computationally hard to distinguish from a collection of polynomials sampled uniformly in . By a proper choice of parameters, the ability to distinguish such a collection can be made arbitrarily hard.
  
  
  In the same paper, Doröz et al. presented three ways to solve the FFI problem. The first two are based on lattice reduction algorithms, whereas the third one is based on solving non-linear polynomial equations. 
  
      
    * Lattice attacks: The isomorphism ϕ: → is also an _p-vector space isomorphism. Hence, ϕ^-1 can be described by an n × n matrix M, i.e., if ϕ^-1(A(y)) = a(x), then a = AM where A,a are the coefficient vectors of the polynomials A(y) and a(x), respectively. By collecting several samples of images of short polynomials in , one gets an instance of a shortest vector problem in a publicly known lattice. In Section <ref>, we describe, in detail, an analogue of this attack for the case of the Galois ring isomorphism problem.
      
    * Non-linear algebraic attack: The strategy here is to recover the image of x (and hence the isomorphism ϕ) by solving a system of high degree multivariate polynomial equations. Suppose the attacker knows A_1(y),A_2(y) ∈ such that they are images of the elements  a_1(x),a_2(x) ∈ sampled from χ_β. Then for each i ∈{1,2}, A_i(y) = a_i(ϕ(x)) F(y). By equating the coefficients, the attacker obtains 2n non-linear equations in 3n unknowns (the coefficients of a_1(x),a_2(x) and ϕ(x)). Then the attacker can eliminate the coefficients of ϕ(x) (e.g. by using Gröbner basis algorithms) to obtain a system of n non-linear equations in 2n unknowns. Solving such a system appears to be exponentially difficult. 
  
  
  
  
  
   §.§ Constructing an Isomorphism
   
  For any cryptographic application of the FFI problem, we need to efficiently construct an isomorphism between finite fields. This can be achieved using Algorithm <ref>.
  
  
  
  Algorithm <ref> consists of two main steps. Let := _p[x]/(f(x)) and := _p[y]/(F(y)), as in the algorithm. The first step is to compute a root α∈ of f(t) ∈[t], which can be done using fast polynomial time algorithms, for example,  routine of Pari-GP <cit.>. The second step is to compute the inverse isomorphism by finding β∈ which is a root of F(t) ∈[t] and satisfy A(β) - x = 0 in , where A(y) is the polynomial representation of α in . For more details on Algorithm <ref>, we refer the interested reader to <cit.>.
  
  
  
   
   The polynomial f(x) must be chosen independently from the polynomial F(y) such that knowledge of F(y) does not give any information about f(x). Otherwise, the attacker may try to gather information about f(x) when she has isomorphic images in  of short polynomials in .
   
  
  
  
  
  
  § GALOIS RING ISOMORPHISM PROBLEM
   
  In this section, we generalize the finite field isomorphism problem to the case of Galois rings. We first recall the definition and properties of Galois rings. We refer to <cit.> as a classical reference for the theory of finite rings and to <cit.> for more detailed reference for Galois rings. 
  
  
  Let p be a prime number, s and n be positive integers. A Galois ring GR(p^s,n) is a finite commutative unitary local ring of characteristic p^s and cardinality p^sn.
  
  
  <cit.> Let GR(p^s,n) be a Galois ring. Then 
  
      
    * GR(p^s,n) is isomorphic to (/p^s)[x]/(f(x)), for any monic polynomial f(x) ∈(/p^s)[x] of degree n whose reduction modulo p is irreducible in (/p)[x].
      
    * GR(p^s,n) is a local ring with a maximal ideal (p) = p GR(p^s,n) and residue field GR(p^s,n)/(p) ≅_p^n. In particular, we have a homomorphism π: GR(p^s,n) →_p^n given by taking reduction modulo p, whose kernel is (p).
  
  
  
  
  Let  and  be two (isomorphic) Galois rings of characteristic p^s and cardinality p^sn. More precisely, let f(x) ∈(/p^s)[x] and F(y) ∈(/p^s)[y] be monic polynomials of degree n such that they are irreducible modulo p, and define:
  
      = (/p^s)[x]/(f(x))          = (/p^s)[y]/(F(y)).
  
  Let ϕ be an isomorphism between  and . 
  
  All the reductions we perform will be centered at 0, i.e., reductions mod p belong to the interval (-p/2,p/2], and reductions mod p^s belong to the interval (-p^s/2,p^s/2].
  Let χ_β be a distribution that produces samples from  having coefficients bounded between -β and β, given 1 ≤β < p^s/2.
  
   
  
  Let ,,ϕ,χ_β as before and let a_1(x),…,a_k(x) be samples from χ_β with corresponding images A_1(y),…,A_k(y) in .
  
      
    * The computational GRI problem (CGRI) is: Given ,A_1(y),…,A_k(y), recover f(x) and/or the preimages a_1(x),…,a_k(x).
      
    * The decisional GRI problem (DGRI) is: Given , A_1(y),…,A_k(y) and B_1(y), B_2(y), where one of B_1(y), B_2(y) is the image of a sample from χ_β and the other one is taken uniformly from , distinguish, with a probability greater than 1/2, the element that was constructed using ϕ.
  
  
  
  
  
  
  
   §.§ Algorithm to construct Galois ring isomorphisms
  
  
  Let f,F,, be described as above. To construct an isomorphism ϕ between  and , we lift the isomorphism between their residue fields. In this section, we will use the notation α (resp. f(x)) to denote αp (resp. f(x) p) for any α∈/p^s (resp. f(x) ∈/p^s[x]).
  
  Let ϕ be an isomorphism between  and , and let π_:→_p[x]/(f(x)) and π_: →_p[y]/(F(Y)) be homomorphims given by reduction modulo p. Then we obtain the following commutative diagram:
  
      = (/p^s)[x]/(f(x)) rϕ[swap]dπ_    = (/p^s)[y]/(F(y)) dπ_
      
       _p[x]/(f(x)) rϕ   _p[y]/(F(y))
  
  Since ϕ is an isomorphism, the induced map ϕ is a field isomorphism. Conversely, given an isomorphism ϕ: _p[x]/(f(x)) →_p[y]/(F(y)), there exists a unique isomorphism ϕ: → that induces ϕ, see <cit.>. The construction and uniqueness of ϕ follows from the following proposition, which is a special case of <cit.>. We provide the proof because it proves the correctness of Algorithm <ref> that describes the construction of ϕ.
  
  <cit.>
  Let R = GR(p^s,n) be a Galois ring and consider the homomorphism π: R → R/(p). Let f(x) be a degree n monic polynomial over /p^s such that f(x) is irreducible over /p. Further, let α be a root of f(x) in R/(p). Then there exists a unique root β∈ R of f(x) such that π(β) = α.
  
  
  
  First note that f(x) has degree n because f(x) is monic. Thus, R/(p) ≅_p^n and f(x) has n distinct roots in R/(p). This implies that α exists and it is a simple root of f(x). 
  
  Let α∈ R be the trivial lift of α. We construct a sequence β_0,β_1,…,β_s-1∈ R as follows:
  
      β_0    = α, 
      β_i+1   = β_i - (f^'(β_i))^-1 f(β_i)  i=0,…,s-2.
  
  We will show that β_s-1 is a root of f(x) and π(β_s-1) = α.
  
  We first show that π(β_i) = α for i = 0,1,…,s-1. Clearly, π(β_0) = π(α)= α. Now, let i ≥ 1 and assume π(β_i-1) = α. Since α is a simple root of f(x), we have that π(f^'(β_i-1)) = f^'(α) = (f)^'(α) ≠ 0. Hence, f^'(β_i-1) is a unit of R. Thus, 
      π(β_i)     = π(β_i-1) - π((f^'(β_i-1))^-1) π(f(β_i-1)) 
          = α - π((f^'(β_i-1))^-1) f(α)
          = α.
   
  
  Now, we show that f(β_i) ∈ (p^i+1) for all i=0,1,…,s-1. Clearly, since π(f(β_0)) = f(α) = 0, we get f(β_0) ∈ (p). Now, let i ≥ 1 and assume that f(β_i-1) ∈ (p^i). Then by Taylor's formula[Let S be a ring and f(x) = a_nx^n + ⋯ + a_0 ∈ S[x]. Then the Taylor's formula is given by 
      f(x+a)    = f(x) +  f^'(x)/1! a + f^''(x)/2!a^2 + ⋯ + f^(n)(x)/n!a^n, 
       
          f^'(x)    = na_n x^n-1 + (n-1)a_n-1x^n-2 + ⋯ + a_1,
      
          f^(m)(x)    = (f^(m-1)(x))^' m ≥ 2.
   We note that the Taylor's formula is well-defined as k! divides each coefficient of f^(k)(x) for all k ∈{2,…,n}.] we have
  
      f(β_i)    = f(β_i-1 - f^'(β_i-1)^-1f(β_i-1) ) 
          = f(β_i-1) + f^'(β_i-1)/1!(-f^'(β_i-1)^-1f(β_i-1)) 
              +  f^''(β_i-1)/2!(-f^'(β_i-1)^-1f(β_i-1))^2 + ⋯
              + f^(n)(β_i-1)/n!(-f^'(β_i-1)^-1f(β_i-1))^n 
          = f^''(β_i-1)/2!(-f^'(β_i-1)^-1f(β_i-1))^2 + ⋯
              + f^(n)(β_i-1)/n!(-f^'(β_i-1)^-1f(β_i-1))^n 
         ∈ (p^i+1)
   
  Thus, by induction, we have β_s-1∈ R such that π(β_s-1) = α and f(β_s-1) ∈ (p^s) =(0). Thus we found a root β:= β_s-1∈ R of f(x) with π(β) = α.
   
  To prove uniqueness, we first write f(x) = (x-β)g(x), for some g(x) ∈ R. Observe that g(α) ≠ 0, as α is a simple root of f(x). 
  Let β^' be another root of f(x) in R such that π(β^') = α. Then we have 
      0 = f(β^') = (β^' - β) g(β^').
   Moreover, π(g(β^')) = g(α) ≠ 0, which implies g(β^') is a unit of R and hence β^' = β.
  
  
  
  
  
  
  
  
  
  
   §.§ On the hardness of the Galois ring isomorphism problem
   
  
  Clearly, the Galois ring isomorphism (GRI) problem is a generalization of the finite field isomophism (FFI) problem. Hence, it follows that the GRI problem is as hard as the FFI problem in the sense that a polynomial time algorithm that solves the GRI problem would also solve the FFI problem. 
  
  In some special cases, the GRI problem canonically reduces to the FFI problem. In particular, reduction to FFI problem is possible when β < p/2. Let ,,ϕ,χ_β, a_1(x),…,a_k(x), A_1(y),…,A_k(y) be as in Definition <ref>. By taking reduction modulo p, we obtain an instance of the FFI problem. Let π_: →:= _p[x]/(f(x)) and π_: →:= _p[y]/(F(y)) be the homomorphisms given by taking reduction modulo p. Then for all i ∈{1,…,k} we have π_(a_i(x))= a_i(x) = a_i(x), as the coefficients of a_i's belong to (-β,β]. This gives an instance of the FFI problem with input ,, χ^'_β, π_(a_1(x)),…,π_(a_k(x)), π_(A_1(y)),…,π_(A_k(y)), where χ^'_β is a distribution on  that produces samples whose coefficients are bounded between -β and β.
  
  In general if β is not less than p/2, then the GRI problem does not directly reduces to the FFI problem. However, we can generalize the techniques of solving FFI problem to solve the GRI problem.
  
  
  
    §.§.§ Solving the GRI problem using lattice reduction algorithms
  
  In <cit.>, Doröz et al. provided two ways to solve the FFI problem using lattice reduction techniques. In the following, we extend these techniques to solve the GRI problem. 
  
  Let , , ϕχ_β, a(x), A(y) be as in the Definition <ref>. We first note that ϕ (and equivalently ϕ^-1) is also a /p^s-module homomorphism, because ϕ is given by ∑_i=0^n-1a_ix^i ↦∑_i=0^n-1a_i ϕ(x)^i F(y). 
  
  We identify a polynomial a(x) with the coefficients vector a=(a_0,…,a_n-1). Then the map ϕ can be described by using an n × n matrix over /p^s.
  Let, for each i ∈{0,…,n-1}, 
      ϕ(x)^i := ∑_j=0^n-1 m_i,j y^j ∈,
   for some m_i,j∈/p^s. Let M = (m_i,j) be the corresponding matrix. Then, A(y) = a(ϕ(x)) F(y) implies that A = aM over /p^s.
  Moreover, the matrix M is invertible, as there exists an n × n matrix N = (n_i,j) ∈(/p^s)^n × n, corresponding to ϕ^-1 with respect to bases {1,x,…,x^n-1} and {1,y,…,y^n-1}, such that NM=MN=I_n.
  
  Using this vector/matrix correspondence, we can extend the two lattice attacks presented in <cit.> to our case. In the following, we describe one of the attacks in which the corresponding lattice has dimension nearly 2n. 
  
  Let A_1,…,A_k be the known vectors and a_1,…,a_k be the unknown vectors, corresponding to the polynomials A_1(y),…,A_k(y) and a_1(x),…,a_k(x), respectively. Then the unknown vectors a_1 = A_1 N,…, a_k = A_k N are small, i.e., the absolute value of the entries is bounded by β. We consider a single coordinate of these vectors, let N_j^⊺ be the j-th column of the matrix N and let 
      b_j := (A_1 N_j^⊺, A_2 N_j^⊺, …, A_k N_j^⊺).
   Now, define the matrices 
      P := (A_1^⊺| A_2^⊺ | ⋯ | A_k^⊺),    Q := (a_1^⊺|a_2^⊺|⋯|a_k^⊺),
   and set 
      D = [       P; p^s I_k ].
  
  
  The matrices P and Q are of dimension n× k with entries from /p^s, the matrix D has dimension (n+k)× k and b_j is the vector consisting of the j-th coordinates of a_i's.
  
  Let L(D) be the lattice generated by the rows of D, so it has dimension k and it contains the short row vector b_j. If k is chosen sufficiently large, then the vectors b_j will be short relative to the Gaussian heuristic. As a result, such vectors (or a linear combination of them) can be recovered using lattice reduction algorithms.
  
  
  
  
  § NOTES ON FURTHER GENERALIZATIONS
   
  
  It is possible to further generalize the FFI problem in many different ways.
  In the most general sense, we can define isomorphism between arbitrary finite commutative rings. Every finite commutative ring is a direct sum of finitely many finite local rings, see <cit.>. Moreover, each of these finite local rings is a homomorphic image of a polynomial ring over a Galois ring, see <cit.>. This implies that an isomorphism between finite rings can be obtained by constructing an isomorphism between the direct summands. 
  
  For more practical purposes, we may restrict ourselves to the case of finite rings that are direct sums of Galois rings. 
  Let R_1,…,R_k be Galois rings given by R_i = (/p_i^s_i)[x]/(f_i(x)) for each i ∈{1,…, k}, where p_1,…,p_k are distinct primes and for each i ∈{1,…,k}, f_i(x) is a monic polynomial of degree n whose reduction modulo p_i is irreducible in (/p_i^s_i)[x]. Let R = R_1 ⊕⋯⊕ R_k, i.e., 
      R = [x]/(p_1^s_1,f_1(x)) ⊕⋯⊕[x]/(p_k^s_k,f_k(x)).
   Since the ideals (p_i^s_i,f_i(x)) and (p_j^s_j,f_j(x)) are co-maximal for all i ≠ j, we can apply the Chinese remainder theorem to obtain the ring isomorphism 
      R ≅[x]/I,
   where I = ∏_i=1^k (p_i^s_i,f_i(x)). One can check that I = (m,f(x)), where m = p_1^s_1⋯ p_k^s_k and f(x) is a monic polynomial of degree n such that f(x) ≡ f_i(x) p_i^s_i for each i ∈{1,…,k}. The polynomial f(x) is unique modulo m, and can be obtained by applying the Chinese remainder theorem (over /m) for each coefficient of f(x). This implies that 
      R ≅(/m)/(f(x)),
   for a polynomial f(x) that is irreducible modulo p_i for each i ∈{1,…,k}. Hence, the isomorphisms between such rings can be constructed by constructing isomorphisms between each Galois ring component and then applying the Chinese remainder theorem. Consequently, we can extend the definition of isomorphism problem for such finite rings. Moreover, all the operations to construct an isomorphism are efficient and can be used for practical purposes.
  
  
  
  
  
  § CONCLUSION
   
  
  In this paper, we generalize the finite field isomorphism (FFI) problem to Galois rings, and define the Galois ring isomorphism (GRI) problem. We observe that, as in the case of the FFI problem, the best known techniques for solving the GRI problem is based on the lattice reduction algorithms. We show that the construction of a Galois ring isomorphism can efficiently be done by constructively lifting the isomorphism between corresponding residue fields. 
  
  In <cit.> and <cit.>, we have seen two applications of the FFI problem, namely, a fully homomorphic encryption scheme and a signature scheme, respectively. As a result of the generalization, we note that both the applications can be extended to the case of Galois rings (or more generally to the case of direct products of Galois rings). Consequently, we obtain the same cryptographic primitives over integer modulo rings. One major advantage of working over integer ring modulo 2^s is the efficiency of the cryptographic protocols: performing operations modulo 2^s on CPUs are way better than modulo an s-bit large prime number. 
  
  
  
  § ACKNOWLEDGEMENT
  
  The author would like to thank Gianira Alfarano, Alessandro Neri and Violetta Weger for several useful discussions. 
  This work was supported by Forschungskredit of the University of Zurich grant no. FK-19-080.
  
  plain
  
  
  