Uma versão não-interativa do k-NN sobre dados cifrados

• Hilder V. L. Pereira Unicamp
• Diego F. Aranha Unicamp

DOI: https://doi.org/10.5753/sbseg.2016.19310

Resumo

Tarefas de aprendizagem de máquina normalmente exigem que grandes quantidades de dados sensíveis sejam compartilhados, o que é notoriamente intrusivo em termos de privacidade. Terceirizar esta computação para a nuvem requer que o servidor seja confiável, introduzindo um requisito de segurança não realista. Neste trabalho, propomos uma versão do classificador k-NN que pode ser executada na nuvem sobre dados cifrados de uma forma não interativa, combinando cifração que preserva a ordem e criptografia homomórfica. De acordo com nossos experimentos, a versão sobre dados cifrados alcança a mesma precisão que a convencional, mas com impactos consideráveis no desempenho original. Contudo, a penalidade de desempenho não é proibitiva e a solução continua viável para uso prático, quando as propriedades de segurança adicionais fornecidas são examinadas em detalhe. Em particular, o servidor em nuvem não precisa ser confiável para além da execução correta do protocolo e, como todos os dados recebidos são cifrados, o servidor não aprende os valores do conjunto de dados, o número de classes, os vetores a serem classificados nem as classes a eles atribuídas.

Referências

Alpaydin, E. (2004). Introduction to Machine Learning. The MIT Press.

Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician, 46(3):175–185.

Boldyreva, A., Chenette, N., Lee, Y., and O’Neill, A. (2009). Order-Preserving Symmetric Encryption. In Proceedings of the 28th Annual International Conference on Advances in Cryptology: The Theory and Applications of Cryptographic Techniques, EUROCRYPT ’09, pages 224–241, Berlin, Heidelberg. Springer-Verlag.

Bos, J. W., Lauter, K., Loftus, J., and Naehrig, M. (2013). Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme, pages 45–64. Springer Berlin Heidelberg, Berlin, Heidelberg.

Bost, R., Popa, R. A., Tu, S., and Goldwasser, S. (2014). Machine learning classification over encrypted data. Technical report, Cryptology ePrint Archive, Report 2014/331, 2014. http://eprint.iacr.org.

Choi, S., Ghinita, G., Lim, H.-S., and Bertino, E. (2014). Secure knn query processing in untrusted cloud environments. Knowledge and Data Engineering, IEEE Transactions on, 26(11):2818–2831.

Dowlin, N., Gilad-Bachrach, R., Laine, K., Lauter, K., Naehrig, M., and Wernsing, J. (2015). Manual for using homomorphic encryption for bioinformatics.

Dowlin, N., Gilad-Bachrach, R., Laine, K., Lauter, K., Naehrig, M., and Wernsing, J. (2016). Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. Technical Report MSR-TR-2016-3.

Elmehdwi, Y., Samanthula, B. K., and Jiang, W. (2014). Secure k-nearest neighbor query over encrypted data in outsourced environments. In Data Engineering (ICDE), 2014 IEEE 30th International Conference on, pages 664–675. IEEE.

Graepel, T., Lauter, K., and Naehrig, M. (2013). Ml confidential: Machine learning on encrypted data. In Information Security and Cryptology (ICISC), pages 1–21. Springer.

Hirt, M. and Sako, K. (2000). Efficient receipt-free voting based on homomorphic encryption. In Advances in Cryptology – EUROCRYPT, pages 539–556. Springer.

Jha, S., Kruger, L., and McDaniel, P. (2005). Privacy preserving clustering. In Computer Security (ESORICS), pages 397–417. Springer.

Lepoint, T. and Naehrig, M. (2014). A comparison of the homomorphic encryption schemes FV and YASHE. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8469 LNCS:318– 335.

Lindell, Y. and Pinkas, B. (2009). Secure multiparty computation for privacy-preserving data mining. Journal of Privacy and Confidentiality, 1(1):5.

Miller, C. C. (2014). Revelations of N.S.A. spying cost U.S. tech companies. The New York Times. [link]. (Acessed February 04, 2016).

Naehrig, M., Lauter, K., and Vaikuntanathan, V. (2011). Can homomorphic encryption be practical? In Proceedings of the 3rd ACM workshop on Cloud Computing Security, pages 113–124. ACM.

Naveed, M., Kamara, S., and Wright, C. V. (2015). Inference Attacks on Property-Preserving Encrypted Databases. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security - CCS ’15, pages 644–655.

Rivest, R. L., Adleman, L., and Dertouzos, M. L. (1978). On data banks and privacy homomorphisms. Foundations of secure computation, 4(11):169–180.

Wong,W. K., Cheung, D.W.-l., Kao, B., and Mamoulis, N. (2009). Secure kNN computation on encrypted databases. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 139–152. ACM.

Xiong, L., Chitti, S., and Liu, L. (2006). K nearest neighbor classification across multiple private databases. In Proceedings of the 15th ACM International Conference on Information and Knowledge Management, pages 840–841.

Xiong, L., Chitti, S., and Liu, L. (2007). Mining multiple private databases using a knn classifier. In Proceedings of the 2007 ACM Symposium on Applied Computing, SAC ’07, pages 435–440, New York, NY, USA. ACM.

Zhan, J., Chang, L., and Matwin, S. (2005). Privacy preserving k-nearest neighbor classification. International Journal of Network Security.

Zhu, Y., Xu, R., and Takagi, T. (2013). Secure k-nn computation on encrypted cloud data without sharing key with query users. In Proceedings of the 2013 International Workshop on Security in Cloud Computing, Cloud Computing ’13, pages 55–60, New York, NY, USA. ACM.