automorphism — Galois group action on R_q

the Galois group of the cyclotomic polynomial Phi_{2n} acts on R_q by permuting the variable x. these automorphisms are the algebraic engine behind key switching, slot rotation, and SIMD operations in FHE.

the Galois group

the 2n-th cyclotomic field has Galois group (Z/2n)* — the integers coprime to 2n, under multiplication mod 2n. since n is a power of 2, the group has order n and is generated by 5:

Gal(Q(ζ_{2n}) / Q) ≅ (Z/2nZ)*

generators: {5, -1}
  5 generates the odd part (cyclic of order n/2)
  -1 gives the conjugation automorphism

group size: φ(2n) = n

the automorphism σ_k

each group element k in (Z/2nZ)* defines an automorphism:

σ_k: R_q → R_q
σ_k: x ↦ x^k

on a polynomial a(x) = Σ a_i x^i:
  σ_k(a)(x) = a(x^k) = Σ a_i x^{ik}

the standard generator is 5. the automorphisms σ_{5^0}, σ_{5^1}, ..., σ_{5^{n/2-1}} together with conjugation σ_{-1} generate the full group.

action on coefficient form

applying σ_k in coefficient form requires remapping indices with conditional negation from the x^n + 1 reduction:

automorphism_coeff(a: RingElement, k: usize) → RingElement:
  assert k is odd and 1 <= k < 2n
  for i in 0..n:
    j = (i * k) mod 2n
    if j < n:
      result[j] = a[i]
    else:
      result[j - n] = -a[i]    // x^n = -1 in R_q

cost: n index computations + at most n conditional negations. no field multiplications.

action on NTT form

in NTT form, an automorphism is a pure permutation of evaluation points. the NTT evaluates at ψ^{2j+1} for j = 0..n-1. applying σ_k maps evaluation point ψ^{2j+1} to ψ^{k(2j+1)}, which is another evaluation point in the set:

automorphism_ntt(a_ntt: RingElement, k: usize) → RingElement:
  for j in 0..n:
    target = index_of(k * (2*j + 1) mod 2n)
    result[target] = a_ntt[j]

cost: n index lookups. zero field arithmetic. this is why FHE implementations keep ciphertexts in NTT form — automorphisms become free permutations.

precomputed permutation tables

for each automorphism σ_k, precompute the permutation:

perm_k[j] = index_of(k * (2*bit_rev(j) + 1) mod 2n)    for NTT form

one table per automorphism, n entries each. at n = 1024 with 512 automorphisms, total storage is 512 * 1024 * 2 bytes = 1 MiB (using u16 indices). this is a one-time cost, amortized over the entire FHE computation.

key switching and automorphisms

in FHE, applying an automorphism to a ciphertext requires a key-switching step:

1. apply σ_k to both components of ciphertext (c0, c1)
2. key-switch c1 back using the evaluation key evk_k

step 1 is the automorphism (free in NTT form). step 2 is the expensive part — it involves gadget decomposition and ring multiplications. jali provides step 1; mudra::veil provides step 2.

Frobenius automorphism

the special case k = p (the Frobenius) raises every coefficient to the p-th power. over F_p this is the identity on coefficients but permutes the NTT slots. the Frobenius and its iterates generate the decomposition group, used in bootstrapping.

jali/specs/automorphism.md