Reversible data hiding in encrypted domain based on NTRU and Chinese remainder theorem

Abstract

Reversible data hiding in the encrypted domain (RDH-ED) based on homomorphic encryption provides a promising approach for privacy-preserving data sharing, yet existing methods based on the N th-degree truncated polynomial ring unit (NTRU) face a fundamental conflict between embedding capacity and reversibility, often requiring preprocessing of plaintext, which in turn compromises randomness of the ciphertext obtained. To address these issues, a novel RDH-ED scheme integrating the Chinese remainder theorem (CRT) with the NTRU cryptosystem is proposed in this study. The proposed scheme operates without any preprocessing of the plaintext and constructs multichannel redundancy in the ciphertext domain, thereby fully preserving the original polynomial structure of the plaintext. By employing a CRT-based encoding, multiple bits of information are enabled to be carried by a single polynomial coefficient, achieving an embedding capacity of 503 bits per polynomial with moderate-sized parameters. Moreover, the embedded data can be extracted before decryption via pre-negotiated coprime parameters, offering greater operational flexibility. Rigorous mathematical constraints ensure that the redundancy term is automatically eliminated during decryption, thereby guaranteeing lossless recovery of the original content. Experimental results demonstrate that the proposed scheme achieves a substantially higher embedding capacity compared to predominant RDH-ED methods based on NTRU, Paillier, and ElGamal cryptosystems, without compromising security or efficiency.

1. Introduction

With the increasing demand for information security and the acceleration of digital transformation, protecting sensitive data while enabling efficient information sharing has become a critical issue. In the plaintext domain, reversible data hiding (RDH) technology has achieved significant progress. For instance, Tang et al. (2020) proposed a weighted average-based complexity calculation for block selection, which improves embedding efficiency. Their subsequent work (Tang et al., 2022a, 2022b) further enhanced block selection strategies based on pixel value ordering and prediction error expansion. However, these methods typically require direct access to the original plaintext data, rendering them unsuitable for privacy-preserving applications.

Against this backdrop, RDH in the encrypted domain (RDH-ED) has been widely adopted. This technique allows additional information to be embedded into encrypted data without compromising confidentiality, while supporting lossless extraction of the hidden data and full recovery of the original content. Specifically, the redundant space in the ciphertext domain is employed to carry additional data. It is especially promising in privacy-critical applications such as medical image transmission and digital rights management. Fig. 1 illustrates different technical frameworks in RDH-ED categorized according to their respective cryptosystems.

Early schemes built on symmetric cryptography (Ma et al., 2013; Liu JF et al., 2015; Yi and Zhou, 2017) often follow a reserving room before encryption (RRBE) strategy, in which embedding space is created in the plaintext domain prior to encryption. In such schemes, RDH is performed by the content owner rather than the data hider. This requirement limits the practicality of these schemes in scenarios where the content owner lacks sufficient processing capability or when the data hiding process is expected to be imperceptible to the content owner, thereby restricting their applicability in flexible encrypted-domain settings. In contrast, public-key cryptosystems, particularly those endowed with homomorphic properties, have been shown to enhance security by enabling data embedding directly in the encrypted domain, and are therefore more closely aligned with the vacating room after encryption (VRAE) paradigm (Qi et al., 2023; Zhou ZY et al., 2024). While these approaches (Ke et al., 2016; Zhang MQ et al., 2016; Zhang XP et al., 2016; Lin et al., 2021; Malik et al., 2022; Kong et al., 2024; Wu et al., 2025) support broader applications, they exhibit low embedding rates and are vulnerable to quantum attacks. Lattice-based schemes represent a recent advancement in RDH-ED by offering quantum resistance through security mechanisms based ...