Abstract— Medical information is usually stored in a centralized database; its recently fast growth makes it even harder for the traditional local database center to handle over time. Investing in an effective data center locally is not a cost efficient; therefore, high-tech platforms are needed to manage these digital records. Today, cloud computing has become a promising paradigm for medical institutions to store and share their medical information since it offers large storage capacity and huge computing capabilities for a limited cost. On the other hand, it still has potential risks and challenges. However, outsourcing medical information to a public cloud storage provider causes the patient’s privacy and medical image security to become a critical concern. In this research, we proposed a novel and secure framework used for storing and sharing medical information over a public cloud based environment. Our approach relies on cryptography and steganography to protect medical information not only during transmission but also when it is stored on the cloud server that is managed by an untrusted party. For cryptography, our encryption algorithm MJEA (for Modified Jamal Encryption Algorithm) has been used; it is a symmetric block encryption algorithm with 64-bit block size and 120-bit key size. This algorithm is used to encrypt the medical image. The encrypted form of the medical image has been used as a cover image to hide the patient’s information and the encryption key. As a result, the security techniques used in the proposed framework ensure confidentiality, integrity and authenticity for medical information before outsourcing it to be stored on the cloud server.