Dot products in Galois rings

\gdef\vec#1{\mathbf#1} \gdef\mat#1{\mathrm#1} \gdef\setn#1{\mathcal#1} \gdef\p#1{\left({#1}\right)}

(These are my notes from studying an idea worked out by Bryan Gillespie)

Galois Rings

Informally, a Galois ring is a generalisation of a Galois field 𝔽_{p^m} to have coefficients from the ring of integers modulo p^s for some s ≥ 1. It inherits much of the structure of the field, and many applications of Galois fields can be generalized to work on Galois rings. This is useful as ℤ_{2^k} can be efficiently implemented on computers.

Definition, existence and uniqueness

Definition. (Wan11 14.1) A Galois ring R is a finite commutative ring with identity such that that the set of its zero divisors with 0 added forms a principal ideal (p) for some prime number p.

Theorem. (Wan11 14.2) The unique maximal ideal of R is (p) and R/(p) is the Galois field 𝔽_{p^m} for some m≥1. The characteristic of R is p^s for some s ≥ 1.

Theorem. (Wan11 14.7) R is uniquely determined (up to isomorphism) by (p,s,m).

Theorem. (Wan11 14.4) The cardinality |R|=p^{s⋅m}.

Theorem. (Wan11 13.9) For any prime p, s ≥ 1 and m ≥ 1 there exists a Galois ring.

We can therefore speak of the Galois ring GR(p^s, m).

Multiplicative group

Theorem. (Wan11 14.9) The group of units R^× has order |R^×| = (p^m - 1)⋅p^{(s-1)⋅m}.

Theorem. An element a ∈ R is a unit if and only if its equivalence class in R/(p)=𝔽_{p^s} does not equal 0.

From this follows a simple method to compute inverses by first testing the reduction mod p against zero and exponentiating the element by |R^×|-1.

x has order (p^m - 1)⋅p^{s-1}

Structure

Theorem. (Wan11 14.6) R is isomorphic to the ring ℤ_{p^s}[x] / (h(x)) for any monic basic polynomial h(x) of degree m over ℤ_{p^s}.

In particular if s=1 then R ≃ 𝔽_{p^m} and if m = 1 then R ≃ ℤ_{p^s}. As such Galois rings generalize over finite fields and integers modulo a prime power. Of particular interest are cases where p=2 which have efficient implementations.

Theorem. (Wan11 14.1) R is a free ℤ_{p^s}-module of rank m.

Theorem. (Wan11 ex. 14.1 p. 367) For 1 ≤ r < s the quotient ring R/(p^r) is isomorphic to GR(p^r, m).

Theorem. (Wan11 14.24) For a positive divisor n of m, R contains a unique subring GR(p^s, n).

p-addic representation

Theorem (Wan11 14.8) There exist a ω ∈ R of order p^m -1 which is a root of a monic basic primitive polynomial h(x) of degree m over ℤ_{p^s} and dividing x^{p^m -1}-1 in ℤ_{p^s}[x]. Let \setn T = \{0, 1, ω, ω^2, …, ω^{p^m - 2}\} be the set of then every element of c ∈ R can be written uniquely in the form c = c_0 + c_1 ⋅ p + c_2 ⋅p^2 + ⋯ + c_{s-1} ⋅ p^{s-1} where c_i ∈ \setn T. Moreover c is a unit if and only if c_0 ≠ 0 and c is a zero divisor or 0 if and only if c_0 = 0.

Note that \setn T, known as the Teichmüller representatives, are a lift from 𝔽_{p^m} to R.

Definition The generalized Frobenius map takes an element in p-addic representations an raises every coefficient to the p-th power: ϕ: c_0 + c_1 ⋅ p + ⋯ + c_{s-1} ⋅ p^{s-1} ↦ c_0^{p} + c_1^{p} ⋅ p + ⋯ + c_{s-1}^{p} ⋅ p^{s-1}

Theorem. (Wan11 14.31) The automorphism group of R is cyclic of order m and generated by the Frobenius automorphism: \operatorname{Aut}_{ℤ_{p^s}}(R) = ⟨ϕ⟩

Bases

Definition. The trace of an element a ∈ R, denoted \operatorname{Tr}(a) and norm, denoted \operatorname{N}(a) are \begin{aligned} \operatorname{Tr}(a) &= \!\!\!\!\!\sum_{i∈[0,m-1]}\!\!\! ϕ^i(a) &\quad \operatorname{N}(a) &= \!\!\!\!\!\prod_{i∈[0,m-1]}\!\!\!\! ϕ^i(a) & \end{aligned}

