Collecting and analyzing patients' e-healthcare data in Medical Internet-of-Things (MIOT), e-Healthcare providers can offer reliable medical services that will achieve better treatment for patients. For example, the diagnosis of disease and predictions of health offer an alternative and helpful evaluation of the risk of diseases, thereby helping patients lead a healthier life. However, e-Healthcare providers cannot cope with the huge volumes of data and respond to this online service such that a feasible solution is adopted to outsource the medical data to powerful medical cloud servers. Since medical data are very sensitive and outsourced servers are not fully trusted, a direct outsourcing decision tree evaluation service will inevitably result in huge privacy risks with regards to patient identity or original medical data. It is hard to hide the results of an evaluation from the single-server model unless a fully homomorphic cryptosystem is used, or the requester must communicat