💻 computer science

How to Watermark the RLWE Homomorphic Ciphertexts

This paper proposes two robust watermarking schemes, ARWMark and MRWMark, for RLWE-based homomorphic encryption that embed copyright and authentication information into ciphertexts while maintaining security and surviving homomorphic additive and multiplicative operations.

Original authors: Yufei Zhou

Published 2026-07-29

📖 9 min read🧠 Deep dive

CC BY 4.0

Original authors: Yufei Zhou

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 a world where you can ask a stranger to do math for you, but you never have to show them your secret numbers. You lock your data in a magical, unbreakable box, hand it over, and the stranger performs calculations on the box itself. When they hand it back, you unlock it to find the answer, and the stranger never saw a single digit of your original data. This is the promise of Homomorphic Encryption (HE), a superpower of modern cryptography that lets us compute on encrypted data without ever decrypting it. It's like sending a sealed letter to a post office that can sort, stamp, and route the letter without ever opening the envelope to read the address.

But here's the catch: once that letter leaves your hands, who owns the work inside? If a company uses your encrypted data to train a model or process a medical scan, the final result is a new, valuable digital asset. How do you prove that your data was used, or that their specific algorithm was the one that did the work? In the digital world, we usually slap a watermark on photos or songs to prove ownership. But you can't just paint a watermark on a locked box; if you scratch the surface, you might break the magic, and the box won't open anymore. Furthermore, if the box gets passed around and processed many times, a simple scratch might get erased completely. Scientists have been trying to figure out how to hide a secret "signature" inside these magical boxes that survives the journey and the math, without breaking the lock.

This paper, titled "How to Watermark the RLWE Homomorphic Ciphertexts," tackles exactly that puzzle. The authors, led by Yufei Zhou, propose a way to hide tiny, invisible "watermarks" inside the mathematical noise of these encrypted boxes. They don't just suggest a vague idea; they build two specific, working methods and prove mathematically that they work. Think of it like hiding a secret message inside the static noise of a radio signal. The message is there, but to the casual listener, it just sounds like static. The authors show that even after the signal gets boosted, mixed with other signals, or passed through a noisy filter, that secret message can still be found by someone who knows the right decoder.

The paper introduces two distinct tools for this job, each designed for a different kind of math problem. The first tool, called ARWMark, is like a sturdy, flexible sticker. It's great at surviving when you add things together (like adding up encrypted numbers), but if you try to multiply the encrypted boxes, the sticker gets torn to shreds. The second tool, MRWMark, is more like a complex, interlocking puzzle piece. It's much tougher; it can survive both adding and multiplying encrypted data. However, it's harder to use and requires a lot more "space" in the noise to hide the message. The authors didn't just dream this up; they wrote code, ran thousands of simulations on powerful computers, and showed that their watermarks stay hidden and detectable even when the encrypted data is put through the wringer of complex calculations.

The Magic of the "Locked Box"

To understand how this works, let's look at the ingredients. The paper relies on a type of encryption called RLWE (Ring Learning with Errors). Imagine you have a secret recipe (your data) and you want to bake a cake (compute a result) in a stranger's kitchen. To keep the recipe safe, you don't give them the ingredients; you give them a bag of flour that has a tiny, invisible amount of sand mixed in. The stranger bakes the cake using this "noisy" flour. When they hand you the cake, you know exactly how much sand was in the flour, so you can subtract it out to get the perfect cake. The "sand" is the noise. In the real world, this noise is a mathematical necessity that keeps the encryption secure; without it, the secret recipe could be guessed.

The problem is that this noise is also the perfect hiding spot for a watermark. The authors realized that if they could hide a tiny, specific pattern of "sand" inside the noise, they could prove that a specific box belonged to them. But there's a risk: if they put too much sand in, the cake might crumble (the decryption fails). If they put too little, the stranger might not be able to find the pattern later. And if the stranger mixes two bags of flour together (homomorphic addition) or multiplies them (homomorphic multiplication), the sand patterns might get scrambled or washed away.

