💻 computer science

Beyond Controlled Noise: Achieving Symmetric FHE through Dynamic Position Shifting

This paper proposes a novel symmetric Fully Homomorphic Encryption scheme that mitigates traditional noise growth and computational overhead by employing plaintext fragmentation with dynamic position shifting, utilizing a dual-regulator system to manage multiplication and a binding mechanism to ensure security against algebraic attacks.

Original authors: Mostefa Kara

Published 2026-05-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mostefa Kara

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a secret message, like a recipe for a cake, and you want to let a chef cook with it without ever showing them the actual ingredients. In the world of cryptography, this is called Fully Homomorphic Encryption (FHE). Usually, doing this is like trying to bake a cake while wearing thick, heavy oven mitts that make your hands clumsy and slow. The "noise" (the oven mitts) gets worse every time you mix ingredients, eventually making the cake impossible to bake correctly.

This paper proposes a new, lighter way to do this using Symmetric FHE. Instead of heavy oven mitts, the authors use a clever system of shuffling and splitting to keep things clean.

Here is how their system works, broken down into simple concepts:

1. The Problem: The "Noise" Explosion

In traditional methods, if you multiply two encrypted numbers, the "noise" (mathematical static) inside the encryption grows wildly. It's like trying to whisper a secret across a crowded room; if you pass the message from person to person, the noise of the crowd eventually drowns out the words. Existing solutions try to fix this by "bootstrapping" (a complex, slow process of refreshing the signal), which is like stopping the game every few minutes to reset the room.

2. The Solution: Breaking the Message into Fragments

The authors' idea is to slice the secret message (the recipe) into three smaller pieces (fragments).

