Modification to Fully Homomorphic Modified Rivest Scheme

This paper introduces the Fully Homomorphic Modified Rivest Scheme (FHMRS), identifies a specific security vulnerability within it, and proposes a modified version (mFHMRS) to resolve that issue.

The Gist

Imagine you have a magical Locked Box that allows you to do math on the contents without ever opening it. This is the core idea of Fully Homomorphic Encryption (FHE). It's like having a sealed envelope where you can add numbers or multiply them, and when you finally open it, the result is correct, even though you never saw the original numbers.

This paper discusses a specific type of magical box called the Modified Rivest Scheme, finds a hole in its security, and then builds a stronger, upgraded version called mFHMRS.

Here is the story of the paper, broken down into simple concepts:

1. The Original Idea: The "Two-Key" Magic Box (FHMRS)

The original scheme (FHMRS) was like a secret recipe for locking messages.

• How it worked: To lock a message (like the number 5), the system took the number, added a secret "noise" ingredient (a random number multiplied by a secret prime), and then split the result into two pieces using a mathematical trick called the Chinese Remainder Theorem (CRT).
• The Analogy: Imagine you have a secret number. You add a secret amount of salt to it, then you pour the mixture into two different buckets (Bucket A and Bucket B). You send the buckets to a cloud server. The server can mix the contents of Bucket A with another Bucket A, and Bucket B with another Bucket B, without ever knowing what the original number was.
• The Catch: To unlock it later, you need the secret recipe (the prime numbers) to mix the buckets back together and wash away the salt.

2. The Problem: The "Spy" with a Cheat Sheet

The authors realized the original box had a fatal flaw. It was vulnerable to a Known Plaintext Attack.

• The Scenario: Imagine a spy who knows what you put in the box (e.g., "I encrypted the number 5") and sees the result (the two buckets).
• The Flaw: In the original design, if the spy had two examples (Message 5 and Message 10) and their corresponding locked buckets, they could do some simple math (subtracting the known message from the locked result). This subtraction would strip away the message and leave only the "noise" (the secret salt).
• The Result: By finding the "Greatest Common Divisor" (a mathematical way of finding the shared factor) of these two noise leftovers, the spy could easily figure out the Secret Prime Number (u). Once they had that, they could unlock any box. It was like finding the master key by looking at two keys that were made with the same mold.

3. The Solution: The "Multi-Compartment" Fortress (mFHMRS)

To fix this, the authors built a new, upgraded system called mFHMRS. They didn't just patch the hole; they redesigned the whole box.

Key Changes:

