How to Watermark the RLWE Homomorphic Ciphertexts

Source: arXiv:2607.25222 · Published 2026-07-28 · By Yufei Zhou

TL;DR

This paper addresses the novel problem of embedding digital watermarks into RLWE-based homomorphic encryption (HE) ciphertexts to enable copyright protection, source authentication, and auditing of encrypted computations. Existing HE schemes focus primarily on functionality and efficiency, overlooking the need to securely demonstrate ownership or contribution during computation workflows where ciphertexts are transformed by homomorphic operations. The authors propose two watermarking schemes tailored for the algebraic structure and noise characteristics of RLWE ciphertexts: ARWMark, which embeds additive watermarks robust to homomorphic additions, and MRWMark, a zero-bit watermarking scheme built on linear algebraic solution spaces that is resilient against both homomorphic additions and multiplications. The schemes preserve plaintext correctness, maintain semantic security, and enable watermark detection only by those holding secret information. The authors provide formal definitions, rigorous security/privacy analyses, and extensive empirical evaluation on RLWE ciphertexts, demonstrating robustness under noise accumulation, operation sequences, and watermark extraction accuracy. This work pioneers the integration of digital watermarking into practical RLWE homomorphic ciphertexts while maintaining cryptographic guarantees.

Key findings

• The ARWMark scheme embeds a 1-bit watermark into ciphertext noise without affecting plaintext decryption, allowing watermark detection via correlation with embedding noise vectors.
• ARWMark scaling to t-bit watermarks is achieved by embedding orthogonal noise vectors, each encoding one bit.
• ARWMark is provably robust to arbitrary-length homomorphic additions while maintaining plaintext correctness and watermark fidelity.
• MRWMark embeds watermark by encoding ciphertext noise vectors as solutions to a linear homogeneous equation system, ensuring the watermark persists under both homomorphic additions and multiplications.
• MRWMark supports zero-bit watermarking (presence detection only) robust to all polynomial homomorphic operations, including multiplication, whereas ARWMark supports additive homomorphism only.
• Watermarks remain computationally indistinguishable from ciphertext noise, preserving semantic security under passive adversaries who know watermarking keys but lack the secret decryption key.
• Experimentally, watermark detection correlates strongly with embedding intensity; increasing ciphertext batches reduces variance and improves detection (Fig. 7 shows standard deviation of correlation decreasing with batch size).
• The watermark embedding intensity trades off robustness and noise budget; too large noise breaks decryption, too small weakens detection resilience to homomorphic noise accumulation.

Threat model

The adversary is passive and computationally bounded, able to intercept watermarked RLWE ciphertexts and know watermark embedding keys and algorithms but lacks access to the secret decryption key sk. The adversary cannot modify ciphertexts or perform active attacks such as re-encryption or chosen ciphertext attacks. The threat model focuses on preserving watermark indistinguishability under normal operating conditions, preventing unauthorized watermark extraction and source repudiation.

Methodology — deep read

The paper begins by formalizing the threat model and watermarking requirements for homomorphic ciphertexts. The adversary is passive, can observe watermarked ciphertexts and knows the watermark scheme and keys but cannot access the secret decryption key (sk). The goal is to embed watermarks that do not alter plaintext decryption (fidelity), survive homomorphic operations (robustness), and are indistinguishable from normal ciphertext noise (security).

The authors work on simplified RLWE-based schemes defined over polynomial ring Rq = Zq[x]/(x^N + 1) with plaintext modulus p. Each ciphertext ct = (c1, c2) hides plaintext and noise in a way that decryption recovers the plaintext modulo p.

Two watermarking schemes are presented:

1. ARWMark: For a 1-bit watermark w ∈ {−1,1}, embed additive perturbation p * w * Iw * kw into the first ciphertext polynomial coefficient c1 (kw sampled from embedding key distribution matching noise). This is done without modifying c2, preserving decryption correctness. Detection extracts noise component by applying secret key sk and modulus operations, then performs correlation-based detection with kw over ciphertext coefficients, thresholded to decide embedded bit. This approach extends to t-bit watermarks by embedding multiple orthogonal noise vectors in the same ciphertext. Multi-ciphertext embedding reduces per-ciphertext noise.

2. MRWMark: Targeting robustness to homomorphic multiplications, MRWMark encodes watermark across m ciphertexts as noise vectors that form solutions to a linear homogeneous equation Ale · Xle = 0 with small integer norms. Because solutions to linear systems remain solutions under linear combinations (key to homomorphic multiplications over Rq), the watermark survives polynomial evaluation. Detection extracts noise vectors from ciphertexts using sk and verifies if they satisfy Ale · Xle = 0 exactly (nonzero solution indicates watermark presence). This is a zero-bit scheme detecting watermark presence only.

Training/hardware details are not applicable as this is a cryptographic construction. The evaluation protocol involves embedding watermarks into RLWE ciphertexts, applying sequences of homomorphic additions or multiplications, adding noise simulating key/modulus switching, and correlating the extracted noise to recover watermark bits or detect watermark presence. Metrics include correlation values (ρ), false positive/negative rates, and robustness under cumulative noise and operations. Figures analyze standard deviations, threshold selection, and attack scenarios such as random noise addition and multiple ciphertext aggregation.

