Galois Key

The core function of a Galois Key is to perform cyclic rotations on encrypted vectors. This operation shifts the positions of encrypted values within a ciphertext, which is essential for implementing non-linear functions (e.g., comparisons, ReLU) and complex algorithms (e.g., sorting, matrix operations) in FHE.

Galois Keys are not manually created. They are automatically generated by the FHE scheme's key generation algorithm alongside the secret and public keys. This process uses the secret key to produce a set of keys, each corresponding to a specific rotation step (e.g., rotate by 1, rotate by 2).

Unlike other FHE operations that increase noise and eventually require bootstrapping, rotations using a Galois Key are typically noise-neutral. This makes them highly efficient and allows for many consecutive rotations without degrading the ciphertext's ability to be decrypted correctly.

Galois Keys are critical for Single Instruction, Multiple Data (SIMD) batching in FHE. By rotating encrypted data slots, a single operation can be applied to different data elements, dramatically improving computational throughput. This is fundamental for practical, performant FHE applications.

The exact structure and generation of Galois Keys depend on the underlying FHE scheme. Prominent examples include:

• CKKS: Uses Galois Keys for efficient rotations on complex numbers.
• BFV/BGV: Employs them for modular arithmetic on integers.
• TFHE: Uses a specialized variant called a Bootstrapping Key that also handles rotations.

Galois Keys contribute to the significant public key size in FHE systems. A full set for all possible rotations can be large (megabytes to gigabytes). Schemes often optimize by generating keys only for necessary rotation steps, trading off flexibility for reduced storage and bandwidth requirements.

The primary function of a Galois Key is to facilitate the homomorphic multiplication of two ciphertexts within an FHE scheme, such as CKKS or BFV. This operation, combined with homomorphic addition, allows for the evaluation of arbitrary functions (like polynomials) on encrypted data without decryption. It is a core component that makes privacy-preserving computation possible.

In the CKKS scheme, Galois Keys are used for operations that do not increase the inherent noise in a ciphertext as severely as regular multiplication. They enable critical functions like ciphertext rotation (shifting encrypted data slots) and complex conjugation, which are essential for efficient linear algebra operations (e.g., matrix multiplications, dot products) on encrypted vectors.

A key application is in private ML inference. A server holding a Galois Key can perform encrypted evaluations of a neural network's activation functions and layers on a client's encrypted data. This allows services like medical diagnosis or financial risk assessment without exposing the raw input data or the model's proprietary weights.

Galois Keys enable analytics on aggregated encrypted data. For example, a data aggregator can compute encrypted statistics (means, variances) or run regression models on sensitive datasets from multiple sources (e.g., hospitals, banks) without ever decrypting the individual data points, preserving confidentiality throughout the computation.

In confidential blockchain networks, Galois Keys are used within zk-FHE or FHE-based smart contracts. They allow contracts to process private user inputs (e.g., encrypted balances or bids) and produce a verifiable, encrypted output, enabling use cases like private decentralized finance (DeFi) and sealed-bid auctions.

It is crucial to distinguish a Galois Key from a Relinearization Key. While both are used after multiplication:

• A Galois Key is for operations that manipulate data within a single ciphertext vector (e.g., rotations).
• A Relinearization Key is for reducing the size of a ciphertext back to its original form after multiplication, controlling noise growth. They are often used in tandem for efficient circuit evaluation.

The security of the entire FHE system depends on the proper generation of the Galois Key. It must be derived from a strong, secret master secret key. If this process is compromised or uses weak randomness, an attacker could potentially decrypt all processed data. This creates a single point of failure in the cryptographic setup.

If a Galois Key is leaked, it does not directly reveal the encrypted data. However, it allows an attacker to perform unlimited homomorphic operations, potentially enabling ciphertext manipulation attacks. For example, they could create malformed ciphertexts to probe the system or amplify noise to cause decryption failures, compromising data integrity.

Every homomorphic multiplication using the Galois Key increases the noise within the ciphertext. Unchecked noise growth will eventually corrupt the data, making it undecryptable. The security model requires precise noise budgeting and potentially bootstrapping operations. A flawed implementation can lead to silent data corruption or necessitate insecure parameter choices to accommodate noise.

The security of the Galois Key is based on the hardness of Ring Learning With Errors (RLWE) problems. Choosing parameters (like polynomial degree and ciphertext modulus) involves a critical trade-off:

• Weak parameters risk cryptanalysis and practical attacks.
• Overly strong parameters cause massive performance overhead, making the system unusable. Parameters must be vetted against current cryptanalytic benchmarks.

Many FHE schemes require a trusted setup to generate the Galois Key and other public parameters. This ceremony must be performed correctly and the toxic waste securely discarded. To mitigate this risk, research focuses on trustless setup models or Multi-Party Computation (MPC)-based key generation, where no single party knows the complete secret.

Even with perfect mathematical security, the physical implementation is vulnerable. Operations using the Galois Key can leak information via:

• Timing attacks
• Power analysis
• Cache attacks Secure implementation requires constant-time algorithms and hardware-level protections to prevent extraction of the secret key or data.