Relinearization Key

A relinearization key is a public parameter in Fully Homomorphic Encryption (FHE) schemes that reduces the size of a ciphertext after multiplication. When two encrypted values are multiplied, the resulting ciphertext's dimension grows. The relinearization key allows anyone to transform this larger ciphertext back to its original, manageable size without decrypting it, preserving the homomorphic property.

• Purpose: Maintains ciphertext size and computational efficiency.
• Mechanism: Uses a technique called key switching to convert ciphertext elements encrypted under a secret key s into elements encrypted under a different key s'.

This key is essential for enabling the multiplicative homomorphism in FHE schemes like BGV, BFV, and CKKS. Without relinearization, each multiplication would exponentially increase ciphertext size, making computations impractical after just a few operations.

• Process Flow: Enc(A) * Enc(B) → Large Ciphertext → Apply Relinearization Key → Standard-sized Ciphertext (Enc(A*B)).
• Security: The key is generated using the secret key but is designed to not leak information about it, relying on the Learning With Errors (LWE) or Ring-LWE hardness assumptions.

In blockchain applications, relinearization keys are crucial for privacy-preserving smart contracts and zero-knowledge proofs (ZKPs) that use FHE. They allow complex computations (like checking balances or executing trades) on encrypted state data within a virtual machine.

• Example: A private DEX could use FHE to match orders on encrypted prices. The relinearization key enables the repeated multiplications needed for the matching algorithm.
• Protocols: Found in FHE-based rollups and confidential DeFi protocols where transaction logic must remain private.

The generation and use of relinearization keys introduce significant performance overhead and key management challenges. They are large data structures, and their security is paramount.

• Size: Can be megabytes or gigabytes, impacting storage and bandwidth.
• Generation: Computationally intensive, typically performed during a trusted setup phase for a specific circuit depth.
• Rotation: In some schemes, a new key is required if the computation exceeds a predefined multiplicative depth, complicating long-running computations.

Relinearization is often discussed alongside bootstrapping, another key FHE operation. They solve different problems:

• Relinearization: Manages ciphertext size growth after multiplication.
• Bootstrapping: Manages ciphertext noise growth after operations, effectively "resetting" the noise level to allow unlimited computations.

Most practical FHE applications require both techniques to be usable. A circuit's multiplicative depth limit is often defined by the available relinearization keys before bootstrapping must be invoked.

The primary security function of a relinearization key is to control the ciphertext size after multiplication. Without it, each multiplication in FHE schemes (like BGV, BFV, or CKKS) would increase the dimension of the ciphertext, making it grow exponentially and quickly becoming unusable. The key allows the system to 'relinearize' or reduce the ciphertext back to its original size, but this process introduces a small amount of controlled noise that must be managed to prevent decryption failure.

Relinearization is one of the most computationally expensive operations in FHE. The process involves complex polynomial arithmetic and operations in a high-dimensional space. The performance impact is measured in:

• Latency: Can add milliseconds to seconds per operation.
• Throughput: Limits the number of multiplications per second.
• Key Size: The relinearization key itself is large (often megabytes), impacting memory usage and network transmission in distributed systems.

The relinearization key is generated from the secret key and is typically made public. This introduces specific trust assumptions:

• Who holds the secret key? In a client-server model, the client generates the keys, keeping the secret key private while sharing the relinearization key with the server. The server cannot decrypt data but can perform computations.
• Security Reduction: The security of the scheme relies on the hardness of the Ring Learning With Errors (RLWE) problem, even when the adversary has access to the relinearization key.

Every FHE operation, especially multiplication followed by relinearization, adds noise to the ciphertext. The relinearization key must be calibrated to ensure:

• Correct Decryption: The total noise after a circuit of operations stays below a threshold.
• Bootstrapping: If the noise budget is exhausted, a bootstrapping operation is required to reset it, which is even more expensive than relinearization. Proper parameter selection for the relinearization key directly influences how often bootstrapping is needed.

Implementing relinearization securely requires attention to cryptographic engineering details:

• Constant-Time Algorithms: Operations must execute in constant time to prevent timing attacks that could leak information about the secret key or data.
• Key Rotation: In some advanced schemes, relinearization keys may need periodic rotation to maintain long-term security, adding operational complexity.
• Protocol Integration: In multi-party computation (MPC) or threshold FHE, the generation and use of relinearization keys become distributed protocols, introducing new coordination and security challenges.

Choosing parameters for the relinearization key involves a direct security-performance trade-off:

• Higher Security Level: Requires larger polynomial rings and bigger keys, increasing computation time and memory footprint.
• Desired Computation Depth: The number of sequential multiplications supported (multiplicative depth) is determined by initial parameters, including those for relinearization. A deeper circuit requires a larger initial noise budget, impacting key size and performance.
• Real-world Impact: This trade-off forces developers to precisely model their application's computational needs against target security benchmarks (e.g., 128-bit security).

A noise management technique in FHE that refreshes a ciphertext, reducing the accumulated noise from homomorphic operations to allow for unlimited computations. It is often more computationally expensive than relinearization.

• Purpose: Resets the noise level of a ciphertext.
• Relation: While relinearization manages ciphertext size, bootstrapping manages ciphertext noise, making them complementary operations in an FHE circuit.

The cryptographic process of converting a ciphertext encrypted under one secret key into a ciphertext encrypting the same message under a different secret key, without decryption. Relinearization is a specific, common form of key switching.

• Core Mechanism: Uses an evaluation key (like a relinearization key) to perform the transformation.
• Application: Essential for multi-key FHE and secure multi-party computation protocols.

A widely used FHE scheme (Cheon-Kim-Kim-Song) optimized for approximate arithmetic on real or complex numbers. It relies heavily on relinearization after multiplication.

• Use Case: Ideal for privacy-preserving machine learning and data analytics.
• Operation Flow: A CKKS multiplication produces a ciphertext with three polynomial components; relinearization reduces this back to two, controlling size growth.

A major FHE scheme (Brakerski-Fan-Vercauteren) designed for exact integer arithmetic. Like CKKS, it requires relinearization to maintain ciphertext size after multiplication.

• Use Case: Suited for applications requiring precise integer calculations on encrypted data.
• Comparison: While the mathematical rings differ, the relinearization step serves the same fundamental purpose in both BFV and CKKS.

Public parameters in FHE that enable specific homomorphic operations without revealing the secret key. A relinearization key is a primary type of evaluation key.

• Function: Allow third parties (e.g., cloud servers) to perform computations on encrypted data.
• Security: These keys are generated from the secret key but are designed not to compromise it.

A space optimization technique (batching) that encodes multiple plaintext values into a single ciphertext, allowing for Single Instruction, Multiple Data (SIMD) operations. Relinearization operates on these packed ciphertexts.

• Efficiency: Enables parallel homomorphic operations on entire vectors of data.
• Interaction: Relinearization is applied to the packed ciphertext after a multiplication, keeping the packed structure intact for subsequent operations.