1. More Buckets (Shares): Instead of splitting the secret into just two buckets, they split it into many buckets (let's say $N+S$ buckets).
   • Analogy: Instead of giving a spy two buckets to analyze, you give them a warehouse full of buckets. Even if they know the message, trying to reverse-engineer the secret from so many different pieces is like trying to guess a specific grain of sand on a beach by looking at a handful of sand.
2. Bigger Secrets: They made the secret prime numbers much larger and more complex.
   • Analogy: The "salt" isn't just a pinch anymore; it's a massive, complex spice blend that changes every time.
3. The "Noise" Guard: They ensured the random "noise" added to the message is large enough and unpredictable enough that even if a spy tries to solve a system of equations (like a math puzzle), the puzzle has too many missing pieces to solve.

4. How the New System Works (The Magic)

In the new mFHMRS:

• Encryption: You take your message, add a huge amount of secret noise, and split it into many shares (buckets).
• Homomorphic Math: The server can still add or multiply these buckets together.
  • Addition: It's like pouring Bucket A from Box 1 into Bucket A from Box 2. The math works out perfectly.
  • Multiplication: It's like mixing the contents of the buckets. The math gets bigger, but the system is designed to handle the growth so the final result doesn't overflow the bucket.
• Decryption: You take all the buckets back, use your secret recipe (the many prime numbers) to reconstruct the original mixture, and then simply "wash away" the noise (modular reduction) to reveal the final answer.

5. Why is it Safe Now? (Security Analysis)

The paper runs through a checklist of how a hacker might try to break it:

• Brute Force: Trying every possible combination of keys? The authors calculated that even with supercomputers, it would take longer than the age of the universe to guess the right keys.
• Lattice Attacks: This is a fancy math attack where hackers try to find a pattern in the noise. The authors proved that because they split the data into so many parts and made the numbers so large, the "patterns" are too messy to find. It's like trying to find a straight line in a hurricane.
• Equation Solving: Even if a hacker knows the message and the result, the new system creates so many variables (random numbers) that the math equations have infinite solutions, making it impossible to pinpoint the secret key.

Summary

The Paper in a Nutshell:
The authors found that an old "magic math box" was too easy for spies to crack if they knew what was inside. They fixed it by splitting the secret into many more pieces and making the ingredients much bigger and more random. Now, even if a spy knows the message and sees the locked box, they are stuck in a maze of math that is impossible to solve without the master key.

The Takeaway:
It's a blueprint for a safer way to do private calculations in the cloud, ensuring that your data remains secret even while it's being processed.

Technical Summary

Here is a detailed technical summary of the paper "Modification to Fully Homomorphic Modified Rivest Scheme" by Sona Alex and Bian Yang.

1. Problem Statement

The paper addresses a critical security vulnerability in the Fully Homomorphic Modified Rivest Scheme (FHMRS), a symmetric-key-based fully homomorphic encryption (FHE) scheme.

• The Vulnerability: The original FHMRS is susceptible to a Known Plaintext Attack (KPA) when it supports multiplicative homomorphism.
• The Mechanism of Attack: In the original scheme, the encryption involves modular reduction of the term $(m_i + g_i \cdot u)$ by two primes $p$ and $q$. The authors demonstrate that if the modulus $n = p \times q$ is sufficiently large to support $N$ consecutive multiplications, the size of $p$ and $q$ becomes larger than the term $(m_i + g_i \cdot u)$. Consequently, the modular reduction becomes redundant, and the ciphertext effectively reveals the value $(m_i + g_i \cdot u)$.
• The Consequence: If an attacker possesses a single plaintext-ciphertext pair $(m, c)$, they can compute $c - m = g \cdot u$. By obtaining a second pair, they can compute the Greatest Common Divisor (GCD) of the differences to recover the secret prime $u$, thereby breaking the entire scheme.

2. Methodology: Modified FHMRS (mFHMRS)

To mitigate the KPA, the authors propose a modified scheme called mFHMRS. The core methodology involves shifting from a two-prime structure to a multi-prime structure and adjusting the key generation parameters to ensure the ciphertext shares do not reveal the underlying linear relationship.

Key Modifications:

1. Multi-Prime Secret Key Generation:

   • Instead of two primes ($p, q$), the scheme generates $N+S$ primes ($p_1, p_2, \dots, p_{N+S}$) and a secret prime $u$.
   • The modulus $n$ is the product of all these primes: $n = p_1 \times p_2 \times \dots \times p_{N+S}$.
   • The number of primes ($N+S$) is determined by the supported number of multiplications ($N$) and additions ($A$).

2. Encryption Process:

   • The message $m_i$ is encrypted using the Chinese Remainder Theorem (CRT) across all $N+S$ primes.
   • Ciphertext $c_i$ is a tuple of shares: $c_i = (c_{i1}, c_{i2}, \dots, c_{i(N+S)})$, where $c_{ij} = (m_i + g_i \cdot u) \pmod{p_j}$.
   • Crucially, the size of the primes $p_j$ is carefully constrained so that the modular reduction is active (i.e., the result is not the raw value), preventing the direct recovery of $g_i \cdot u$.

3. Homomorphic Operations:

   • The scheme supports homomorphic addition, subtraction, constant addition, constant multiplication, and multiplication.
   • Operations are performed component-wise on the ciphertext shares (e.g., $c_{add} = (c_{1j} + c_{2j}) \pmod{p_j}$).
   • No modular reduction is performed during homomorphic operations; the reduction occurs only during decryption.

4. Decryption Process:

   • The receiver uses CRT to reconstruct the full value $M' = m_i + g_i \cdot u$ from the shares.
   • The final message is retrieved by computing $m_i = M' \pmod u$.

3. Key Contributions

• Identification of KPA: The paper formally identifies and mathematically proves the vulnerability in the original FHMRS where large modulus sizes required for deep circuits inadvertently nullify the security provided by modular reduction.
• Parameter Constraints for Security: The authors derive rigorous mathematical constraints for the bit-lengths of the secret parameters ($p_i, u, g_i$) to ensure:
  • Correctness: The reconstructed value before the final mod $u$ operation must be less than $n$.
  • Security: The parameters must be large enough to prevent brute-force, lattice-based, and linear equation attacks.
  • Specific Constraint: The random number $g_i$ must satisfy $l_g \ge \lambda/4$ (where $\lambda$ is the security parameter) to prevent attacks based on solving linear equations.
• Security Analysis: The paper provides a comprehensive security analysis of mFHMRS against:
  • Brute-force attacks: Analyzing the effective key space size.
  • Lattice-based attacks (LLL): Demonstrating that the error terms in the lattice construction are too large for the LLL algorithm to recover the secret vectors.
  • Linear Equation Attacks: Showing that with multiple ciphertexts, the system of equations remains underdetermined or requires an infeasible number of trials to solve for $u$ and $p_i$.

4. Results and Performance

• Security Verification: The analysis confirms that mFHMRS resists the specific KPA that broke the original scheme. The introduction of multiple primes and specific bit-length constraints ensures that $c_{ij} \neq (m_i + g_i \cdot u)$, making GCD attacks impossible.
• Ciphertext Expansion:
  • The scheme incurs a ciphertext expansion proportional to the number of primes ($N+S$).
  • Example 1 (Single Multiplication): With $\lambda=128$, $N=1$, $A=20$, the scheme uses 3 primes ($S=2$) of 128 bits and a 130-bit $u$. The ciphertext size is approximately 384 bits.
  • Example 2 (Deep Circuit): For $N=14$ multiplications, the scheme uses 6 primes ($S=5$) of 180 bits. The ciphertext size increases to approximately 3420 bits.
• Decryption Correctness: The paper proves that if the bit-lengths of $p_i$ and $u$ satisfy the derived inequalities (e.g., $l_{p_i} \ge \frac{(N+1)(l_u + l_g + 1) + A}{N+S}$), the decryption will correctly recover the message.

5. Significance

• Restoring Viability of Symmetric FHE: The paper salvages a symmetric-key FHE scheme that was previously considered insecure for multiplicative operations. This is significant because symmetric FHE schemes generally offer better performance (speed and lower overhead) than asymmetric ones (like RSA or Lattice-based FHE).
• Practical Implementation Guidelines: The paper provides concrete guidelines for selecting key sizes based on the desired security level ($\lambda$) and the depth of the arithmetic circuit ($N$ and $A$). This makes the scheme implementable for real-world applications requiring privacy-preserving computation.
• Theoretical Contribution: It highlights the subtle interplay between modulus size, homomorphic depth, and security in CRT-based schemes, demonstrating that simply increasing modulus size for correctness can inadvertently create security loopholes if not managed with multi-prime structures.

In conclusion, the authors successfully modify the Rivest scheme to create a robust, symmetric-key Fully Homomorphic Encryption system that resists known plaintext attacks while maintaining the ability to perform arbitrary numbers of additions and multiplications, provided the secret parameters are sized according to their derived constraints.