Welcome to the resource topic for 2023/852
Title:
Efficient and Secure k-NN Classification from Improved Data-Oblivious Programs and Homomorphic Encryption
Authors: Kelong Cong, Robin Geelen, Jiayi Kang, Jeongeun Park
Abstract:The k-nearest neighbors classifier is a simple machine learning algorithm with applications in image recognition, finance, medical diagnosis and so on. It involves a measurement which is compared against a database of preclassified vectors, so that the result depends on the k vectors in the database that are closest to the measurement. In the client-server model, this classification process can be outsourced to an external party that offers machine learning as a service, where the measurement is sent in the form of a query. However, this raises privacy concerns if sensitive information is contained in the query.
We design a secure and non-interactive version of the k-nearest neighbors classifier, based on fully homomorphic encryption, which does not leak any information about the query to the server. Our algorithm is instantiated with the TFHE homomorphic encryption scheme, and the selection of the top-k elements is done with a novel strategy based on a type of data-oblivious algorithm—sorting networks. Compared to prior work from PoPETs 2021, the asymptotic complexity is improved from O(d^2) to O(d \log^2 {k}), where d is the number of entries in the k-NN model. Experimental results show that the proposed protocol can be up to 16 times faster (not accounting for difference in CPU) than previous approaches for a moderately sized database.
ePrint: https://eprint.iacr.org/2023/852
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .