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

DSpace Repository

A- A A+

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

Show full item record

Title: Algoritmos de programação linear com atributos de privacidade para o uso em computação segura multi-parte
Author: Deitos, Rafael José
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.
Description: Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-graduação em Engenharia de Automação e Sistemas, Florianópolis, 2009
URI: http://repositorio.ufsc.br/xmlui/handle/123456789/93097
Date: 2012-10-24


Files in this item

Files Size Format View
275396.pdf 1.533Mb PDF Thumbnail

This item appears in the following Collection(s)

Show full item record

Search DSpace


Advanced Search

Browse

My Account

Statistics

Compartilhar