Galois Keys

Galois keys enable cyclic rotations of the plaintext slots encoded within a single RLWE ciphertext. A rotation by k positions shifts each slot value to slot i+k mod n.

• Left Rotation: Shifts slots toward the most significant position
• Right Rotation: Shifts slots toward the least significant position
• Arbitrary Step Sizes: Any integer step k can be evaluated, provided the corresponding key has been generated

The operation applies a specific automorphism to the underlying ring element, mapping a(X) to a(X^k) modulo the cyclotomic polynomial. This preserves the encrypted state while rearranging the logical data layout.

In encrypted neural networks, convolution operations are implemented using Galois rotations and element-wise multiplication. For a filter of size f, the process requires:

• Rotate the input ciphertext by each offset position in the filter
• Multiply each rotated ciphertext by the corresponding plaintext filter weight
• Accumulate all resulting ciphertexts via homomorphic addition

This transforms a spatial convolution into a series of SIMD-friendly operations. The number of rotations scales linearly with the filter size, making Galois key selection a critical performance parameter for CNN inference under FHE.

Galois keys enable efficient encrypted matrix multiplication by supporting row-major to column-major transformations and diagonal extraction patterns.

• Row Rotation: Shifts entire rows within the packed matrix representation
• Column Extraction: Uses specific rotation patterns to isolate columns for dot-product computation
• Transposition: Achieved through a sequence of structured rotations and masking operations

This capability is fundamental for implementing fully connected layers and attention mechanisms in transformer architectures operating on encrypted data. The choice of encoding (row-packed vs. column-packed) determines the exact rotation schedule required.

Galois keys are generated by the data owner using their secret key and published as part of the public evaluation key set. Each distinct rotation step k requires a separate key.

• Key Material: A Galois key is a special key-switching key that transforms a ciphertext under s(X^k) back to s(X)
• Storage Cost: Each key is approximately the size of a relinearization key, typically several megabytes
• Security Property: Possession of Galois keys does not enable decryption; they only permit slot permutation

The set of required rotation indices must be determined before computation begins, as generating new keys requires access to the secret key.

Galois rotation is a specific instance of the key switching primitive. The operation transforms a ciphertext encrypted under the automorphed secret key s' = s(X^k) back to the original secret key s(X).

• Underlying Mechanism: Identical to the key switching used in relinearization and modulus switching
• Decomposition Base: The key switching decomposition base affects both noise growth and computational cost
• Noise Addition: Each rotation adds a small, additive noise term proportional to the decomposition parameters

This shared mechanism means optimizations to key switching (such as hybrid key switching or GPU acceleration) directly benefit Galois rotation performance.

Galois rotations are among the most expensive operations in HE computation, typically dominating the runtime of encrypted CNN inference.

• NTT Operations: Each rotation requires multiple Number Theoretic Transform passes
• Key Count Trade-off: Generating more keys increases storage but reduces online computation by avoiding rotation decomposition
• Decomposition Strategy: A rotation by k can be decomposed into a sequence of rotations by powers of two, trading key count for latency
• Hardware Acceleration: Modern FHE libraries leverage GPU and FPGA acceleration specifically for the NTT-heavy rotation kernel

Optimal key selection is a storage-computation trade-off that must be tuned per model architecture.

A technique that encodes multiple plaintext values into a single ciphertext, enabling SIMD parallelism. Galois keys are the cryptographic mechanism that allows individual slots within this packed structure to be rotated and permuted without decryption.

• Encodes vectors of up to 2^15 values in a single ciphertext
• Amortizes computation cost across thousands of operations
• Requires Galois keys for any non-trivial data movement between slots

A cryptographic operation that transforms a ciphertext encrypted under one secret key into a ciphertext encrypting the same message under a different secret key. Galois keys are a specialized form of key-switching key that enable automorphic mappings on polynomial rings.

• Underlies relinearization, rotation, and conjugation
• Requires publishing evaluation keys without compromising the secret key
• Computational cost scales with the size of the key-switching key matrix

A key-switching procedure that reduces a ciphertext after multiplication back to two ring elements, preventing quadratic growth in ciphertext dimension. Uses a relinearization key (a type of evaluation key) to convert the quadratic term.

• Without relinearization, each multiplication triples ciphertext size
• Essential for deep circuits like neural network inference
• Shares underlying mathematical structure with Galois key operations

The ability to perform a single homomorphic operation on a packed ciphertext that simultaneously applies to all encoded plaintext slots. Galois keys unlock the full potential of SIMD by enabling cross-slot data movement.

• Addition and multiplication are natively SIMD-parallel
• Convolution requires Galois rotations to align filter weights with input patches
• Achieves amortized throughput of thousands of operations per ciphertext operation

A leveled homomorphic encryption scheme optimized for approximate fixed-point arithmetic on real numbers. CKKS heavily relies on Galois keys for implementing matrix multiplication and convolution in encrypted neural networks.

• Supports rescaling to manage precision after multiplication
• Native packing of complex numbers into ciphertext slots
• Galois rotations enable efficient dot product computation across packed weight matrices