Bridges connecting Encryption Schemes

1. Problem Statement

The paper addresses the challenge of securely transforming ciphertexts from one encryption scheme ($S_1$) to another ($S_2$) without decrypting them. While Proxy Re-Encryption (PRE) allows switching keys within the same scheme, and Universal Proxy Re-Encryption attempts to switch between arbitrary schemes, existing general methods often rely on heavy cryptographic primitives like indistinguishability obfuscation, making them impractical.

The authors focus on unidirectional transformations between two distinct encryption schemes, termed Bridges. These are crucial for:

• Hybrid Homomorphic Encryption: Converting symmetric ciphertexts into homomorphic ones to allow computation on encrypted data.
• Encryption Switching Protocols (ESP): Enabling 2-party computation by switching between additive and multiplicative homomorphic schemes.
• Bootstrapping: Generalizing Gentry's "Recrypt" procedure, which is essentially a bridge from a scheme to itself.

The core problem is to formally define these bridges, provide a general construction method, and rigorously analyze their security (specifically IND-CPA) without relying on ad-hoc assumptions.

2. Methodology and Definitions

2.1 Definition of a Bridge

A bridge $B_{\iota, f}$ from scheme $S_1$ to $S_2$ consists of three components:

1. Injective Mapping ($\iota$): A polynomial-time computable, injective function mapping the plaintext space of $S_1$ ($P_1$) to $P_2$, with an efficiently computable inverse on its image.
2. Bridge Key Generation: A PPT algorithm that takes $S_1$'s secret key ($sk_1$) and generates a secret key for $S_2$ ($sk_2$) and a Bridge Key ($bk$). The $bk$ typically contains encryptions of bits of $sk_1$ under $S_2$'s public key.
3. Transformation Algorithm ($f$): A PPT algorithm that takes $bk$ and a ciphertext $c_1 \in C_1$ and outputs $c_2 \in C_2$.

Correctness Condition:
$$\Pr[\text{Dec}_2(sk_2, f(bk, \text{Enc}_1(pk_1, m))) = \iota(m)] = 1 - \text{negl}(\lambda)$$

2.2 Security Framework

The authors define the security of a bridge by associating it with a specific Associated Encryption Scheme ($G_f$):

• Plaintext Space: $P_1$.
• Ciphertext Space: $C_1 \times C_2$.
• Key Generation: Generates $(sk_1, pk_1, sk_2, pk_2, bk)$. The secret key is $(sk_1, sk_2)$, and the public key is $(pk_1, pk_2, bk)$.
• Encryption: Encrypts $m$ as $(a, f(bk, b))$, where $a, b \leftarrow \text{Enc}_1(pk_1, m)$.
• Decryption: Uses $sk_1$ to decrypt the first component $a$.

The IND-CPA security of the bridge is defined as the IND-CPA security of this associated scheme $G_f$.

3. Key Contributions

3.1 General Security Theorem (Theorem 2)

The paper proves that the security of a bridge reduces to the security of the source scheme ($S_1$) plus a technical condition.

• Theorem: If $S_1$ is IND-CPA secure, and the distribution of the bridge key components (specifically the triple $(pk_1, pk_2, bk)$) is computationally indistinguishable from a "fake" distribution where $bk$ encrypts a fixed value (e.g., 0) rather than the secret key bits, then the bridge is IND-CPA secure.
• Significance: This provides a modular security proof. One does not need to prove the security of the complex transformation $f$ from scratch; one only needs to prove that the bridge key does not leak information about $sk_1$ beyond what is already implied by the security of $S_1$.

3.2 Gentry's Recipe (General Construction)

Inspired by Gentry's bootstrapping, the authors propose a general recipe to construct bridges from any scheme $S$ to any somewhat homomorphic encryption (SHE) or fully homomorphic encryption (FHE) scheme $H$:

1. Embedding: Map $P_S$ into the plaintext ring of $H$ ($P_H$).
2. Key Encryption: The bridge key $bk$ consists of encryptions of the bits of $sk_S$ under $pk_H$.
3. Homomorphic Decryption: The transformation $f$ homomorphically evaluates the decryption circuit of $S$ using the encrypted bits of $sk_S$ (from $bk$) and the encrypted bits of the ciphertext $c_S$ (converted to $P_H$).
4. Result: The output is an encryption of the plaintext under $H$.

Theorem 3: If both $S$ and $H$ are IND-CPA secure, then any bridge constructed via Gentry's recipe is IND-CPA secure. This is proven by showing that the "fake" bridge key (encrypting zeros) is indistinguishable from the real one due to the IND-CPA security of $H$.

3.2.1 Variants and Non-Gentry Bridges

• Product Schemes: The authors show how to construct bridges using product schemes ($H^p$) to handle vector-valued decryption circuits.
• Entangled Schemes (Empty Bridge Key): The paper presents a bridge between the Goldwasser-Micali (GM) and Sander-Young-Yung (SYY) schemes where the bridge key is empty (the secret keys are identical). This demonstrates that bridges can exist without the "key encryption" step if the schemes share structural properties (entanglement).

4. Results and Experiments

4.1 Theoretical Results

• Security Reduction: The paper establishes that the security of the bridge is strictly tied to the source scheme's security and the indistinguishability of the bridge key.
• Equivalence: The authors show that for honest players, their definition of bridge security is equivalent to Cohen's HRA (Homomorphic Re-Encryption Attack) security, rendering Cohen's simulatability theorem vacuous in this specific context.

4.2 Experimental Evaluation

The authors implemented bridges using the CSGN scheme (a monoid-based encryption) as the source and various FHE schemes (BGV, BFV, TFHE) as targets.

• Four Variants: They constructed four different bridges from CSGN to FHE, representing the decryption circuit of CSGN in four distinct ways (e.g., using standard basis vectors, polynomial representations, or permutation matrices).
• Performance:
  • Hybrid Approach: For monomials with high degrees, the hybrid approach (encrypt in CSGN $\to$ bridge to FHE) outperforms direct FHE evaluation. This is because CSGN multiplication is extremely cheap, and the bridge handles the noise growth efficiently.
  • Thresholds: The experiments identified degree thresholds where the bridge becomes faster than native FHE evaluation.
  • GM-SYY Bridge: They implemented the "empty key" bridge between GM and SYY to evaluate comparison circuits. The results showed linear scaling with input size, validating the practicality of entangled bridges for specific operations like equality checks.

5. Significance and Conclusion

• Formalization: The paper provides the first rigorous categorical definition and security analysis of "bridges" between arbitrary encryption schemes, moving beyond the specific case of Proxy Re-Encryption.
• Unified View: It unifies concepts like Gentry's bootstrapping, key switching, and encryption switching protocols under a single framework.
• Practicality: By proving that bridges can be constructed securely using standard IND-CPA assumptions (without obfuscation), the paper opens the door for efficient hybrid encryption systems. This is particularly relevant for Hybrid Homomorphic Encryption, where data is encrypted with a fast symmetric cipher and then "bridged" to an FHE scheme for computation.
• New Primitive: The concept of "Entangled Schemes" (bridges with empty keys) suggests a new area of research into the structural relationships between different cryptosystems.

In summary, the paper successfully bridges the gap between theoretical category theory and practical cryptographic engineering, offering a secure, generalizable method to switch between encryption schemes, thereby optimizing performance in complex homomorphic computation scenarios.