Formalized threshold reversible hiding in encrypted images in Post-Quantum settings

Abstract As advancements in computer vision emerge, the necessity for securing image processing techniques also arises. For this purpose, one of the promising methods is Reversible Data Hiding in Encrypted Images (RDHEI), which directly secures visual data while providing the option of embedding auxiliary information. However, RDHEI has not been formalized in the cryptographic context. The absence of such formalization leads to a lack of provable security guarantees and robust privacy comparisons between schemes. In this work, we address this gap by formalizing RDHEI, where we formally define the syntax, correctness properties, and security notions, including semantic security, payload privacy, separability, compactness, and robustness. Then, we construct Post-Quantum RDHEI (PQ-RDHEI) as an efficient scheme secure against quantum adversaries under the Module Learning With Errors assumption in the quantum random oracle model. Our design uses a Module Lattice Key Encapsulation Mechanism, pseudorandom functions, hash functions, and verifiable secret sharing as building blocks. The quantitative experiments show that on the standard grayscale test images, our PQ-RDHEI achieves embedding rates of 0.61-2.27 bits per pixel against 0.04-0.18 bits per pixel for the most efficient existing scheme, along with a $$13.4\times $$ improvement in mean rate, and raises the entropy of the encrypted shares from 7.48 to 7.9902-7.9992 bits per pixel.