💻 computer science

Affine Encryption and Adaptive Single-Neighbor Prediction for High-Capacity Reversible Data Hiding in Encrypted Images

This paper proposes a high-capacity reversible data hiding scheme for encrypted images that combines per-block affine encryption with an adaptive single-neighbor predictor to preserve embedding room while scrambling block variance, thereby achieving significantly higher embedding rates and eliminating the need for variance-based separability compared to existing methods.

Original authors: Ngoc Hung Nguyen, Van At Pham

Published 2026-10-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ngoc Hung Nguyen, Van At Pham

Original paper licensed under CC BY 4.0 (https://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

In the digital age, vast libraries of private photographs are stored on remote servers, safe from prying eyes because they are locked behind encryption. This lock ensures that even the people running the servers cannot see the images. However, a practical problem arises: sometimes a server needs to attach a small piece of information to a file, like a label or a security code, without ever unlocking the image to see what is inside. If the server tries to open the file to add the note, the privacy is broken. If it cannot open the file, it cannot find the empty space needed to hide the note. Scientists have developed a clever workaround called reversible data hiding in encrypted images. This technique allows a server to tuck extra data into a locked image and, later, for an authorized person to retrieve that data and restore the picture to its exact original state, as if the data had never been there. The challenge has always been finding enough room to hide the message without ruining the picture's quality or the security of the lock.

A recent study by researchers from the Vietnam Academy of Science and Technology and the University of Economics–Technology for Industries addresses a specific weakness in the most advanced method currently available. The existing top-performing system works by dividing an image into small blocks and scrambling the pixels within each block in a way that preserves the relationship between neighboring pixels. This preserved relationship creates a pattern of redundancy that can be exploited to hide data. However, the researchers discovered that this leading method had two significant flaws. First, it scrambled the pixels by adding the exact same number to every pixel in a block. While this kept the internal patterns intact, it left the overall "roughness" or variance of the block unchanged. This meant that an observer could still tell the difference between a smooth, flat area of the image and a busy, textured one just by looking at the statistical properties of the encrypted blocks, which is a security leak. Second, the method used a fixed, unchanging rule to guess what a pixel should look like based on its neighbors, a rule that was not always the most efficient choice for every part of the image.

To solve these problems, the team proposed a new approach that replaces the simple addition of a constant number with a more complex, slanted shift. Imagine the pixels in a block as a flat floor; the old method raised the entire floor by the same amount, leaving its tilt unchanged. The new method tilts the floor, raising one side more than the other. This tilt is calculated using a special key that the data-hiding server possesses, but it is designed so that the server can still see the differences between neighboring pixels without being able to figure out the actual brightness of any single pixel. Because the tilt changes the variance of the block, the statistical difference between smooth and textured areas disappears, making the encrypted image much harder to analyze. Furthermore, because this new shift is a straight line across the block, the mathematical differences between neighbors cancel out perfectly, allowing the data-hiding server to work directly on the encrypted numbers without needing to know the secret offset that hides the true image values.

This change in encryption required a change in how the data is hidden. The previous system used a complex average of three neighboring pixels to make its predictions, but that method failed with the new slanted shift. The researchers replaced this with a simpler, single-neighbor prediction that works reliably with the new encryption. They also introduced an adaptive system that tests different starting points for the prediction within each block, choosing the one that creates the most space for the hidden message. This flexibility is particularly useful for images with complex textures, where a single fixed rule would leave less room. By combining these improvements, the researchers eliminated the need for a separate map to track which blocks were modified, a step that previously wasted space.

The results of their experiments, tested on a wide variety of standard and general image sets, show that this new method is fully reversible and significantly more effective. On standard test images, the new technique increased the amount of data that could be hidden by about sixteen percent compared to the previous best method, reaching a rate of 1.48 bits per pixel. On more diverse, general-purpose images, the improvement was even more pronounced, boosting the capacity by four to twelve percent and reaching up to 2.01 bits per pixel. Crucially, the new method successfully scrambled the block variance to the point where it became impossible to distinguish smooth areas from textured ones, reducing the security leak to a level indistinguishable from random chance. The study confirms that by changing the geometry of the encryption from a flat shift to a slanted one, and by adapting the prediction strategy to match, it is possible to hide more data more securely in encrypted images without ever compromising the ability to recover the original picture perfectly.

Technical Summary: Affine Encryption and Adaptive Single-Neighbor Prediction for High-Capacity Reversible Data Hiding in Encrypted Images

Problem Statement
Reversible Data Hiding in Encrypted Images (RDHEI) enables cloud services to embed auxiliary data (e.g., labels, authentication codes) into encrypted images without decrypting them, allowing authorized users to later extract the data and perfectly restore the original image. While Vacating Room After Encryption (VRAE) methods are suitable for cloud outsourcing because they require minimal processing from the content owner, achieving high embedding capacity remains challenging.

The authors identify specific weaknesses in the recent baseline scheme by Chai et al. [16], which utilizes correlation-preserving encryption to maintain intra-block pixel redundancy for embedding. The baseline employs a block-level encryption that adds a constant offset to every pixel within a block. The authors note two critical flaws in this approach:

Statistical Leakage: Because the same constant is added to all pixels in a block, the block variance remains unchanged. This allows an observer to distinguish between smooth and textured blocks based on variance, even if the global entropy appears high.
Suboptimal Prediction: The baseline uses a fixed reference position for its predictor and a three-neighbor average. This heuristic is not optimal for all image regions, limiting the embedding capacity.

Methodology
The proposed method retains the general VRAE structure (block permutation, encryption, prediction, and High-Bit-Plane Redundancy Coding or HBP-RMC) but redesigns the encryption and prediction stages to address the identified weaknesses.

Correlation-Preserving Affine Encryption:
Instead of adding a constant offset, the content owner applies a per-block affine modulation (a tilted plane) defined by $Z_B(i, j) = (X_B(i, j) + a_B i + b_B j + c_B) \mod 256$ .
- Key Delegation: The modulation key $K_m$ is split into a slope key ( $K_s$ ) and an offset key ( $K_c$ ). The content owner holds both, but delegates only $K_s$ to the data hider (cloud).
- Homomorphism: The encryption is homomorphic with respect to modular pairwise differences. The constant term $c_B$ cancels out when calculating the difference between two pixels, leaving a known offset $\Delta r$ dependent only on the slope parameters ( $a_B, b_B$ ) and coordinate differences. This allows the data hider to compute prediction residuals without knowing the absolute pixel values.
- Variance Scrambling: Unlike the baseline, this method scrambles the block variance, preventing the leakage of smooth vs. textured block information.
- Location Map Removal: Since the affine modulation is applied uniformly to all blocks without conditional wrapping checks, the location map ( $\Phi$ ) required by the baseline to track skipped blocks is eliminated, reducing side information overhead.
Modular Single-Neighbor Prediction:
Because the affine keystream cancels only under pairwise differences, the baseline's three-neighbor average predictor (which relies on a floor function that disrupts the cancellation) is replaced.
- Single-Neighbor Predictor: Each pixel is predicted from a single reference-side neighbor. The encrypted-domain residual is calculated as $e(p) = \text{smod}_{256}(Z_B(p) - Z_B(q) - \Delta r(p, q))$ .
- Residual Preservation: Due to the homomorphic property, this encrypted residual is congruent to the plaintext-domain residual, preserving the redundancy required for HBP-RMC.
- Adaptive Reference Selection: Instead of a fixed reference position, the method tests all possible reference positions within a block ( $k_1^2$ positions) and selects the one that maximizes the embedding room (uniform bit-planes) after HBP-RMC coding. This selection index (4 bits for $4\times4$ blocks) is stored as side information.
Data Embedding and Recovery:
The data hider uses the slope key to compute residuals, vacates room via HBP-RMC, and embeds the message. Recovery involves reconstructing the encrypted block by processing pixels in increasing Manhattan distance from the reference position (to ensure the predicting neighbor is already recovered), followed by decryption using the full key.

Key Contributions

Affine Encryption with Delegated Slope Key: A new encryption scheme that replaces constant offsets with a tilted plane, enabling the cancellation of keystreams under modular differencing while scrambling block variance to enhance privacy.
Modular Single-Neighbor Predictor: A predictor tailored to the affine encryption that relies on pairwise differences rather than averages, ensuring the prediction error histogram remains identical to the plaintext domain.
Adaptive Reference Selection: A mechanism to dynamically choose the optimal reference position per block to maximize embedding capacity, particularly beneficial for textured images.
Elimination of Location Map: The removal of the block-skipping logic and its associated location map reduces auxiliary data overhead.

Experimental Results
The method was evaluated on 8-bit grayscale images from standard (USC-SIPI) and general datasets (BOSSbase, BOWS2, UCID) using $4\times4$ blocks.

Capacity: The proposed method achieved a net embedding rate of 1.48 bits per pixel (bpp) on standard images (a ~16% increase over the baseline) and up to 2.01 bpp on general datasets (a 4–12% increase).
Security:
- Histogram: The proposed encryption produced histograms close to uniform (Chi-square values between 240–280), whereas the baseline remained uneven (6,800–49,600).
- Variance: The baseline's block variance perfectly separated smooth and textured blocks; the proposed method reduced this separability to approximately chance levels.
- Entropy: While both schemes achieved high global entropy (~8 bits), the proposed method significantly reduced local entropy variation across blocks compared to the baseline.
Reversibility: The scheme was verified to be fully reversible, allowing perfect restoration of the original image and extraction of the hidden message.

Significance
The paper claims that by integrating affine encryption with a modular single-neighbor predictor, it successfully resolves the trade-off between high embedding capacity and privacy protection in RDHEI. The primary significance lies in eliminating the variance-based leakage inherent in previous correlation-preserving schemes and removing the overhead of location maps, thereby increasing the net embedding rate while ensuring the encrypted image reveals no structural information about the underlying content (smooth vs. textured regions) to unauthorized observers.

More like this