Reversible data hiding (RDH) for medical image applications has been widely researched in recent years due to its relevance in securely transmitting patient reports (PR) along with medical images. Researchers have explored various approaches for RDH, aiming to improve the embedding rate without compromising image restoration capabilities. RDH schemes can embed patient reports in medical images before transmission, allowing the receiving entity to extract the hidden reports for reference, while the restored images can be used for further diagnosis. Histogram shifting-based RDH (HS-RDH) schemes are popular due to their low complexity and sufficiently high embedding rates. However, a major constraint of all HS-RDH versions is handling overflow/underflow during embedding. Most existing RDH schemes overlook overflow/underflow, assuming it occurs infrequently. Those that address overflow/underflow often consume a significant portion of the embedding capacity to store handling information, ensuring the exact restoration of the original image after data extraction. In this paper, we introduce a multi-key encryption-based approach to embed overflow/underflow handling information within the same image through the encryption process. This scheme ensures that the actual embedding capacity of histogram shifting is utilized for embedding the actual data. Experimental studies of the proposed scheme have been conducted on both natural images (USC-SIPI dataset) and medical images. The main advantage of the proposed approach is its adaptability to any variant of HS-RDH schemes. In this paper, we focus on the basic HS-RDH scheme, but the proposed method can be applied to any variant.