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.　©　2014　IEEE.