Organizations use cloud service providers for outsourcing their data, since this includes advantages such as: scalability, security and no need for in house experts. Therefore, outsourcing data to cloud providers results in reduced costs. The disadvantage of outsourcing data to a cloud provider, is that organizations are not in control of their own data. When organizations are not in control of their data, they are subject to privacy risks. Privacy risks should be avoided, especially when sensitive data such as medical or financial records are involved. Therefore, organizations protect their data by only outsourcing encrypted data to cloud providers. However, data analysis on encrypted data is significantly reduced due to computational and communicational overhead. A commonly used data analysis method, such as k-Nearest Neighbour Search (k- NNS), is useful when for finding similar records in a database for a given query. Previous research shows success using k-NNS methods while preserving privacy, by using fully homomorphic encryption. However, previous solutions required the client to be online and help in the protocol, or make use of non-colluding servers. Therefore, we introduce our k-NNS protocol, which outsources all the work to the cloud server and the client is not involved in the computation. Our k-NNS protocol shows success on data sets used to test k-NNS applications, however is significantly slower than solutions which involve the client or non-colluding servers.