La clasificación se utiliza en varias áreas donde la clasificación del vecino más cercano es la más popular ya que produce resultados eficientes. La computación en la nube con recursos potentes es una opción confiable para manejar datos a gran escala de manera eficiente, pero muchas empresas dudan en externalizar datos debido a preocupaciones de privacidad. Este documento tiene como objetivo implementar una clasificación del vecino más cercano (PNC) preservando la privacidad en un entorno externalizado. El trabajo existente propuso un protocolo seguro (SLE/SSE) para calcular datos con el valor más grande/más pequeño de forma privada, pero este trabajo revela información. Además, SLE/SSE requiere un protocolo de comparación seguro, y los protocolos existentes también presentan problemas de revelación de información. En este documento, proponemos un nuevo protocolo de comparación seguro y protocolos SLE/SSE para resolver los problemas de revelación de información mencionados anteriormente e implementar PNC con estos nuevos protocolos. Nuestros protocolos propuestos no revelan información y demostramos la seguridad de forma formal. Luego, a través de experimentos extensos, demostramos que el PNC aplicando los protocolos propuestos también es eficiente. Especialmente, el PNC es adecuado para el análisis de grandes volúmenes de datos para manejar grandes cantidades de datos, ya que nuestro SLE/SSE se ejecuta para cada conjunto de datos en paralelo. Aunque los protocolos propuestos requieren sacrificios de eficiencia para mejorar la seguridad, el tiempo de ejecución de nuestro PNC sigue siendo significativamente más eficiente en comparación con los PNC propuestos anteriormente.