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.

Keywords

Reversible data hiding / NTRU cryptosystem / Chinese remainder theorem (CRT) / Multichannel redundancy

References

[1] Hoffstein J , Pipher J , Silverman JH , et al., 1998. NTRU:a ring-based public key cryptosystem. Int Algorithmic Number Theory Symp, p.267-288.

[2] Hoffstein J , Howgrave-Graham N , Pipher J , et al., 2003. NTRUSign:digital signatures using the NTRU lattice. Topics in Cryptology-CT-RSA, p.122-140.

[3] Ke Y , Zhang MQ , Su TT , 2016.. A novel multiple bits reversible data hiding in encrypted domain based on R-LWE. J Comput Res Dev, 53 (10): 2307- 2322 (in Chinese).

[4] Kong YJ , Zhang MQ , Jiang ZB , et al., 2024.. A fine-grained reversible data hiding in encrypted domain based on the cipher-text redundancy of encryption process. Heliyon, 10 (11): e31542.

[5] Lin WB , Zhang MQ , Guo S , et al., 2021.. Separable reversible data hiding in encrypted domain based on Paillier. Appl Res Comput, 38 (10): 3161- 3165 (in Chinese).

[6] Liu DC , Wu HT , Zhuang ZW , et al., 2023.. Reversible data hiding scheme in NTRU encrypted domain based on polynomial partition. Comput Sci, 50 (8): 294- 303 (in Chinese).

[7] Liu JF , Han T , Tian YG , et al., 2015.. Reversible data hiding in encrypted images using recompression. J Commun, 36 (9): 13- 25 (in Chinese).

[8] Ma KD , Zhang WM , Zhao XF , et al., 2013.. Reversible data hiding in encrypted images by reserving room before encryption. IEEE Trans Inform Forens Secur, 8 (3): 553- 562.

[9] Malik A , Ashraf A , Wu HZ , et al., 2022. Reversible data hiding in encrypted text using Paillier cryptosystem. Asia-Pacific Signal and Information Processing Association Annual Summit and Conf, p.1495-1499.

[10] Qi KL , Zhang MQ , Di FQ , et al., 2023.. High capacity reversible data hiding in encrypted images based on adaptive quadtree partitioning and MSB prediction. Front Inform Technol Electron Eng, 24 (8): 1156- 1168.

[11] Tang X , Zhou LN , Liu D , et al., 2020. Reversible data hiding based on improved rhombus predictor and prediction error expansion. IEEE 19^th Int Conf on Trust, Security and Privacy in Computing and Communications, p.13-21.

[12] Tang X , Zhou LN , Tang G , et al., 2022a. Improved fluctuation derived block selection strategy in pixel value ordering based reversible data hiding. Proc 20^th Int Workshop on Digital Forensics and Watermarking, p.163-177.

[13] Tang X , Zhou YT , Cheng YX , et al., 2022b.. Weighted average-based complexity calculation in block selection oriented reversible data hiding. Secur Commun Netw, 2022: 5225978.

[14] Wang C , Han YL , Duan XW , et al., 2021.. NTRU-type proxy reencryption scheme based on RLWE difficult assumption. J Cryptol Res, 8 (5): 909- 920 (in Chinese).

[15] Wu HT , Cheung YM , Tian ZH , et al., 2024.. Lossless data hiding in NTRU cryptosystem by polynomial encoding and modulation. IEEE Trans Inform Forens Secur, 19: 3719- 3732.

[16] Wu HT , Chen YQ , Cheung YM , et al., 2025.. BGN encryption based lossless data hiding by random number replacement and partitioning. IEEE Trans Depend Secur Comput, 22 (8): 8043- 8055.

[17] Yi S , Zhou YC , 2017.. Binary-block embedding for reversible data hiding in encrypted images. Signal Process, 133: 40- 51.

[18] Zhang MQ , Ke Y , Su TT , 2016. Reversible steganography in encrypted domain based on LWE. J Electron Inform Technol, 38 (2): 354- 360(in Chinese).

[19] Zhang TJ , Li ZC , 2022.. Research on image reversible double watermarking algorithm in ciphertext domain based on NTRU. Softw Eng Appl, 11 (3): 504- 515 (in Chinese).

[20] Zhang XP , Long J , Wang ZC , et al., 2016.. Lossless and reversible data hiding in encrypted images with public-key cryptography. IEEE Trans Circ Syst Video Technol, 26 (9): 1622- 1631.

[21] Zhou N , Zhang MQ , Tang HQ , et al., 2020.. Reversible data hiding algorithm in encrypted domain based on NTRU. Sci Technol Eng, 20 (32): 13285- 13294 (in Chinese).

[22] Zhou ZY , Wang CY , Yan KX , et al., 2024.. Reversible data hiding in encrypted images based on additive secret sharing and additive joint coding using an intelligent predictor. Front Inform Technol Electron Eng, 25 (9): 1250- 1265.

RIGHTS & PERMISSIONS

The Authors. Published by Zhejiang University Press Co., Ltd.