A computação multi-partes segura (também conhecida como computação segura, computação multi-partes (MPC) ou computação voltada à preservação da privacidade) é um subcampo da criptografia com o objetivo de criar métodos para que várias partes computem conjuntamente uma função sobre suas entradas, mantendo essas entradas privadas. Ao contrário das tarefas criptográficas tradicionais, onde a criptografia garante a segurança e a integridade da comunicação ou do armazenamento e o adversário está fora do sistema de participantes (um interceptador entre o remetente e o receptor), a criptografia neste modelo protege a privacidade dos participantes uns dos outros.
As bases para a computação multi-partes segura começaram no final da década de 1970 com o trabalho sobre pôquer mental, um trabalho criptográfico que simula jogos ou tarefas computacionais a distância sem a necessidade de uma terceira parte confiável. Tradicionalmente, a criptografia tratava de ocultar conteúdo, enquanto este novo tipo de computação e protocolo trata de ocultar informações parciais sobre os dados enquanto se computa com dados de várias fontes, produzindo saídas corretas. No final da década de 1980, Michael Ben-Or, Shafi Goldwasser e Avi Wigderson, e independentemente David Chaum, Claude Crépeau e Ivan Damgård, publicaram artigos mostrando "como computar com segurança qualquer função no cenário de canais seguros".
História Protocolos de propósito específico para tarefas específicas começaram no final da década de 1970.A. Shamir, R. Rivest, and L. Adleman, "Mental Poker", Technical Report LCS/TR-125, Massachusetts Institute of Technology, April 1979. Mais tarde, a computação segura foi formalmente introduzida como computação de duas partes segura (2PC) em 1982 (para o chamado Problema dos Milionários, um problema específico que é um predicado booleano), e de forma generalizada (para qualquer computação viável) em 1986 por Andrew Yao.Andrew C. Yao, Protocols for secure computations (extended abstract)Andrew Chi-Chih Yao:How to Generate and Exchange Secrets (Extended Abstract). FOCS 1986: 162-167 A área também é referida como Avaliação de Função Segura (SFE). O caso de duas partes foi seguido por uma generalização para multi-partes por Oded Goldreich, Silvio Micali e Avi Wigderson. A computação baseia-se no compartilhamento de segredo de todas as entradas e em provas de conhecimento zero para um caso potencialmente malicioso, onde a maioria de jogadores honestos no cenário de adversário malicioso garante que o comportamento inadequado seja detectado e a computação continue com a pessoa desonesta eliminada ou sua entrada revelada. Este trabalho sugeriu o esquema geral básico a ser seguido por essencialmente todos os futuros protocolos multi-partes para computação segura.Oded Goldreich, Silvio Micali, Avi Wigderson:How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. STOC 1987: 218-229 Este trabalho introduziu uma abordagem, conhecida como paradigma GMW, para compilar um protocolo de computação multi-partes que é seguro contra adversários semi-honestos em um protocolo que é seguro contra adversários maliciosos. Este trabalho foi seguido pelo primeiro protocolo seguro robusto que tolera comportamentos falhos graciosamente sem revelar a saída de ninguém, através de um trabalho que inventou para este propósito a frequentemente utilizada "ideia de compartilhamento de compartilhamentos"Zvi Galil, Stuart Haber, Moti Yung: Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model. CRYPTO 1987: 135-155 e um protocolo que permite que uma das partes oculte sua entrada incondicionalmente.David Chaum, Ivan Damgård, Jeroen van de Graaf: Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result. 87-119 O paradigma GMW foi considerado ineficiente por anos devido às enormes sobrecargas que traz ao protocolo base. No entanto, foi demonstrado que é possível alcançar protocolos eficientes, o que torna esta linha de pesquisa ainda mais interessante de uma perspectiva prática. Os resultados acima estão em um modelo onde o adversário é limitado a computações em tempo polinomial e observa todas as comunicações, sendo, portanto, chamado de "modelo computacional". Além disso, o protocolo de transferência inconsciente demonstrou ser completo para estas tarefas.Joe Kilian: Founding Cryptography on Oblivious Transfer. STOC 1988: 20-31 Os resultados acima estabeleceram que é possível, sob as variações mencionadas, alcançar a computação segura quando a maioria dos usuários é honesta.
A próxima questão a ser resolvida foi o caso de canais de comunicação segura onde a comunicação ponto-a-ponto não está disponível para o adversário; neste caso, foi mostrado que soluções podem ser alcançadas com até 1/3 das partes agindo de forma inadequada e maliciosa, e as soluções não aplicam ferramentas criptográficas (já que a comunicação segura está disponível).Michael Ben-Or, Shafi Goldwasser, Avi Wigderson: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). STOC 1988: 1-10 A adição de um canal de difusão (broadcast) permite que o sistema tolere até 1/2 de minoria malcomportada,Tal Rabin, Michael Ben-Or: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract). STOC 1989: 73-85 enquanto as restrições de conectividade no grafo de comunicação foram investigadas no livro Perfectly Secure Message Transmission.Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung: Perfectly Secure Message Transmission. J. ACM 40(1): 17-47 (1993)
Ao longo dos anos, a noção de protocolos multi-partes de propósito geral tornou-se uma área fértil para investigar propriedades básicas e gerais de protocolos, como a composição universal ou adversário móvel, como no compartilhamento de segredo proativo.Rafail Ostrovsky, Moti Yung: How to Withstand Mobile Virus Attacks. PODC 1991. pp. 51-59
Desde o final dos anos 2000, e certamente a partir de 2010, o domínio dos protocolos de propósito geral passou a lidar com melhorias de eficiência dos protocolos com aplicações práticas em mente. Protocolos cada vez mais eficientes para MPC foram propostos, e o MPC pode agora ser considerado uma solução prática para vários problemas da vida real (especialmente aqueles que requerem apenas o compartilhamento linear de segredos e principalmente operações locais sobre as fatias com pouca interação entre as partes), tais como votação distribuída, licitações e leilões privados, compartilhamento de funções de assinatura ou descriptografia e recuperação de informação privada.Claudio Orlandi: Is multiparty computation any good in practice?, ICASSP 2011 A primeira aplicação prática e em larga escala de computação multi-partes foi a execução de um leilão duplo eletrônico no Leilão de Beterraba Açucareira da Dinamarca, ocorrido em janeiro de 2008. Obviamente, são necessárias tanto noções teóricas e investigações quanto construções aplicadas (por exemplo, as condições para transformar o MPC em parte dos negócios cotidianos foram defendidas e apresentadas emMoti Yung: From Mental Poker to Core Business: Why and How to Deploy Secure Computation Protocols? ACM Conference on Computer and Communications Security 2015: 1-2 https://dl.acm.org/citation.cfm?doid=2810103.2812701).
Em 2020, uma série de empresas que trabalham com computação multi-partes segura fundaram a MPC Alliance com o objetivo de "acelerar a conscientização, aceitação e adoção da tecnologia MPC".
Definição e visão geral Em um MPC, um dado número de participantes, p1, p2, ..., pN, cada um possui dados privados, respectivamente d1, d2, ..., dN. Os participantes desejam computar o valor de uma função pública sobre esses dados privados: F(d1, d2, ..., dN) enquanto mantêm suas próprias entradas em segredo.
Por exemplo, suponha que tenhamos três partes Alice, Bob e Charlie, com as respectivas entradas x, y e z denotando seus salários. Eles querem descobrir qual o maior dos três salários, sem revelar uns aos outros quanto cada um ganha. Matematicamente, isso se traduz na computação de:
Se houvesse alguma parte externa confiável (digamos, se eles tivessem um amigo mútuo, Tony, que soubessem que poderia guardar segredo), cada um poderia contar seu salário ao Tony, ele calcularia o máximo e diria esse número a todos eles. O objetivo do MPC é projetar um protocolo onde, trocando mensagens apenas entre si, Alice, Bob e Charlie ainda possam aprender sem revelar quem ganha o quê e sem ter que depender do Tony. Eles não devem aprender mais ao participar do protocolo do que aprenderiam interagindo com um Tony incorruptível e perfeitamente confiável.
Em particular, tudo o que as partes podem aprender é o que podem inferir da saída e da sua própria entrada. Portanto, no exemplo acima, se a saída for , então Charlie aprende que seu é o valor máximo, enquanto Alice e Bob aprendem (se , e forem distintos) que sua entrada não é igual ao máximo, e que o máximo detido é igual a . O cenário básico pode ser facilmente generalizado para casos onde as partes têm várias entradas e saídas, e a função produz valores diferentes para partes diferentes.
Informalmente falando, as propriedades mais básicas que um protocolo de computação multi-partes visa garantir são: Privacidade de entrada: Nenhuma informação sobre os dados privados detidos pelas partes pode ser inferida a partir das mensagens enviadas durante a execução do protocolo. A única informação que pode ser inferida sobre os dados privados é o que puder ser inferido pela visualização da saída da função isoladamente. Correção: Qualquer subconjunto adequado de partes adversárias em conluio, dispostas a compartilhar informações ou desviar-se das instruções durante a execução do protocolo, não deve ser capaz de forçar as partes honestas a produzir um resultado incorreto. Este objetivo de correção vem em dois sabores: ou as partes honestas têm a garantia de computar a saída correta (um protocolo "robusto"), ou elas abortam se encontrarem um erro (um protocolo MPC "com aborto").
Existe uma ampla gama de aplicações práticas, variando de tarefas simples, como o lançamento de moedas, a tarefas mais complexas, como leilões eletrônicos (por exemplo, calcular o preço de equilíbrio do mercado), votação eletrônica ou mineração de dados que preserva a privacidade. Um exemplo clássico é o Problema dos Milionários: dois milionários querem saber quem é mais rico, de tal forma que nenhum deles aprenda o patrimônio líquido do outro. Uma solução para esta situação é, essencialmente, avaliar de forma segura a função de comparação.
Definições de segurança
Um protocolo de computação multi-partes deve ser seguro para ser eficaz. Na criptografia moderna, a segurança de um protocolo está relacionada a uma prova de segurança. A prova de segurança é uma prova matemática onde a segurança de um protocolo é reduzida à segurança de suas primitivas subjacentes. No entanto, nem sempre é possível formalizar a verificação de segurança do protocolo criptográfico baseando-se apenas no conhecimento da parte e na correção do protocolo. Para protocolos MPC, o ambiente no qual o protocolo opera é associado ao Paradigma Mundo Real/Mundo Ideal.Michael Backes, Birgit Pfitzmann, and Michael Waidner. "A general composition theorem for secure reactive systems." In Theory of Cryptography Conference, pp. 336-354. Springer, Berlin, Heidelberg, 2004. Não se pode dizer que as partes não aprendem nada, pois elas precisam aprender a saída da operação, e a saída depende das entradas. Além disso, a correção da saída não é garantida de forma absoluta, pois a correção da saída depende das entradas das partes, e as entradas devem ser assumidas como corretas.