Made available in DSpace on 2014-06-12T15:59:37Z (GMT). No. of bitstreams: 2 arquivo5353_1.pdf: 2899587 bytes, checksum: 5f8d77138fc281697613bf9ad7df021c (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 / A computação segura entre múltiplos participantes (MPC) é uma área de convergência entre estudos de criptografia e de sistemas distribuídos. Na MPC, assim como na computação distribuída, dois ou mais participantes colaboram na resolução de uma determinada tarefa. Esta tarefa a ser resolvida pode ser modelada através de uma função f (x1, ...,xn), onde cada entrada xi pertence a um participante diferente, e ao final da execução do protocolo, cada participante obterá apenas a sua saída pré-determinada e as entradas xi permanecerão secretas. Por exemplo, considere um conjunto de pessoas que deseja descobrir quem é o mais rico, entretanto nenhum deles quer revelar qual é o montante da sua fortuna (este problema é conhecido como o problema dos milionários e foi discutido pela primeira vez por Yao [Yao82]). Diversos estudos teóricos e práticos já foram realizados por pesquisadores da área e muitos avanços já foram dados em direção à resolução dos problemas MPC. De um lado se encontram os pesquisadores teóricos, que buscam esquemas genéricos capazes de solucionar qualquer problema computável, do outro lado, os pesquisadores práticos, na busca de soluções específicas para cada categoria de problema. Os estudos teóricos já conseguiram provar que existem soluções genéricas para qualquer problema computável, entretanto essas soluções requerem um enorme custo computacional, o que torna o seu uso inviável. Por atacar cada categoria de problema isoladamente, as pesquisas práticas conseguem produzir soluções viáveis, pois estudam as características inerentes a cada categoria, e se beneficiam destas características de forma a reduzir o custo computacional do protocolo. A proposta deste trabalho é desenvolver uma solução viável ao problema do substring MPC, e, para tanto, será utilizada uma abordagem prática. Considere dois participantes E e R que possuem os strings secretos SE e SR, respectivamente; o protocolo de substring MPC permite que o participante R descubra se o string SR é ou não substring de SE, sem que R tenha acesso ao string SE, nem E tenha acesso ao string SR. Finalmente, o protocolo de substring MPC será utilizado para a construção de um protocolo de consulta a banco de dados seguro, capaz de realizar consultas do tipo "SELECT * FROM funcionarios WHERE nome LIKE %joão% ", sem revelar ao servidor de banco de dados qual é o valor que está sendo procurado