The rapid adoption of cloud computing in healthcare has improved data accessibility but introduced significant challenges in privacy preservation. This study presents a secure cloud-based framework for medical pre-diagnosis using encrypted machine learning techniques. The proposed approach applies matrix- based encryption and a privacy-preserving Mahalanobis distance mechanism to enable classification directly on protected data. A hybrid model combining K- Nearest Neighbor (KNN) with ensemble methods such as Random Forest and XGBoost is used to enhance predictive accuracy and robustness. To improve efficiency, a hierarchical indexing structure is incorporated for faster retrieval of encrypted records, while a trapdoor-based query mechanism ensures secure inter- action without revealing sensitive inputs. Experimental evaluation demonstrates that the framework achieves accuracy above 98% with low computational over- head. The results confirm that the proposed system effectively balances security, efficiency, and predictive performance, making it suitable for scalable and reliable cloud-based healthcare analytics.