The Setup: Instead of hiding one big secret, they hide three small pieces in three different "positions" (let's call them Position 1, 2, and 3).
The Magic Trick: They use special "Regulator Keys." Think of these as traffic controllers or shuffling cards.

3. How Multiplication Works (The "Interposition" Mechanism)

When you want to multiply two encrypted numbers, the system doesn't just smash them together. Instead, it plays a game of musical chairs with the fragments:

The Rule: If you multiply a piece in Position 1 with another piece in Position 1, the result doesn't stay in Position 1. The "Regulator" forces it to move to Position 2.
The Cycle: If you multiply pieces in Position 2 and 3, the result moves to Position 1.
The Result: The fragments are constantly shuffled to new spots. This prevents the "noise" from piling up in one place. It's like a relay race where the baton (the math) is passed to a fresh runner every time, so no single runner gets tired (accumulates too much noise).

4. The "Dual-Regulator" Safety Net

To make sure no one can cheat or figure out the secret key, the system uses two types of regulators working together:

Exponent Regulators: These control where the math moves (the traffic direction).
Coefficient Regulators: These control the size of the numbers (normalizing the weight).

The paper claims these two are "dual-bound." Imagine trying to unlock a safe that requires two different keys turned at the exact same time. If a hacker tries to guess one key, the other one changes the lock, making it impossible to solve the puzzle. This protects the secret key from being stolen through algebraic tricks.

5. What the Paper Claims (The Results)

Speed: Because they don't need the heavy "bootstrapping" process, this method is incredibly fast. The paper says encryption takes about 0.02 milliseconds (faster than a blink of an eye).
Size: The encrypted data is very small (only 9 KB), whereas other methods can be hundreds of kilobytes.
Accuracy: The math works perfectly. You can multiply numbers as many times as you want, as long as the final answer isn't bigger than a specific limit (the size of the prime number used). There is no "noise budget" to run out of.
Security: The system is secure against standard hacking attempts (IND-CPA). However, the paper admits a major limitation: It is not safe against quantum computers. The security relies on the difficulty of factoring large numbers, which a quantum computer could solve easily.

Summary Analogy

Think of this scheme as a secret relay race.

Old Way: One runner carries a heavy, noisy backpack. Every time they pass the baton, the backpack gets heavier and noisier until they collapse.
This Paper's Way: The message is split into three small bags. Every time the baton is passed, the bags are swapped between three different runners, and the bags are magically resized to stay light. The runners never get tired, and the message stays clear. The only catch? If a super-fast quantum robot shows up, it might be able to figure out the route map, but for now, it's a very fast and efficient way to keep secrets safe on regular computers.

Technical Summary: Beyond Controlled Noise: Achieving Symmetric FHE through Dynamic Position Shifting

Problem Statement
Traditional Fully Homomorphic Encryption (FHE) schemes, particularly those based on lattice constructions (e.g., BGV, BFV, CKKS), suffer from prohibitive computational overhead and complex noise management. These schemes often require expensive operations like bootstrapping or relinearization to maintain correctness during homomorphic multiplication. While symmetric FHE offers a potential path to reduced overhead, naive symmetric designs (such as trivial encryption $c = mk$) fail in practice because the noise or secret key exponents grow exponentially during multiplication, rendering the scheme impractical for deep arithmetic circuits. Existing literature lacks a symmetric FHE construction that effectively regulates ciphertext growth without relying on lattice-based complexity.

Methodology
The paper proposes a novel symmetric FHE scheme that replaces traditional noise management with a mechanism of plaintext fragmentation and dynamic interposition. The core architecture relies on a modular encryption foundation $c = mk + rp$ (where $p$ is a prime modulus and $r$ is a random scalar), which is naturally additive but unstable under multiplication.

To resolve multiplicative instability, the authors introduce:

Plaintext Fragmentation: The message $m$ is probabilistically split into three fragments ( $m_1, m_2, m_3$ ) such that their sum equals $m$ . Each fragment is encrypted under a distinct "position key" ( $k_1, k_2, k_3$ ).
Dual-Regulator System: A set of public keys, termed "regulators," governs the multiplication process. These are divided into:
- Exponent Regulators ( $t_i$ ): These redirect the product of ciphertext fragments to a new logical position. This prevents the accumulation of secret key exponents (e.g., transforming $k^x \cdot k^y$ into a form associated with a new position $k^z$ ) rather than allowing them to compound exponentially.
- Coefficient Regulators ( $d_i$ ): These normalize the scalar coefficients resulting from multiplication, ensuring the output remains in the correct algebraic form for decryption.
Interposition Mechanism: The scheme operates on a cyclic flow of three positions ( $P_1, P_2, P_3$ ). When fragments are multiplied, the result is not returned to the original position (which would require risky inverse operations) but is shifted to a target position determined by a deterministic function (e.g., $P_1 \times P_1 \to P_2$ ). This creates a closed-loop system where fragments are perpetually reshuffled but never lost or exponentially expanded.

Key Contributions

Novel Symmetric Construction: The paper introduces the first symmetric FHE scheme utilizing interposition and plaintext fragmentation to regulate ciphertext growth, filling a gap in lightweight cryptography literature.
Noise-Free Multiplicative Depth: Unlike lattice-based schemes, this approach does not suffer from stochastic noise accumulation. The "noise" term ($rp$) vanishes upon reduction modulo $p$ at every step. Consequently, the scheme supports unbounded multiplicative depth, limited only by the plaintext capacity (i.e., the product of messages must remain less than the prime modulus $p$ ).
Dual-Binding Security: The security relies on a binding mechanism where exponent and coefficient regulators are mutually dependent. An attacker cannot isolate the secret key $k$ by manipulating one regulator without being thwarted by the unknown parameters of the other.
Formal Security Analysis: The authors provide an IND-CPA security proof based on two hardness assumptions: the Multiplicative Masking Assumption ( $MMA_p$ ) and Hidden Modulus Indistinguishability ( $HMP_n$ ). The security of the position keys is grounded in the Discrete Logarithm Assumption (DLA) and Integer Factorization (IFA).

Results and Performance
The paper presents a performance evaluation comparing the proposed scheme against established lattice-based models (BGV, BFV, CKKS, TFHE) on a standard Intel i7-10700 CPU:

Efficiency: The proposed scheme demonstrates significantly lighter performance. Encryption time is approximately 0.02 ms, and homomorphic addition is nearly negligible (0.002 ms).
Ciphertext Size: The ciphertext size is compact at 9 KB, compared to the hundreds of kilobytes typical in lattice-based schemes.
Correctness: The scheme achieves exact homomorphic addition and multiplication in $\mathbb{Z}_p$ without the need for bootstrapping or modulus switching.
Limitations: The scheme is not IND-CCA secure (a known property of homomorphic schemes due to malleability) and is not post-quantum secure, as its security relies on DLA and IFA, which are vulnerable to Shor's algorithm.

Significance
The paper claims to provide a highly efficient, lightweight alternative to traditional FHE for scenarios prioritizing speed and compactness over post-quantum security. By eliminating the need for complex noise management and bootstrapping, the proposed "interposition" mechanism offers a deterministic approach to symmetric homomorphic encryption. The authors position this work as a viable solution for resource-constrained environments (such as IoT) where classical security assumptions hold, while acknowledging that future work is required to adapt the interposition mechanism to post-quantum settings.