Third Party Data Clustering Over Encrypted Data Without Data Owner Participation: Introducing the Encrypted Distance Matrix

The increasing demand for Data Mining as a Service, using cloud storage, has raised data security concerns. Standard data encryption schemes are unsuitable because they do not support the mathematical operations that data mining requires. Homomorphic and Order Preserving Encryption provide a potential solution. Existing work, directed at data clustering, has demonstrated that using such schemes provides for secure data mining. However, to date, all proposed approaches have entailed some degree of data owner participation, in many cases the amount of participation is substantial. This paper proposes an approach to secure data clustering that does not require any data owner participation (once the data has been encrypted). The approach operates using the idea of an Encrypted Distance Matrix (EDM) which, for illustrative purposes, has been embedded in an approach to secure third-party data clustering - the Secure Nearest Neighbour Clustering (SNNC) approach, that uses order preserving and homomorphic encryption. Both the EDM concept and the SNNC approach are fully described.