Theorem. (Wan11 14.34) \begin{aligned} \operatorname{Tr}(a) &∈ ℤ_{p^m} \\ \operatorname{Tr}(a + b) &= \operatorname{Tr}(a) + \operatorname{Tr}(b) \\ \operatorname{Tr}(c ⋅ a) &= c⋅\operatorname{Tr}(a) \\ \operatorname{Tr}(c) &= m ⋅ c \\ \operatorname{Tr}(ϕ(a)) &= \operatorname{Tr}(a) \\ \end{aligned}

Question. Is \operatorname{Tr}(a⋅b) an inner product?

Definition. (Wan11 8.2) Two bases \set{a_1, a_2, …, a_n} and \set{b_1, b_2, …, b_n} are said to be equivalent if there exist an e ∈ 𝔽_p such that a_i = e⋅b_i and weakly equivalent if there exist and e ∈ R such that a_i = e⋅b_i.

Question. What are all the bases of a Galois ring up to permutation and weak equivalence?

Products in Galois Ring Representations

(See also Wan11 p. 164)

Represent R by ℤ_{p^s}[x] / h(x) for some h, then \setn X = \set{ x^i } is the monomial basis that creates an isomorphism with ℤ_{p^s}^m.

The Frobenius automorphism group ϕ becomes a linear operator and can be represented by a matrix \mat F of order m.

Question. What are all the isomorpisms GR(p^s, m) → ℤ_{p^s}^m that can be constructed? We can change h and change the choice of basis. The result must equal the automorphism group

\operatorname{Aut}_{ℤ_{p^s}}(ℤ_{p^s}^m) ≃ \operatorname{GL}_{m}(ℤ_{p^s})

Hypothesis. Changes of basis on ℤ_{p^s}[x] / h(x) are in one-to-one correspondence with matrices \operatorname{GL}_{m}(ℤ_{p^s}).

Hypothesis. The ℤ_{p^s}-module automorphisms are also ring homomorphisms by an appropriate transformation of the bilinear map for ring products.

