Secure spectral clustering

The approximation of eigenvectors in the integer domain

Master thesis (2017)

Authors

M.C. Steverink Electrical Engineering, Mathematics and Computer Science

Contributors

M.B. van Gijzen (mentor)
Thijs Veugen (mentor)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2017 Lisa Steverink
More Info
expand_more

Published Date

31-08-2017

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

In this thesis, the adaptation of the spectral clustering algorithm to the privacy preserving domain was investigated. The spectral clustering algorithm divides data points into clusters according to a measure of connectivity. A pivotal part of spectral clustering is the partial eigendecomposition of the graph Laplacian. Two numerical algorithms are used to approximate the eigenvectors of the Laplacian: the Lanczos algorithm and the QR algorithm. These numerical methods are adapted to work on Paillier encrypted data values. The main challenge is the fact that Paillier encryption can only be applied to a field of positive integers. Moreover, cryptographic protocols have to be invoked to perform non-linear operations. Also, the square root and division operations are computationally heavy in the privacy preserving domain. The numerical algorithms are adapted to overcome these challenges and be more suitable to work on encrypted values.