Reproducibility: The authors provide open-source implementation on GitHub for their watermarking schemes and evaluations, accompanying the paper. The underlying RLWE ciphertexts follow standard open constructions, enabling replication of results.

A concrete example: embedding a 1-bit watermark involves sampling a noise vector kw, computing c'1 = c1 + p * w * Iw * kw for ciphertext ct = (c1, c2), then detecting by computing e' = round((c'1 + c'2 * s) / (Iw * p)), correlating e' with kw and applying thresholding to recover w without corrupting decryption output.

Technical innovations

• Design of ARWMark scheme embedding additive watermarks into the decryption noise of RLWE ciphertexts that preserve plaintext correctness and are robust against arbitrary-length homomorphic additions.
• Extension of ARWMark to multi-bit watermarking by embedding linearly independent noise vectors into a single ciphertext and multi-ciphertext watermarking to reduce noise magnitude.
• Development of MRWMark watermarking scheme that encodes watermarks as solutions to a linear homogeneous system to maintain robustness against both homomorphic additions and multiplications, enabling watermark detection despite complex ciphertext transformations.
• Formalization of homomorphic ciphertext watermarking problem with fidelity, robustness, and security definitions tailored to RLWE HE schemes under passive adversary models.

Baselines vs proposed

• Comparison of correlation ρ under different embedding intensities and numbers of ciphertexts demonstrates increased detection robustness with higher intensity and larger batch sizes (Fig. 3, Fig. 7).
• Success attack rate for random noise addition drops sharply below 10^-3 when embedding intensity exceeds certain threshold, indicating resilience to noise injection attacks (Fig. 6).
• MRWMark shows stable watermark detection across multiple homomorphic addition and multiplication operations, unlike correlation-based ARWMark which degrades under multiplication (Fig. 8).

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.25222.

Fig 5: Normalized frequency distribution histogram of ρ with embed-

Fig 6: Normalized frequency distribution histogram of ρ with embed-

Fig 7: Standard deviation of ρ for different embedding intensities.

Fig 8: Comparison of ρ under different embedding values after adding

Fig 9: Comparison of ρ under different embedding values after adding

Fig 10: Success attack rate for adding uniformly random noise. We set

Fig 11: Standard deviation of ρ with different number of ciphertexts.

Fig 12: Effect of addition operations on MRWMark.

Limitations

• MRWMark supports only zero-bit watermarking (presence detection) without capacity for message encoding, limiting applications that require watermark content extraction.
• Watermark embedding increases ciphertext noise, reducing the noise budget available for homomorphic operations and risking decryption failure if embedding intensity is too high.
• The schemes have only been evaluated on simplified RLWE schemes; practical deployment on full FHE stacks with key switching, modulus switching, and batching may introduce additional noise or distortions.
• Security analysis assumes passive adversaries; robustness to active tampering, adaptive adversaries, or powerful attackers injecting malicious ciphertexts remains untested.
• Watermark detection relies on the secret key sk, requiring trusted parties to verify watermark presence, limiting public verifiability scenarios.
• The paper does not evaluate robustness under heterogeneous ciphertexts or scenarios with non-identical homomorphic operations on watermark-carrying ciphertexts.

Open questions / follow-ons

• Can watermarking techniques be extended to support public verifiability without exposing the secret key or plaintext?
• How do watermarking schemes generalize to state-of-the-art full FHE schemes with complex noise management techniques like bootstrapping and key switching?
• What are the robustness limits and trade-offs for watermark embedding when adaptive adversaries actively alter ciphertexts to remove or forge watermarks?
• Is it possible to develop multi-bit watermarking schemes resilient to homomorphic multiplications, enabling message extraction rather than zero-bit presence detection?

Why it matters for bot defense

While primarily focused on cryptographic watermarking of RLWE homomorphic ciphertexts, the techniques and formalism introduced provide valuable insight into embedding robust, noise-resilient signals within encrypted data flows. Bot-defense and CAPTCHA engineers working with privacy-preserving encrypted computation pipelines can apply the presented watermark embedding and detection methodologies to enable proof-of-ownership or computational contribution verification during encrypted federated learning or privacy-sensitive model inference workflows. The fidelity and robustness definitions clarify crucial data integrity constraints in challenging encrypted domains, guiding the design of embedded authentication systems. The zero-bit watermarking approach MRWMark, in particular, suggests a lightweight scheme for tamper-evident tracking of encrypted payloads resistant against complex manipulations, which might inspire novel CAPTCHA challenge constructions leveraging homomorphic transformations. However, practical adaptation requires consideration of noise budget constraints and trusted key management for watermark detection.

Cite

@article{arxiv2607_25222,
  title={ How to Watermark the RLWE Homomorphic Ciphertexts },
  author={ Yufei Zhou },
  journal={arXiv preprint arXiv:2607.25222},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.25222}
}

Read the full paper

• arXiv:2607.25222 (abstract)
• arXiv:2607.25222 (PDF)