The Two Solutions: The Sticker and the Puzzle

The authors propose two ways to solve this, depending on what kind of math the "stranger" needs to do.

1. ARWMark: The "Addition-Proof" Sticker
This method is designed for situations where the encrypted data is mostly just added together, like tallying up votes or summing up medical statistics. The authors treat the watermark like a secret signal hidden in the static. They pick a random "key" (a specific pattern of sand) and add a little bit of it to the noise in the box.

How it works: Imagine you have a bag of flour with random sand. You add a tiny, specific amount of "blue sand" to it. When you want to check if the bag is yours, you look for the blue sand.
The Catch: This works great if you just add more bags of flour together. The blue sand just gets a little diluted, but it's still there. However, if you try to multiply the bags (a much more complex operation), the blue sand gets mixed up so thoroughly that the pattern disappears. The paper proves mathematically that this method is robust against addition but fails against multiplication.
The Result: They showed that even after adding many encrypted numbers together, the "blue sand" pattern could still be detected with high accuracy, provided the initial amount of blue sand was strong enough.

2. MRWMark: The "Multiplication-Proof" Puzzle
This is the heavy lifter. It's designed for scenarios where the data is multiplied, like running a complex AI model or deep learning inference. This is much harder because multiplication scrambles the noise in a chaotic way.

How it works: Instead of just adding a pattern, the authors use a clever trick involving a "linear equation system." Imagine you have a set of rules (like a riddle) that only a specific set of numbers can solve. They hide a set of numbers inside the noise that solves this riddle.
The Magic: When you multiply the encrypted boxes, the math of the multiplication actually preserves the solution to the riddle. It's like if you had a puzzle where the pieces fit together, and even if you shook the box, the pieces still fit the same way.
The Catch: Because multiplication creates so much chaos, this method needs a lot more "space" (embedding intensity) to hide the message. The paper notes that the amount of noise required to make this work is huge—sometimes needing an embedding intensity in the millions—to ensure the message isn't lost in the mathematical storm.
The Result: They demonstrated that this method can survive both addition and multiplication, but it's a "zero-bit" system (it just proves a watermark exists, it doesn't carry a long message) and requires a lot of resources to be reliable.

What the Numbers Say

The authors didn't just guess; they tested these ideas rigorously. They built a simulation using Python on a powerful computer with an Intel Xeon Gold CPU and 502 GB of RAM. They set up the encryption parameters to meet a standard 128-bit security level, using a polynomial size ( $N$ ) of 2048 and a plaintext modulus ( $p$ ) of 65537.

For ARWMark, they found that with a modest embedding intensity ( $I_w$ ) of 7, they could clearly distinguish the watermark in secret-key encryption. However, for public-key encryption (which is noisier), they needed to crank that intensity up to 100 to get the same clear signal. They tested what happens when you add random noise (simulating an attacker trying to erase the watermark). They found that as long as the noise wasn't too massive, the watermark survived. But if the attacker added enough noise, the watermark could be lost, unless the original embedding was made stronger.

For MRWMark, the stakes were higher. They found that with a small embedding intensity, the watermark was often lost in the noise. But when they increased the intensity to 34, the success rate of finding the watermark jumped to nearly 100%. When they tested multiplication, the requirements skyrocketed. To survive a single multiplication operation without a "resize" (a specific noise-reduction step), they needed an intensity of at least 782,327. If they added a resize operation, that number jumped to nearly 96 million. These numbers show that while the method works, it comes with a heavy cost in terms of the "size" of the watermark needed.

The Bottom Line

This paper proves that we can indeed hide watermarks inside these magical encrypted boxes. It's a significant step forward because it moves beyond just "can we compute?" to "can we track and protect the results of that computation?"

The authors are careful to point out the limits. Their "sticker" (ARWMark) is great for simple addition but breaks under multiplication. Their "puzzle" (MRWMark) can handle multiplication but is expensive and hard to use. They don't claim to have solved the problem for every possible scenario, but they have provided a solid foundation and two working prototypes.

