Automorphism

An automorphism is a structure-preserving map from a mathematical object to itself that is bijective (invertible). It's essentially an "internal symmetry" of the structure.

General Definition

For a ring $R$, an automorphism $\sigma: R \to R$ must satisfy:

• $\sigma(a + b) = \sigma(a) + \sigma(b)$ (preserves addition)
• $\sigma(a \cdot b) = \sigma(a) \cdot \sigma(b)$ (preserves multiplication)
• $\sigma$ is bijective (one-to-one and onto)

In Cyclotomic Rings (Lattice Crypto Context)

For the ring $\mathbb{Z}_q[X]/(X^d + 1)$ where $d = 2^k$, the automorphisms are specifically:

$\tau_\ell : X \mapsto X^\ell \quad \text{where} \quad \gcd(\ell, 2d) = 1$

This means: replace every $X$ in the polynomial with $X^\ell$, then reduce modulo $(X^d + 1)$.

Why It's Useful in Cryptography

• Key switching: Automorphisms let you transform ciphertexts encrypted under one key to ciphertexts under a related key
• Slot rotations: In packed RLWE (where one ciphertext encodes multiple plaintexts), automorphisms rotate the "slots"
• CDKS packing: Uses automorphisms to create "constructive interference" when merging LWE ciphertexts, ensuring values land in different coefficient positions rather than colliding

Intuition

Think of it as a "rearrangement" of the polynomial's coefficients according to a specific pattern—one that preserves all the algebraic relationships.

The set of all valid automorphisms forms the Galois group of the cyclotomic field, which for $X^d + 1$ has exactly $d$ elements (all odd numbers from 1 to $2d-1$).

Related Concepts

• LWE - Learning With Errors, the foundation of lattice cryptography
• LWE to RLWE Conversion - Uses automorphisms in the Field Trace operation
• CDKS Packing - Uses automorphisms for constructive interference when merging ciphertexts