Abstract
“Machine learning as a service” (MLaaS) in the cloud accelerates the adoption of machine learning techniques. Nevertheless, the externalization of data on the cloud raises a serious vulnerability issue because it requires disclosing private data to the cloud provider. This paper deals with this problem and brings a solution for the K-nearest neighbors (k-NN) algorithm with a homomorphic encryption scheme (called TFHE) by operating on end-to-end encrypted data while preserving privacy. The proposed solution addresses all stages of k-NN algorithm with fully encrypted data, including the majority vote for the class-label assignment. Unlike existing techniques, our solution does not require intermediate interactions between the server and the client when executing the classification task. Our algorithm has been assessed with quantitative variables and has demonstrated its efficiency on large and relevant real-world data sets while scaling well across different parameters on simulated data.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Al Badawi, A., et al.: Towards the AlexNet moment for homomorphic encryption: HCNN, the first homomorphic CNN on encrypted data with GPUs. IEEE Trans. Emerg. Top. Comput. 9(3), 1330–1343 (2021)
Bourse, F., Minelli, M., Minihold, M., Paillier, P.: Fast homomorphic evaluation of deep discretized neural networks. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 483–512. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_17
Brutzkus, A., Elisha, O., Gilad-Bachrach, R.: Low latency privacy preserving inference. Ar**v, abs/1812.10659 (2019)
Çetin, G.S., Doröz, Y., Sunar, B., Savaş, E.: Depth optimized efficient homomorphic sorting. In: Lauter, K., Rodríguez-Henríquez, F. (eds.) LATINCRYPT 2015. LNCS, vol. 9230, pp. 61–80. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22174-8_4
Chabanne, H., de Wargny, A., Milgram, J., Morel, C., Prouff, E.: Privacy-preserving classification on deep neural network. IACR Cryptology ePrint Archive 2017/35 (2017)
Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: TFHE: fast fully homomorphic encryption library, August 2016. https://tfhe.github.io/tfhe/
Hesamifard, E., Takabi, H., Ghasemi, M.: CryptoDL: deep neural networks over encrypted data. Ar**v, abs/1711.05189 (2017)
Izabachène, M., Sirdey, R., Zuber, M.: Practical fully homomorphic encryption for fully masked neural networks. In: Mu, Y., Deng, R.H., Huang, X. (eds.) CANS 2019. LNCS, vol. 11829, pp. 24–36. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-31578-8_2
Li, F., Shin, R., Paxson, V.: Exploring privacy preservation in outsourced k-nearest neighbors with multiple data owners. In: Proceedings of the 2015 ACM Workshop on Cloud Computing Security Workshop, CCSW 2015, pp. 53–64. Association for Computing Machinery, New York (2015)
Masters, O., Hunt, H., Steffinlongo, E., Crawford, J., Bergamaschi, F.: Towards a homomorphic machine learning big data pipeline for the financial services sector. IACR Cryptology ePrint Archive 2019/1113 (2019)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16
Pulido-Gaytan, B., et al.: Privacy-preserving neural networks with homomorphic encryption: challenges and opportunities. Peer-to-Peer Netw. Appl. 14(3), 1666–1691 (2021). https://doi.org/10.1007/s12083-021-01076-8
Samanthula, B.K., Elmehdwi, Y., Jiang, W.: k-nearest neighbor classification over semantically secure encrypted relational data. IEEE Trans. Knowl. Data Eng. 27(5), 1261–1273 (2015)
Wong, W.K., Cheung, D.W., Kao, B., Mamoulis, N.: Secure kNN computation on encrypted databases. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, SIGMOD 2009, pp. 139–152. Association for Computing Machinery, New York (2009)
**ao, X., Li, F., Yao, B.: Secure nearest neighbor revisited. In: Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013), USA, pp. 733–744. IEEE Computer Society (2013)
Zuber, M., Sirdey, R.: Efficient homomorphic evaluation of k-NN classifiers. In: Proceedings on Privacy Enhancing Technologies 2021, pp. 111–129 (2021)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Ameur, Y., Aziz, R., Audigier, V., Bouzefrane, S. (2022). Secure and Non-interactive k-NN Classifier Using Symmetric Fully Homomorphic Encryption. In: Domingo-Ferrer, J., Laurent, M. (eds) Privacy in Statistical Databases. PSD 2022. Lecture Notes in Computer Science, vol 13463. Springer, Cham. https://doi.org/10.1007/978-3-031-13945-1_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-13945-1_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-13944-4
Online ISBN: 978-3-031-13945-1
eBook Packages: Computer ScienceComputer Science (R0)