In the future, the authors hope to combine the best of both worlds—creating a watermark that is both small and tough enough to survive any math operation. Until then, their work offers a new layer of security for the privacy-preserving world, ensuring that when we hand our secrets to the cloud, we can still prove who did the work and who owns the result. It's a small, invisible signature in a sea of noise, but for the digital age, that signature might be the difference between trust and chaos.

Technical Summary: Watermarking the RLWE Homomorphic Ciphertexts

1. Problem Statement

Homomorphic Encryption (HE) based on the Ring Learning with Errors (RLWE) problem has become a cornerstone for privacy-preserving computation, enabling tasks such as secure deep learning inference and database queries. However, existing HE schemes prioritize computational feasibility and efficiency, often neglecting the protection of ciphertexts as valuable digital assets.

In scenarios like federated learning or outsourced computation, HE ciphertexts undergo transformations that add value (e.g., processing logic, model contributions) but also expose them to ownership disputes. Current protection mechanisms, such as homomorphic MACs, hash functions, or Zero-Knowledge Proofs (ZKPs), are insufficient for this specific context because:

They introduce significant overhead.
They are often separated from the ciphertext, increasing the attack surface.
They lack robustness against the noise accumulation inherent in HE operations (e.g., relinearization, approximate arithmetic in CKKS).
ZKPs typically verify only final results, failing to protect intermediate states or prove the participation of specific parties in a computation pipeline.

Directly applying traditional digital watermarking is also infeasible. HE ciphertexts possess strict mathematical structures where even minor perturbations (like flipping a least significant bit) can cause decryption failure. Furthermore, the distribution of HE ciphertexts is computationally indistinguishable from uniform, rendering statistical watermarking methods (e.g., difference expansion) ineffective.

2. Methodology

The paper proposes a formal framework for Homomorphic Ciphertext Watermarking and introduces two distinct schemes tailored for RLWE-based HE: ARWMark and MRWMark.

Core Definitions

The authors define three essential properties for the scheme:

