Algoritmos de programação linear com atributos de privacidade para o uso em computação segura multi-parte

Abstract

Tradicionalmente a pesquisa na área de segurança tem focado na proteção contra ataques externos e internos. No entanto, recentemente, com modelos de negócios em rede, uma nova ameaça de segurança surgiu: o parceiro de negócios. Otimização de Cadeias Logísticas (CL) é um exemplo onde o compartilhamento de informação pode melhorar drasticamente o desempenho de toda a cadeia. Apesar de tais problemas poderem ser modelados e resolvidos utilizando-se programação linear, requisitos de segurança impedem a sua implementação de maneira tradicional. Entre as diversas medidas de segurança já conhecidas, computação segura multi-parte (CSM) é a única a oferecer a garantia de segurança necessária enquanto computa o problema de otimização da cadeia logística. CSM é uma técnica criptográfica que permite que um conjunto de participantes computem uma função conjunta sem que seja necessária a revelação de informação. Um dos maiores desafios de CSM é a sua realização prática. Esta dissertação tem seu foco em algoritmos de programação linear com preservação da privacidade para o uso em computação segura multi-parte que podem ser utilizados na resolução de problemas de otimização da cadeia logística. Para essa classe de problemas, existem protocolos onde a seleção do índice do elemento pivô é realizada em claro. A primeira contribuição é um esquema probabilístico para a redução do número de permutações seguras requerido pelo protocolo seguro e privado de programação linear colaborativa. Nossa solução é capaz de reduzir em aproximadamente 40% o número de permutações seguras ao custo da revelação de uma pequena quantidade de informação, além de ser capaz de controlar a relação entre segurança e desempenho de tal protocolo. Nossa segunda contribuição compreende a introdução de dois protocolos seguros para permutação multi-parte. Primeiramente, propõe-se um protocolo com complexidade linear no número de participantes e comunicação. Considerando-se cenários reais onde as cadeias logísticas são formadas por vários participantes usualmente dispersos e, considerando-se também as condições da rede de comunicação, propõe-se um segundo protocolo com complexidade de base logarítmica. É feito um estudo detalhado e uma análise de tais protocolos além de uma avaliação, na prática, das melhorias observadas quando da utilização do algoritmo de base logarítmica. Resultados experimentais revelam uma forte relação entre o número de participantes, condições da rede, complexidade de rodadas e poder de paralelização, quando se considera a otimização do desempenho de protocolos de CSM. Adicionalmente, pode-se considerar protocolos de CSM onde o índice do elemento pivô é mantido como uma variável criptografada. Computação com valores criptografados é bastante cara e, as melhores soluções conhecidas normalmente se beneficiam de computação paralela para a redução dos custos computacionais e de comunicação. Nosso foco é otimizar a utilização dos processadores de máquinas multi-core/processor quando da resolução de programas lineares seguros. Para tal, duas abordagens de programação linear segura em paralelo são comparadas e uma delas é implementada. Dada esta implementação, o desempenho é praticamente independente das condições da rede de comunicação, mas o paralelismo, ou seja, o número de threads, precisa ser adaptado para a optimalidade. Nossa última contribuição consiste em um algoritmo de agendamento adaptativo para a seleção dinâmica do número de threads, de modo que não é necessário determinar-se tal número estaticamente e a priori para um speed-up ótimo. O algoritmo pode ainda lidar com variações nas condições da rede e é capaz de alcançar desempenho próximo da optimalidade.