In　this　article,　we　propose　a　privacy-preserving　medical　treatment　system　using　nondeterministic　finite　automata　(NFA),　hereafter　referred　to　as　P-Med,　designed　for　remote　medical　environment.　P-Med　makes　use　of　the　nondeterministic　transition　characteristic　of　NFA　to　flexibly　represent　medical　model,　which　includes　illness　states,　treatment　methods　and　state　transitions　caused　by　exerting　different　treatment　methods.　A　medical　model　is　encrypted　and　outsourced　to　cloud　to　deliver　telemedicine　service.　Using　P-Med,　patient-centric　diagnosis　and　treatment　can　be　made　on-the-fly　while　protecting　the　confidentiality　of　patient＇s　illness　states　and　treatment　recommendation　results.　Moreover,　a　new　privacy-preserving　NFA　evaluation　method　is　given　in　P-Med　to　get　a　confidential　match　result　for　the　evaluation　of　an　encrypted　NFA　and　an　encrypted　data　set,　which　avoids　the　cumbersome　inner　state　transition　determination.　We　demonstrate　that　P-Med　realizes　treatment　procedure　recommendation　without　privacy　leakage　to　unauthorized　parties.　We　conduct　extensive　experiments　and　analysis　to　evaluate　the　efficiency.　©　2013　IEEE.