Due to the emerging of digital library and fast development of multimedia, more and more people use data hiding techniques to hide annotations or side information in images. In this paper, we propose a novel data hiding mechanism by hiding data based on pair-wise logical computation. The proposed mechanism can achieve the benefits of reversible and lossless reconstruction of hidden data and host image without utilizing any information from the original host image. It will not degrade the visual quality of the recovered host image after extracting the hidden data. Moreover, satisfactory data hiding capacity can be obtained simultaneously. The proposed data hiding mechanism is suitable to be applied to the data hiding of images, scanned texts, figures, and signatures, especially for side information and annotation data embedding.