Secure multiParty computation protocols

Abstract

Secure Multiparty Computation (abrv. MPC) is a group of techniques that enable multiple entities to compute some function on their private inputs. Moreformally,itenablesasetofplayers{P1,...,Pn},eachofthemholding private inputs xi, where i is the index of the player, to evaluate a function f(x1,...,xn) = (y1,...,yn) so that every player Pi learns yi. Multiparty Computation has many application scenarios such as private auctioning, computation outsourcing, or private information retrieval. These and other applications make MPC a very appealing object of study, since it may be a solution to problems in different fields. The objective of this thesis is twofold. First, we aim to provide a comprehensive guide to the current state of multiparty computation protocols. Wedosobyinspectingthetwocategorieswheremostgeneralfunctionality secure function evaluation protocols are inserted - boolean or arithmetic circuit evaluation. Moreover, we show how to implement MPC protocols with current constructions, and what problems are inherently connected to the chosen representations. Second, we document some of the design choices behind a partial implementation of a concrete secure arithmetic circuit evaluation protocol - the SPDZ protocol by Damgård et al. [10]. We explain the protocol in general terms, and then go into the details of some subprotocols, namely those that were implemented.

Secure Multiparty Computation (abrv. MPC) é uma área que engloba um conjunto de técnicas que permitem que diferentes entidades avaliem uma função sem revelar os seus valores privados. Formalmente, esta técnica permite a um conjunto de participantes {P1,...,Pn}, que possuem inputs privados xi, onde i é o índice de cada participante,avaliaremafunção f(x1,...,xn) = (y1,...,yn) deformaaque cada participante Pi obtenha unica e exclusivamente yi. Multiparty Computation destaca-se pelo facto de ser aplicável em diversas áreas como private auctioning, computation outsourcing ou private information retrieval. Estas aplicações tornam MPC um tópico de bastante interesse, pois engloba a solução para problemas de diferentes ramos. Esta dissertação é composta por duas partes. Primeiro, disponibilizamos um manual de introdução ao tópico, com o objectivo de descrever o estado actual da tecnologia. Com esse fim, introduzimos os dois grandes ramos onde todos os protocolos de avaliação genérica se enquadram - avaliação de circuitos booleanos ou avaliação de circuitos aritméticos. A nossa descrição engloba também aspectos práticos, como os recursos existentes em termos de frameworks para desenvolvimento de protocolos multiparty. Por fim, descrevemos os problemas que estão associados à escolha de uma representação em vez de outra. Na segunda parte, descrevemos algumas das decisões que foram tomadas aquando da implementação parcial do protocolo SPDZ de Damgård et al. [10]. Com esse objetivo, começamos por descrever o protocolo em termos gerais,e posteriormente explicamos o funcionamento em detalhe de alguns subprotocolos, nomeadamente os que foram implementados.