Theorem. (Wan11 14.32) Given Galois ring R=GR(p^s, m) with subring R'=GR(p^s, n), the automorphism group of R over R' is isomorphic to the automorphism group over their residue fields. \operatorname{Aut}_{R'}(R) ≃ \operatorname{Aut}_{𝔽_{p^n}}(𝔽_{p^m})

So every automorphism of a Galois ring is a power of the generalized Frobenius automorphism.

σ(n) = n^{p^m}

Note. The automorphism group of B over A, denoted \operatorname{Aut}_{A}(B) here following Wan11, is also commonly denoted \operatorname{Aut}(B/ A). When A and B are Galois fields, this group is typically denoted \operatorname{Gal}(B / A).

Under this isomorphism the R-product becomes a symmetric bilinear map ℤ_{p^s}^m × ℤ_{p^s}^m → ℤ_{p^s}^m. Such bilinear maps are uniquely characterized by a rank-3 tensor m ∈ ℤ_{p^s}^{m^3} defined by:

x^k ⋅ x^l = \sum_{r} m_{klr} ⋅ x^r

The m values depend on the choice of h and basis.

The m values are constraint by the automorphism group as the product needs to satisfy

a ⋅ b = ϕ^{-k}(ϕ^k(a) ⋅ ϕ^k(b))

Question. What are other constraints to make this a valid product? It needs to be bilinear, symmetric. Basically needs to satisfy the ring axioms? Distributivity follows from bilinearity. Missing is identity and associativity. What about compatibility with the scalar product?

The ring product operation is a symmetric bilinear map over the module. Given two bases \setn U = \set{\vec u_i} and \setn V = \set{\vec v_i} for R we can represent the product in coordinates as:

a ⋅ b = \sum_k a^{\setn U}_i ⋅ b^{\setn U}_j ⋅ m_{ijk} ⋅ \vec v_k

where a^{\setn U}_i, b^{\setn U}_j ∈ ℤ_{p^s} are coordinates of a, b in basis \setn U and m is a rank-3 tensor over ℤ_{p^s} with coordinates given by

m_{ijk} = (\vec u_i ⋅ \vec u_j)^{\setn V}_k

Observe that each product coordinate (a ⋅ b)^{\setn V}_k is a symmetric bilinear form on the input coordinates. This let's us state our main question:

Question. Which symmetric bilinear forms on ℤ_{p^s}^m can be constructed by appropriate choices of \setn U and \setn V?

Computing Bilinear Forms

Without loss of generality we can focus on the first output coordinate \vec v_0. Given a bilinear form \mat B_{ij}, we need

m_{ij0} = (\vec u_i ⋅ \vec u_j)^{\setn V}_0 = \delta_{ij}

Represent R by ℤ_{p^s}[x] / h(x) for some h, then \setn X = \set{ x^i } is a basis. We can represent the transformation from \setn X to \setn U and \setn V by invertible matrices u_{ij} = (x^i)^{\setn U}_j and v_{ij} = (x^i)^{\setn V}_j.

x^k ⋅ x^l = \sum_{r} m_{klr} ⋅ x^r

In the target bases

\vec u_i = \sum_j u_{ij} ⋅ x^j

where u_{ij} = (\vec u_i)^{\setn X}_j and similarly for \setn V.

x^r = \sum_{q} v_{rq} ⋅ \vec v_q

where v_{rq} = (x^r)^{\setn V}_q. Then

\begin{aligned} \vec u_i ⋅ \vec u_j &= \p{\sum_k u_{ik} ⋅ x^k} ⋅ \p{\sum_l u_{jl} ⋅ x^l} \\ &= \sum_k \sum_l u_{ik} ⋅ u_{jl} ⋅ \p{x^k ⋅ x^l} \\ &= \sum_k \sum_l \sum_r u_{ik} ⋅ u_{jl} ⋅ m_{klr} ⋅ x^r \\ &= \sum_k \sum_l \sum_r \sum_q u_{ik} ⋅ u_{jl} ⋅ m_{klr} ⋅ v_{rq} ⋅ \vec v_q \\ (\vec u_i ⋅ \vec u_j)^{\setn V}_q &= \sum_k \sum_l \sum_r u_{ik} ⋅ u_{jl} ⋅ m_{klr} ⋅ v_{rq} \end{aligned}

This is a polynomial system of equations in unknowns u_{ij} and v_{ij}.

u_i^T ⋅ M_r ⋅ u_j

Example: the Galois ring ℤ_{2^{16}}[x] / (x^4 -x - 1)

In R = ℤ_{2^{16}}[x] / (x^4 -x - 1) with basis \{ x^i \} we have multiplication represented by structure constants

c = \begin{bmatrix}\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0& 1 \\ \end{pmatrix}, \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix} \end{bmatrix} such that x^i⋅x^j = \sum_k c_{ij}^k ⋅ x^k. The order of the multiplicative group |R^×| = 2^{60}⋅3⋅5 with \operatorname{ord}(x) = 2^{15}⋅3⋅5. For k dividing \operatorname{ord}(x) we construct primitive k-th roots of unity ω_k as ω_k = x^\frac{\operatorname{ord}(x)}{k}. In particular the generator of the Teichmüller set is ω_{2^4-1} = 40289 + 46738⋅x + 59713⋅x^2 + 8880⋅x^3 and the Frobenius map ϕ of R over ℤ_{2^{16}} is represented by the matrix \mat F = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 14104 & 36826 & 23545 & 3040 \\ 50161 & 28753 & 57364 & 20500 \\ 21492 & 33826 & 19639 & 36881 \end{bmatrix} such that ϕ(x^i) = \sum_j \mat F_{ij} ⋅ x^j. \mat F generates the automorphism group of the ring. The automorphism group of the module is the general linear group \operatorname{GL}_4(ℤ_{2^{16}}).

\begin{aligned} (\vec u_i ⋅ \vec u_j)^{\setn V}_q &= \sum_k \sum_l \sum_r u_{ik} ⋅ u_{jl} ⋅ m_{klr} ⋅ v_{rq} \\ \end{aligned}

So we need to solve

δ_{ij} = \sum_k \sum_l \sum_r u_{ik} ⋅ u_{jl} ⋅ m_{klr} ⋅ v_{r0}

where the lhs and m_{klr} are constants, and u and v are invertible matrices. Ignoring the invertibility constraint, this is a system of 16 polynomial equations in 20 unknowns of degree 3.

Question. Why are there exactly two solutions when we constrain the matrix to be unitriangular?

Question. Which symmetric bilinear forms can be computed simultaneously?

Question. If we pick two different bases for the input elements the coordinate bilinear forms are no longer symmetric. Which (not necessarily symmetric) bilinear forms can be constructed by an appropriate choice of basis?

Efficient Computation in MPC

The scheme is to be used inside an Shamir Secret Sharing setting. Let (a_0, a_1, … a_n) be valid evaluation points, with the secret stored at a_0, then the secret s is reconstructed from shares s_i as

Claim. Given a Shamir secret sharing with secret evaluation point x_s and party points x_0,…x_{n-1} the parties can locally convert to additive sharing.

This follows from the observation that the Lagrange interpolation formula is a sum over locally computable terms s = \sum_{i∈[1,n]} L_i(x_s) ⋅ s_i

Question. Are the L_i(x_s) guaranteed to be units? Can we therefore always convert locally back from additive to Shamir sharing? Can this be generalized to any linear sharing scheme?

