In this paper, we propose privacy-enhancing technologies for medical tests and personalized medicine methods, which utilize patients' genomic data. First, we highlight the potential privacy threats on genomic data and the challenges of providing privacy-preserving algorithms. Then, focusing specifically on a typical disease-susceptibility test, we develop a new architecture (between the patient and the medical unit) and propose privacy-preserving algorithms by utilizing homomorphic encryption and proxy encryption. Assuming the whole genome sequencing is done by a certified institution, we propose to store patients' genomic data encrypted by their public keys at a Storage and Processing Unit (SPU). The proposed algorithm lets the SPU (or the medical unit) process the encrypted genomic data for medical tests and personalized medicine methods while preserving the privacy of patients' genomic data. We extensively analyze the relationship between the storage cost (of the genomic data), the level of genomic privacy (of the patient), and the characteristics of the genomic data. Furthermore, we implement and show via a complexity analysis the practicality of the proposed schemes. Finally, we evaluate the security of the proposed schemes and propose new research directions on genomic privacy.