Fidelity: Watermark embedding must not alter the decryption result ( $Dec(sk, c'_t) = Dec(sk, c_t)$ ).
Robustness: The watermark must remain extractable after a sequence of homomorphic operations (addition and/or multiplication) and noise accumulation.
Security: Watermarked ciphertexts must remain computationally indistinguishable from non-watermarked ones under passive attacks.

Scheme 1: ARWMark (Addition-Robust Watermarking)

Mechanism: ARWMark embeds a watermark into the noise component of the ciphertext. It exploits the redundancy in the decryption noise by adding a scaled embedding key ( $k_w$ ) to the ciphertext polynomial.
Embedding: For a 1-bit watermark $w \in \{0, 1\}$ , mapped to $w_e \in \{-1, 1\}$ , the first component of the ciphertext $c_1$ is modified as:
$c'_1 = c_1 + p \cdot w_e \cdot I_w \cdot k_w$
where $p$ is the plaintext modulus, $I_w$ is the embedding intensity, and $k_w$ is sampled from a distribution similar to the encryption noise.
Detection: Detection is blind and correlation-based. The extractor (holding the secret key) recovers the noise, computes the inner product with the known embedding key $k_w$ , and compares the correlation value $\rho$ against a threshold.
Robustness: The scheme is robust against homomorphic addition. Since addition in RLWE is linear, the embedded watermark signal adds linearly, while the noise variance increases. By adjusting the embedding intensity and using multi-ciphertext averaging, the signal-to-noise ratio can be maintained.
Limitation: It is not robust against homomorphic multiplication, as multiplication mixes noise components from different ciphertexts, destroying the linear correlation structure required for detection.

Scheme 2: MRWMark (Multiplication-Robust Watermarking)

Mechanism: MRWMark is designed to withstand both addition and multiplication. It leverages the property that the solution space of a homogeneous linear system is closed under linear combinations.
Embedding: Instead of a single noise vector, the scheme embeds a set of noise vectors derived from the solution space of a homogeneous linear system ( $A_{le} \cdot X_{le} = 0$ ) into a group of $m$ ciphertexts. The embedding key is the matrix $A_{le}$ .
Detection: The extractor recovers the noise vectors from the ciphertexts and checks if they satisfy the original linear system. If the reconstructed vectors are non-zero solutions to $A_{le} \cdot X_{le} = 0$ , the watermark is present.
Robustness: Because homomorphic multiplication induces linear combinations of the underlying noise polynomials, the resulting noise remains within the solution space of the linear system, preserving the watermark's structural integrity.
Limitation: It is a 0-bit (or limited capacity) watermarking scheme (detecting presence rather than extracting a specific message bit easily without complex extensions) and requires a significantly larger embedding intensity ( $I_w$ ) to separate the watermark from the intrinsic decryption noise, as the solution vectors must be distinct from random noise.

3. Key Contributions

Formal Definition: The paper establishes the first formal definition of homomorphic ciphertext watermarking, defining requirements for fidelity, robustness, and security in the context of HE.
ARWMark: A 1-bit (extendable to $t$ -bits) robust watermarking scheme that resists homomorphic addition. It utilizes noise stratification and correlation-based detection.
MRWMark: A 0-bit (presence detection) robust watermarking scheme that resists both homomorphic addition and multiplication. It utilizes the algebraic properties of linear equation solution spaces.
Theoretical and Empirical Validation: The authors provide rigorous proofs for security (indistinguishability) and fidelity, along with theoretical bounds on correctness and robustness. Extensive experiments validate these claims under various noise levels and operation counts.

4. Experimental Results

The schemes were implemented in Python with RLWE parameters set for 128-bit security ( $N=2048$ , $p=65537$ , $\sigma=3.2$ ).

ARWMark Performance:
- Correctness: Correlation values ( $\rho$ ) concentrate around their expected values (0 for no watermark, $\pm \sigma^2$ for watermarks). Increasing embedding intensity ( $I_w$ ) reduces variance, improving separation.
- Robustness: The scheme maintains high True Positive Rates (TPR) even after multiple homomorphic additions. The standard deviation of $\rho$ increases with added noise, but the watermark remains distinguishable.
- Attack Resistance: It shows resilience against random noise attacks (multiples of $p$ ) that do not affect decryption, provided $I_w$ is sufficiently large.
MRWMark Performance:
- Correctness: TPR increases significantly with $I_w$ . Perfect extraction (TPR=1.0) was achieved at $I_w=34$ for addition-only scenarios.
- Robustness:
  - Addition: TPR decreases as the number of added ciphertexts increases unless $I_w$ is increased.
  - Multiplication: The scheme successfully withstands multiplication, but requires very large $I_w$ (e.g., $>782,000$ ) to counteract the massive noise introduced by multiplication and relinearization.
- Trade-off: MRWMark is more sensitive to noise than ARWMark, necessitating higher embedding intensities to maintain reliability.

5. Significance and Claims

The paper claims that introducing digital watermarking into HE addresses a critical gap in practical deployment: provenance and accountability.

Value Protection: By treating HE ciphertexts as valuable digital assets, the proposed schemes allow data providers and service providers to authenticate the origin of ciphertexts and verify computational contributions (e.g., in federated learning).
Complementarity: The work positions watermarking as a necessary complement to existing HE schemes, offering protection mechanisms that are robust to the specific noise characteristics of homomorphic operations, unlike traditional MACs or ZKPs.
Feasibility: The authors demonstrate that watermarking is theoretically sound and practically feasible for RLWE-based HE, providing a foundation for future applications requiring copyright protection and source authentication in secure computation pipelines.

The paper concludes modestly, acknowledging that ARWMark lacks multiplication robustness and MRWMark has limited embedding capacity, identifying these as targets for future research to create more versatile and practical schemes.