Claim. Given a linear map p:U→V and an additive secret s ∈ U such that s = \sum_i s_i, the parties can locally compute an additive sharing of p(s):

p(s) = p\!\p{\sum_i s_i} = \sum_i p(s_i)

So given a Shamir sharing of s we can locally compute an additive sharing of p(s).

Galois rings among ℤ_{p^s}-algebras

Take ℤ_{p^s}^m, the free ℤ_{p^s}-module of rank m, and a bilinear operation denoted as multiplication to form an algebra A. For a basis \{\vec e_i\} multiplication is uniquely defined by the structure constants c_{ij}^k ∈ ℤ_{p^s} given by \vec e_i ⋅ \vec e_j= \sum_k c_{ij}^k ⋅ \vec e_k

We constrain A to be commutative, unital and associative, which respectively imply

c_{ij}^k = c_{ji}^k \\ \sum_i u_i ⋅ c_{ij}^k = δ_{jk} \\ \sum_l c_{ij}^l ⋅ c_{lk}^m = \sum_l c_{ik}^l ⋅ c_{jl}^m

where u_i are the coordinates of the identity element in the basis.

Question. What are the (additional) requirements for A to be a Galois ring?

Question. What other algebras are suitable for MPC?

To show that A is a Galois ring by the definition above, all that remains is to show that "the set of its zero divisors with 0 added forms a principal ideal (p) for some prime number p". We already have that (p) is an ideal, as this is inherited from ℤ_{p^s}.

References

• Wan11 Zhe-Xian Wan (2011). Finite Fields and Galois Rings.
• Sis20 Virgilio P. Sison (2020). Bases and Automorphism Matrix of the Galoir Ring GR(p^r, m) over ℤ_{p^r}.
• ACD⁺19 Mark Abspoel, Ronald Cramer, Ivan Damgård, Daniel Escudero, Chen Yuan (2019). Efficient Information-Theoretic Secure Multiparty Computation over ℤ/p^kℤ via Galois Rings.
• ACD⁺20 Mark Abspoel, Ronald Cramer, Ivan Damgård, Daniel Escudero, Matthieu Rambaud, Chaoping Xing, Chen Yuan (2019). Asymptotically Good Multiplicative LSSS over Galois Rings and Applications to MPC over ℤ/p^kℤ.

Appendix: Solver

See the full source in galois-dot.rs and associated SageMath notebook galois-dot.ipynb.

To find solutions I wrote a little multi-threaded solver in Rust:

/// Solve polynomial systems of equations over `u64` by linear Hensel lifting.
/// 
/// `eval` should be a function that takes a solution vector and returns the
/// bitwise-or of the polynomial functions at that point.
fn root<const N: usize>(eval: impl Fn([u64; N]) -> u64 + Sync) -> Vec<[u64; N]> {
    let mut solutions = vec![[0; N]];
    for bit in 0..64 {
        println!("Lifting bit {}, initial solutions {}", bit, solutions.len());
        solutions.truncate(1000); // Limit number of candidate solutions to prevent explosion
        solutions = solutions.into_par_iter().flat_map(|solution| {
            (0..(1 << N)).into_par_iter().map(|bit_pattern| {
                std::array::from_fn(|i| solution[i] | (((bit_pattern >> i) & 1) << bit))
            }).filter(|&sol| eval(sol).trailing_zeros() > bit)
            .collect::<Vec<_>>()
        }).collect();
    }
    solutions
}

For example to compute the inverse of 5:

root(|[n]| n.wrapping_mul(5).wrapping_sub(1))

For example to find 2×2 invertible matrices m such that

\begin{aligned} m_{00}⋅ m_{10}^3 &= m_{01} & m_{01}^3 &= 5 & m_{00}^5 &= 9 \end{aligned}

/// Check if a number is a unit by computing $1 - n^{2^{63}}$.
fn is_unit(mut v: Wrapping<u64>) -> Wrapping<u64> {
    (v & Wrapping(1)) ^ Wrapping(1) // Equivalent expression
}

fn equations(v: [u64; 4]) -> u64 {
    let [m00, m01, m10, m11] = v.map(Wrapping);
    let mut lhs = Wrapping(0);
    lhs |= is_unit(m00*m11 - m10*m01); // Determinant is a unit
    lhs |= m00*m10.pow(3) - m01;
    lhs |= m01.pow(3) - Wrapping(5);
    lhs |= m00.pow(5) - Wrapping(9);
    lhs.0
}

println!("Solutions {:?}", root(equations));

There's room for optimization. The is_unit checks can be dismissed after the first bits are found. Linear constraints can be solved first to reduce the number of variables.