Machine learning over encrypted data
Hilder V. L. Pereira · 2016
A ata da defesa com as respectivas assinaturas dos membros da banca encontra-se no processo de vida acadêmica do aluno.Campinas, 23 de setembro de 2016 I would like to thank the laboratories LASCA and LMCAD and their members for receiving me and providing resources to perform my research.I am also grateful to Google for the grants they awarded me.They were very important to give me comfortable conditions to study and participate on conferences and workshops.I certainly have a lot of professors to thank, but two of them deserve special acknowledgements: first, professor Diego Aranha, my advisor, for using his experience to guide me in a way that allowed me to obtain good results, by all his suggestions and recommendations, and also for being a pleasant person whom it is easy and nice to work with; the second one is professor Alfredo Goldman, whom I have to thank for being a great person and for helping me infinitely.Without him, I would not be finishing my Masters now.And the most heartful acknowledgements are for my mother, Ana Lícia Lima Pereira, and for my father, Hilmar Rodrigues Pereira, who despite all the socioeconomic pressure and difficulties, were able to cleverly see the opportunities that the formal education could give me and to artfully supply me the means to begin my undergraduate course.I will be eternally grateful to you both. ResumoAprendizado de máquina normalmente exige que grandes quantidades de dados sensíveis sejam compartilhados, o que é notoriamente intrusivo em termos de privacidade.Sendo assim, terceirizar a computação de tais algoritmos para a nuvem requer que o servidor seja confiável, o que introduz um pressuposto de segurança não-realista e com alto risco de abusos ou violações.Mas se a nuvem fosse capaz de realizar cálculos sobre dados cifrados, ao invés de computar sobre dados às claras, como de costume, os clientes poderiam então cifrar seus dados antes de enviá-los à nuvem, minimizando as suposições de segurança feitas sobre o servidor.Neste trabalho, são propostas versões que preservam a privacidade do classificador k-NN e do algoritmo para Análise de Componentes Principais que podem ser executadas sobre dados cifrados.Os algoritmos para Análise de Componentes Principais são baseados em esquemas de criptografia homomórfica, enquanto as versões do k-NN (uniforme e ponderado) apresentadas aqui combinam criptografia que preserva a ordem com criptografia homomórfica.Os resultados experimentais mostram que as variantes privativas do k-NN alcançam a mesma precisão que o classificador k-NN convencional, mas com impactos consideráveis no desempenho.No entanto, essa penalidade no tempo de execução não significa que as soluções não podem ser usadas na prática quando as propriedades de segurança fornecidas pela abordagem são examinadas em detalhe.Os algoritmos propostos para a Análise de Componentes Principais têm profundidade multiplicativa linear no número de componentes a serem encontradas, mas mesmo assim, os tempos de execução ainda são proibitivos, principalmente devido à falta de técnicas eficientes para codificar os valores de dupla precisão dos conjuntos de dados para textos claros do esquema homomórfico utilizado na execução.Para ambos os algoritmos propostos, o servidor em nuvem não precisa ser confiável para além da correta execução do protocolo (modelo semi-honesto) e pode avaliar os algoritmos sobre dados cifrados, não aprendendo assim os valores do conjunto de dados original nem as respostas devolvidas, já que as saídas de algoritmos homomórficos são também cifradas.