With　the　promotion　of　online　medical　pre-diagnosis　system,　more　and　more　research　has　begun　to　pay　attention　to　the　issue　of　privacy,　and　existing　privacy-preserving　schemes　are　designed　for　single-label　data.　However,　medical　users　may　infect　many　different　diseases　at　the　same　time,　it　is　necessary　to　take　multi-label　instances　into　account.　In　this　paper,　we　propose　an　efficient　and　privacy-preserving　multi-level　medical　pre-diagnosis　scheme,　called　CREDO,　which　based　on　multi-label　k-nearest-neighbors　(ML-kNN).　With　CREDO,　medical　users　can　ensure　their　sensitive　health　information　secure,　and　service　provider　can　provide　high-efficiency　service　without　revealing　pre-diagnosis　model　data.　Specifically,　service　provider　first　narrows　down　the　scope　of　medical　instances　needed　to　be　calculated　based　on　k-means　clustering,　then　provides　service　for　medical　users　based　on　ML-kNN　classification.　The　query　vector　is　encrypted　before　being　sent　out　and　directly　operated　in　the　service　provider,　meanwhile,　the　pre-diagnosis　result　can　only　be　achieved　by　the　medical　user.　Through　extensive　analysis,　we　show　that　CREDO　can　resist　multifarious　known　security　threats,　and　has　much　lower　computation　complexity　than　the　compared　scheme.　Moreover,　performance　evaluations　based　on　a　real　medical　dataset　demonstrate　that　our　proposed　scheme　is　highly　efficient　in　terms　of　computation　and　communication　overhead.　(C)　2019　Elsevier　Inc.　All　rights　reserved.