Quo Vadis — Galois Ring Isomorphism Attack

Challenge

Two representations of the same Galois ring (R₁ tower extension, R₂ single extension). A secret polynomial P(x) is evaluated at a random point pt₁ ∈ R₁. We submit pt₂ ∈ R₂, get P(pt₂), and must recover coefficients of P(pt₁) in R₁.

Mathematical Foundation

Since R₁ ≅ R₂, let φ: R₁ → R₂ be the isomorphism. Setting pt₂ = φ(pt₁), the server gives coefficients of y = φ(P(pt₁)). This reduces to solving M·x = y (mod 2^k) where M is the matrix representing φ.

• Find roots of defining polynomials of R₁ in R₂ via residue field GF(2^D)
• Newton Lifting: lift roots from Z₂ to Z_{2^k}
• Build matrix M by mapping basis elements through the isomorphism
• Solve linear system over Z_{2^k} using SageMath

Flag