Online medical primary diagnosis system, which can provide convenient medical decision support through applying mobile communication and data analysis technology, has been considered as a promising approach to improve the quality of healthcare service. However, it still faces many severe challenges on the privacy of users' health information and the accuracy of diagnosis result, which deter the wide adoption of online medical primary diagnosis system. In this paper, we propose an efficient and privacy-preserving online medical primary diagnosis (CINEMA) framework. Within CINEMA framework, users can access online medical primary diagnosing service accurately without divulging their medical data. Specifically, based on fast secure permutation and comparison technique, the encrypted user's query is directly operated at the service provider (SP) without decryption, and the diagnosis result can only be decrypted by the user, meanwhile, the diagnosis model in SP can also be protected. Through extensive analysis, we show that CINEMA can ensure that user's health information and healthcare SP's diagnosis model are kept confidential, and has significantly reduce computation and communication overhead. In addition, performance evaluations via implementing CINEMA demonstrate its effectiveness in term of the real environment.