Machine learning classification has a wide range of applications. In the big data era, a client may want to outsource classification tasks to reduce the computational burden at the client. Meanwhile, an entity may want to provide a classification model and classification services to such clients. However, applications such as medical diagnosis require sensitive data that both parties may not want to reveal. Fully homomorphic encryption (FHE) enables secure computation over encrypted data without decryption. By applying FHE, classification can be outsourced to a cloud without revealing any data. However, existing studies on classification over FHE do not achieve the scenario of outsourcing classification to a cloud while preserving the privacy of the classification model, client's data and result. In this work, we apply FHE to a naïve Bayes classifier and, to the best of our knowledge, propose the first concrete secure classification protocol that satisfies the above scenario.