Abstract: With the rapid development of cloud computing techniques and demand of privacy preservation,reversible data hiding(RDH) in homomorphic encrypted domain has become a hot research topic.Most of the existing RDH schemes in encrypted domain exploit correlations between adjacent pixels and redundancy in images,whose applications are limited.To improve applicabi-lity and embedding capacity,a new RDH scheme in NTRU encrypted domain based on polynomial partitioning is proposed.It divides the polynomial space in NTRU cryptosystem,which can be applied to multiple encrypted media content for data hiding.Part of the space is used to represent the original plaintext,while the rest space is used to hide the hidden data.The receiver can retrieve part of the hidden data directly from the ciphertext,while the rest hidden data can be extracted after decryption and the original plaintext can be correctly restored.In our experiments,grayscale images and text files are chosen to verify feasibility of the proposed scheme.Experimental results show that a maximum of N-8 bits can be hidden into a ciphertext for a plaintext represented with 8 bits,where N is a parameter used in NTRU cryptosystem.When N is set to 503,at most 495 bits can be hidden in a ciphertext while the plaintext can be exactly recovered.Compared with the existing schemes,the proposed scheme has higher embedding capacity and better applicability.

Key words: Reversible data hiding, NTRU cryptosystem, Polynomial partition, Lossless recovery, Embedding capacity