Secure spectral clustering
The approximation of eigenvectors in the integer domain
M.C. Steverink (TU Delft - Electrical Engineering, Mathematics and Computer Science)
More Info
expand_more
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.
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.