Tarefas de aprendizagem de máquina normalmente exigem que grandes quantidades de dados sensíveis sejam compartilhados, o que é notoriamente intrusivo em termos de privacidade. Terceirizar esta computação para a nuvem requer que o servidor seja confiável, introduzindo um requisito de segurança não realista. Neste trabalho, propomos uma versão do classificador $k$-NN que pode ser executada na nuvem sobre dados cifrados de uma forma não interativa, combinando cifração que preserva a ordem e criptografia homomórfica. De acordo com nossos experimentos, a versão sobre dados cifrados alcança a mesma precisão que a convencional, mas com impactos consideráveis no desempenho original. Contudo, a penalidade de desempenho não é proibitiva e a solução continua viável para uso prático, quando as propriedades de segurança adicionais fornecidas são examinadas em detalhe. Em particular, o servidor em nuvem não precisa ser confiável para além da execução correta do protocolo e, como todos os dados recebidos são cifrados, o servidor não aprende os valores do conjunto de dados, o número de classes, os vetores a serem classificados nem as classes a eles atribuídas.