Storing and sharing of medical data in the cloud environment, where computing resources including storage is provided by a third party service provider, raise serious concern of individual privacy for the adoption of cloud computing technologies. Existing privacy protection researches can be classified into three categories, i.e., privacy by policy, privacy by statistics, and privacy by cryptography. However, the privacy concerns and data utilization requirements on different parts of the medical data may be quite different. The solution for medical dataset sharing in the cloud should support multiple data accessing paradigms with different privacy strengths. The statistics or cryptography technology alone cannot enforce the multiple privacy demands, which blocks their application in the real-world cloud. This paper proposes a practical solution for privacy preserving medical record sharing for cloud computing. Based on the classification of the attributes of medical records, we use vertical partition of medical dataset to achieve the consideration of different parts of medical data with different privacy concerns. It mainly includes four components, i.e., (1) vertical data partition for medical data publishing, (2) data merging for medical dataset accessing, (3) integrity checking, and (4) hybrid search across plaintext and ciphertext, where the statistical analysis and cryptography are innovatively combined together to provide multiple paradigms of balance between medical data utilization and privacy protection. A prototype system for the large scale medical data access and sharing is implemented. Extensive experiments show the effectiveness of our proposed solution. •Proposed a hybrid solution for privacy preserving data sharing in cloud environment.•Different methods are innovatively combined to support multiple paradigms of medical data sharing with different privacy strengths.•The experimental evaluations are reported based on the implementation of four basic components and a real world case study.