Computação multipartidária segura

A computação segura de várias partes (também conhecida como computação segura, computação de várias partes (MPC) ou computação de preservação de privacidade) é um subcampo da criptografia com o objetivo de criar métodos para as partes computarem conjuntamente uma função sobre suas entradas, mantendo as 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 bisbilhoteiro do emissor e do receptor), a criptografia neste modelo protege a privacidade dos participantes uns dos outros.

A base para a computação multi partidária segura começou no final dos anos 1970 com o trabalho em pôquer mental, trabalho criptográfico que simula jogos/tarefas computacionais a distâncias sem a necessidade de terceiros de confiança. Observe que, tradicionalmente, a criptografia tratava de ocultar conteúdo, enquanto esse novo tipo de computação e protocolo trata de ocultar informações parciais sobre os dados enquanto calcula com os dados de várias fontes e produz resultados corretamente.

História

Os protocolos de propósito especial para tarefas específicas começaram no final dos anos 1970. Mais tarde, a computação segura foi formalmente introduzida como computação segura de duas partes (2PC) em 1982 (para o chamado problema dos milionários, um problema específico que é um predicado booleano) e, em geral (para qualquer cálculo viável), em 1986 por Andrew Yao. A área também é conhecida como avaliação de função segura (SFE). O caso de duas partes foi seguido por uma generalização ao multi partidário por Goldreich, Micali e Wigderson. O cálculo é baseado no compartilhamento secreto de todas as entradas e provas de conhecimento zero para um caso potencialmente malicioso, onde a maioria dos jogadores honestos no caso do adversário malicioso garantem que o mau comportamento seja detectado e o cálculo continue com a pessoa desonesta eliminada ou sua entrada revelada. Este trabalho sugeriu o esquema geral muito básico a ser seguido por essencialmente todos os protocolos multi partidários para computação segura futuros. Este trabalho apresentou uma abordagem, conhecida como paradigma GMW, para compilar um protocolo de computação multi partidária que é seguro contra adversários semi honestos para um protocolo que é seguro contra adversários maliciosos. Este trabalho foi seguido pelo primeiro protocolo seguro robusto que tolera comportamento defeituoso graciosamente sem revelar a saída de alguém por meio de um trabalho que inventou para esse fim, a frequentemente usada "ideia de compartilhamento de compartilhamentos", e um protocolo que permite que uma das partes esconda sua entrada incondicionalmente. O paradigma GMW foi, durante anos, considerado ineficiente devido às enormes sobrecargas que ele traz para o protocolo de base. Porém, mostra que é possível alcançar protocolos eficientes e isso torna esta linha de pesquisa ainda mais interessante do ponto de vista prático. Os resultados acima são em um modelo em que o adversário é limitado a cálculos de tempo polinomial e observa todas as comunicações e, portanto, o modelo é chamado de "modelo computacional". Além disso, o protocolo de transferência inconsciente se mostrou completo para essas tarefas. Os resultados acima estabeleceram que é possível, com as variações acima, obter um cálculo seguro quando a maioria dos usuários é honesta.

A próxima questão a resolver foi o caso dos canais de comunicação seguros em que a comunicação ponto a ponto não está disponível para o adversário. Neste caso, foi mostrado que as soluções podem ser alcançadas com até 1/3 das partes sendo de comportamento mal intencionado e malicioso, e as soluções não aplicam ferramentas criptográficas (já que a comunicação segura está disponível). Adicionar um canal de transmissão permite que o sistema tolere até 1/2 minoria malcomportada, enquanto as restrições de conectividade no grafo de comunicação foram investigadas no livro "Transmissão de mensagens perfeitamente segura".

Com o passar dos anos, a noção de protocolos multi partidários de propósito geral se tornou uma área fértil para investigar propriedades de problemas básicos e gerais de protocolo, como composibilidade universal ou adversário móvel como no compartilhamento de segredo pró ativo.

Desde o final dos anos 2000, e certamente desde 2010 em diante, o domínio dos protocolos de propósito geral mudou para lidar com melhorias de eficiência dos protocolos com aplicações práticas em mente. Protocolos cada vez mais eficientes para a MPC foram propostos, e a MPC pode agora ser considerada como uma solução prática para vários problemas da vida real (especialmente aqueles que requerem apenas o compartilhamento linear dos segredos e principalmente operações locais nas ações sem muitas interações entre as partes), como votação distribuída, licitações e leilões privados, compartilhamento de assinatura ou dfunções de decodificação e recuperação de informações privadas. A primeira aplicação prática e em grande escala de computação multi partidária (demonstrada em um problema real de leilão) ocorreu na Dinamarca em janeiro de 2008. Obviamente, tanto noções teóricas quanto investigações e construções aplicadas são necessárias (por exemplo, as condições para mover a MPC para parte do dia a dia dos negócios foram defendidas e apresentadas em ).

Definição e visão geral

Em uma MPC, um determinado número de participantes, p₁, p₂, ..., p_N, cada um possui dados privados, respectivamente d₁, d₂, ..., d_N. Os participantes desejam calcular o valor de uma função pública nesses dados privados: F (d1, d2, ..., dN), mantendo suas próprias entradas em segredo.

Por exemplo, suponha que temos três partes, Alice, Bob e Charlie, com as respectivas entradas x, y e z denotando seus salários. Eles querem saber o maior dos três salários, sem revelar um ao outro quanto cada um ganha. Matematicamente, isso se traduz para eles computando:

F(x, y, z) = max(x, y, z)

Se houvesse alguém de confiança de fora (digamos, eles tinham um amigo em comum, Tony, que sabiam que podia guardar um segredo), cada um poderia contar seu salário a esse alguém, ele poderia calcular o máximo e dizer esse número a todos. O objetivo da MPC é projetar um protocolo, onde, trocando mensagens apenas entre si, Alice, Bob e Charlie ainda possam aprender F(x, y, z) sem revelar quem faz o quê e sem ter que contar com alguém de confiança de fora (Tony). Eles não deveriam aprender mais, ao se engajar em seu protocolo, do que aprenderiam ao interagir com um Tony incorruptível e perfeitamente confiável.

Em particular, tudo o que as partes podem aprender é o que podem aprender com os resultados e com seus próprios dados. Portanto, no exemplo acima, se a saída for z, então Charlie aprende que seu z é o valor máximo, enquanto Alice e Bob aprendem (se x, y e z são distintos) que sua entrada não é igual ao máximo e que o máximo mantido é igual a z. O cenário básico pode ser facilmente generalizado para onde as partes têm várias entradas e saídas e a função produz diferentes valores para diferentes partes.

Falando informalmente, as propriedades mais básicas que um protocolo de computação multi partidária visa garantir são:

• Privacidade de entrada: Nenhuma informação sobre os dados privados mantidos pelas partes pode ser inferida das mensagens enviadas durante a execução do protocolo. A única informação que pode ser inferida sobre os dados privados é tudo o que pode ser inferido ao ver apenas a saída da função.
• Correção: Qualquer subconjunto apropriado de partes de adversários coniventes dispostos a compartilhar informações ou se desviar 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. Essa meta de correção vem em dois modos: ou as partes honestas têm a garantia de calcular a saída correta (um protocolo "robusto") ou abortam se encontrarem um erro (um protocolo MPC "com abortar").

Há uma ampla gama de aplicações práticas, variando de tarefas simples como lançamento de moeda (cara ou coroa), até outras mais complexas como leilões eletrônicos (calcular o preço de compensação de mercado, por exemplo), votação eletrônica ou mineração de dados com preservação de privacidade. Um exemplo clássico é o "problema dos milionários": dois milionários querem saber quem é mais rico, de forma que nenhum deles saiba o patrimônio líquido do outro. Uma solução para esta situação é essencialmente avaliar com segurança a função de comparação.

Definições de segurança

Um protocolo de computação de várias 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 em que a segurança de um protocolo é reduzida à segurança de suas primitivas subjacentes. No entanto, nem sempre é possível formalizar a verificação da segurança do protocolo criptográfico com base no conhecimento da parte e na correção do protocolo. Para protocolos MPC, o ambiente no qual o protocolo opera está associado ao paradigma mundo real/mundo ideal. Não se pode dizer que as partes não aprendem nada, uma vez que precisam aprender a saída da operação, e a saída depende das entradas. Além disso, a exatidão da saída não é garantida, uma vez que a exatidão da saída depende das entradas das partes, e as entradas devem ser assumidas como corrompidas.

O paradigma mundo real/mundo ideal afirma dois mundos: (i) No modelo de mundo ideal, existe uma parte confiável incorruptível para a qual cada participante do protocolo envia sua entrada. Essa parte confiável calcula a função por conta própria e envia de volta a saída apropriada para cada parte. (ii) Em contraste, no modelo do mundo real, não existe uma parte confiável e tudo que as partes podem fazer é trocar mensagens entre si. Um protocolo é considerado seguro se não se pode aprender mais sobre as entradas privadas de cada parte no mundo real do que se poderia aprender no mundo ideal. No mundo ideal, nenhuma mensagem é trocada entre as partes, portanto, as mensagens trocadas no mundo real não podem revelar nenhuma informação secreta.

O paradigma mundo real/mundo ideal fornece uma abstração simples das complexidades da MPC para permitir a construção de um aplicativo sob o pretexto de que o protocolo MPC em seu núcleo é na verdade uma execução ideal. Se o aplicativo for seguro no caso ideal, ele também será seguro quando um protocolo real for executado.

Os requisitos de segurança em um protocolo MPC são rigorosos. No entanto, em 1987 foi demonstrado que qualquer função pode ser computada com segurança, com segurança para adversários maliciosos e os demais trabalhos iniciais mencionados anteriormente. Apesar dessas publicações, a MPC não foi projetada para ser eficiente o suficiente para ser usada na prática naquela época. A MPC incondicionalmente (ou de informações teoricamente) segura está intimamente relacionada e se baseia no problema de compartilhamento de segredo (mais especificamente, de compartilhamento de segredo verificável (VSS)) que muitos protocolos de MPC seguros usam contra adversários ativos.

Ao contrário das aplicações criptográficas tradicionais, como criptografia ou assinatura, deve se supor que o adversário em um protocolo MPC é um dos participantes do sistema (ou partes internas do controle). Essa parte corrompida pode conspirar para violar a segurança do protocolo. Seja $n$ o número de partes no protocolo e $t$ o número de partes que podem ser adversárias. Os protocolos e as soluções para o caso de $t<n/2$ (ou seja, quando uma maioria honesta é assumida) são diferentes dos casos em que essa suposição não é feita. Este último caso inclui o caso importante de computação de duas partes em que um dos participantes pode ser corrompido e o caso geral em que um número ilimitado de participantes é corrompido e conspira para atacar os participantes honestos.

Os adversários enfrentados pelos diferentes protocolos podem ser categorizados de acordo com o quanto estão dispostos a se desviar do protocolo. Existem essencialmente dois tipos de adversários, cada um dando origem a diferentes formas de segurança (e cada um se encaixa em diferentes cenários do mundo real):

• Segurança semi honesta (passiva): Neste caso, presume se que as partes corrompidas simplesmente cooperam para coletar informações fora do protocolo, mas não se desviam da especificação do protocolo. Este é um modelo de adversário ingênuo, gerando uma segurança fraca em situações reais. No entanto, os protocolos que alcançam esse nível de segurança evitam o vazamento inadvertido de informações entre as partes (de outra forma colaboradoras) e, portanto, são úteis se essa for a única preocupação. Além disso, os protocolos no modelo semi honesto são bastante eficientes e costumam ser um primeiro passo importante para alcançar níveis mais altos de segurança.
• Segurança maliciosa (ativa): Neste caso, o adversário pode desviar arbitrariamente da execução do protocolo em sua tentativa de trapacear. Os protocolos que alcançam a segurança neste modelo fornecem uma garantia de segurança muito alta. No caso da maioria das partes mal comportadas: A única coisa que um adversário pode fazer no caso da maioria desonesta é fazer com que as partes honestas “abortem” ao detectar a trapaça. Se as partes honestas obtiverem resultados, então terão a garantia de que estão corretos. A privacidade delas é sempre preservada.

A segurança contra adversários ativos normalmente leva à uma redução na eficiência que leva à segurança encoberta, uma forma relaxada de segurança ativa. A segurança encoberta captura situações mais realistas, em que adversários ativos estão dispostos a trapacear, mas apenas se não forem pegos. Por exemplo, sua reputação pode ser prejudicada, impedindo a colaboração futura com outras partes honestas. Assim, os protocolos que são veladamente seguros fornecem mecanismos para garantir que, se alguma das partes não seguir as instruções, isso será notado com alta probabilidade, digamos 75% ou 90%. De certa forma, adversários encobertos são ativos forçados a agir passivamente devido a preocupações não criptográficas externas (negócios, por exemplo). Este mecanismo estabelece uma ponte entre os dois modelos na esperança de encontrar protocolos que sejam eficientes e seguros o suficiente na prática.

Como muitos protocolos criptográficos, a segurança de um protocolo MPC pode se basear em diferentes suposições:

• Pode ser computacional (ou seja, com base em algum problema matemático, como fatoração) ou incondicional, ou seja, depender da indisponibilidade física de mensagens em canais (geralmente com alguma probabilidade de erro que pode ser arbitrariamente pequena).
• O modelo pode assumir que os participantes usam uma rede sincronizada, onde uma mensagem enviada em um "tick" sempre chega no próximo "tick", ou que existe um canal de transmissão seguro e confiável, ou que existe um canal de comunicação seguro entre cada par de participantes onde um adversário não pode ler, modificar ou gerar mensagens no canal, etc.

O conjunto de partes honestas que podem executar uma tarefa computacional está relacionado ao conceito de estrutura de acesso. As estruturas adversárias podem ser estáticas, onde o adversário escolhe suas vítimas antes do início da computação multi partidária, ou dinâmicas, onde (dificultando a defesa) ele escolhe suas vítimas durante o curso da execução da computação multi partidária. Uma estrutura adversária pode ser definida como uma estrutura de limite ou como uma estrutura mais complexa. Em uma estrutura de limite, o adversário pode corromper ou ler a memória de vários participantes até certo limite. Enquanto isso, em uma estrutura complexa, pode afetar certos subconjuntos predefinidos de participantes, modelando diferentes conluios possíveis.

Protocolos

Existem grandes diferenças entre os protocolos propostos para computação de duas partes (2PC) e computação de várias partes (MPC). Além disso, muitas vezes para protocolos de finalidade especial de importância, um protocolo especializado que se desvia dos genéricos deve ser projetado (votação, leilões, pagamentos, etc.)

Computação de duas partes

A configuração de duas partes é particularmente interessante, não apenas do ponto de vista dos aplicativos, mas também porque técnicas especiais podem ser aplicadas na configuração de duas partes que não se aplicam ao caso de várias partes. Na verdade, a computação multi partidária segura (na verdade, o caso restrito de avaliação de função segura, em que apenas uma única função é avaliada) foi apresentada pela primeira vez na configuração de duas partes. O trabalho original é frequentemente citado como sendo de um dos dois artigos de Yao; embora os documentos não contenham realmente o que agora é conhecido como protocolo de circuito truncado de Yao.

O protocolo básico de Yao é seguro contra adversários semi honestos e é extremamente eficiente em termos de número de rodadas, que é constante e independente da função alvo que está sendo avaliada. A função é vista como um circuito booleano, com entradas em binário de comprimento fixo. Um circuito booleano é uma coleção de portas conectadas com três tipos diferentes de fios: fios de entrada de circuito, fios de saída de circuito e fios intermediários. Cada porta recebe dois fios de entrada e tem um único fio de saída que pode ser espalhado (ou seja, ser passado para várias portas no próximo nível). A avaliação simples do circuito é feita avaliando cada porta por vez; assumindo que as portas foram topologicamente ordenadas. A porta é representada como uma tabela verdade de forma que para cada par possível de bits (aqueles vindos da porta dos fios de entrada) a tabela atribui um bit de saída exclusivo; que é o valor do fio de saída da porta. Os resultados da avaliação são os bits obtidos nos fios de saída do circuito.

Yao explicou como distorcer um circuito (ocultar sua estrutura) para que duas partes, emissor e receptor, possam aprender a saída do circuito e nada mais. Em um nível alto, o transmissor prepara o circuito truncado e o envia ao receptor, que avalia o circuito inconscientemente, aprendendo as codificações correspondentes tanto à sua saída quanto à do transmissor. Ele então apenas envia de volta as codificações do remetente, permitindo que o remetente calcule sua parte da saída. O remetente envia o mapeamento das codificações de saída do receptor em bits para o receptor, permitindo que o receptor obtenha sua saída.

Em mais detalhes, o circuito truncado é calculado da seguinte maneira. O ingrediente principal é um esquema de criptografia simétrica de chave dupla. Dada uma porta do circuito, cada valor possível de seus fios de entrada (0 ou 1) é codificado com um número aleatório (rótulo). Os valores resultantes da avaliação da porta em cada um dos quatro pares possíveis de bits de entrada também são substituídos por rótulos aleatórios. A tabela verdade ilegível da porta consiste em criptografias de cada rótulo de saída usando seus rótulos de entrada como chaves. A posição dessas quatro criptografias na tabela verdade é aleatória, de modo que nenhuma informação sobre a porta vaza.

Para avaliar corretamente cada porta truncada, o esquema de criptografia tem as duas propriedades a seguir. Em primeiro lugar, os intervalos da função de criptografia em quaisquer duas chaves distintas são separados (com probabilidade esmagadora). A segunda propriedade diz que pode ser verificado de forma eficiente se um determinado texto cifrado foi criptografado sob uma determinada chave. Com essas duas propriedades, o receptor, depois de obter os rótulos de todos os fios de entrada do circuito, pode avaliar cada porta descobrindo primeiro qual dos quatro textos criptografados foi criptografado com suas chaves de rótulo e, em seguida, o descifrar para obter o rótulo do fio de saída . Isso é feito inconscientemente, pois tudo o que o receptor aprende durante a avaliação são codificações dos bits.

Os bits de entrada do remetente (ou seja, os criadores do circuito) podem ser enviados apenas como codificações para o avaliador; ao passo que as codificações do receptor (isto é, avaliadores de circuito) correspondentes aos seus bits de entrada são obtidas por meio de um protocolo de transferência inconsciente (OT) 1 de 2. Um protocolo OT 1 de 2, permite ao remetente, em posse de dois valores C1 e C2, enviar aquele solicitado pelo destinatário (valor b a em {1,2}) de tal forma que o remetente não sabe qual valor foi transferido e o receptor só aprende o valor consultado.

Se alguém está considerando adversários maliciosos, outros mecanismos para garantir o comportamento correto de ambas as partes precisam ser fornecidos. Por construção, é fácil mostrar segurança para o remetente se o protocolo OT já estiver seguro contra adversários maliciosos, pois tudo o que o receptor pode fazer é avaliar um circuito truncado que não alcançaria os fios de saída do circuito se ele se desviasse das instruções . A situação é muito diferente do lado do remetente. Por exemplo, ele pode enviar um circuito ilegível incorreto que calcula uma função revelando a entrada do receptor. Isso significaria que a privacidade não seria mais válida, mas como o circuito está truncado, o receptor não seria capaz de detectar isso. No entanto, é possível aplicar provas de conhecimento zero de forma eficiente para tornar este protocolo seguro contra adversários maliciosos com uma pequena sobrecarga em comparação com o protocolo semi honesto.

Protocolos multi partidários

A maioria dos protocolos MPC, ao contrário dos protocolos 2PC e especialmente sob a configuração incondicional de canais privados, faz uso do compartilhamento d secredo. Nos métodos baseados em compartilhamento de secredo, as partes não desempenham papéis especiais (como em Yao, de criador e avaliador). Em vez disso, os dados associados a cada fio são compartilhados entre as partes e um protocolo é então usado para avaliar cada porta. A função agora é definida como um “circuito” sobre um campo finito, em oposição aos circuitos binários usados por Yao. Tal circuito é denominado circuito aritmético na literatura e consiste em “portas” de adição e multiplicação onde os valores operados são definidos sobre um corpo finito.

O compartilhamento de secredo permite distribuir um segredo entre várias partes, distribuindo ações para cada parte. Dois tipos de esquemas de compartilhamento de segredos são comumente usados: O compartilhamento de segredos de Shamir e o compartilhamento de segredos aditivo. Em ambos os casos, as ações são elementos aleatórios de um campo finito que se somam ao segredo do campo; intuitivamente, a segurança é obtida porque qualquer conjunto não qualificado de compartilhamentos parece distribuído aleatoriamente.

Os esquemas de compartilhamento de segredos podem tolerar um adversário controlando até t partes de um total de n partes, onde t varia com base no esquema, o adversário pode ser passivo ou ativo e diferentes suposições são feitas sobre o poder do adversário. O esquema de compartilhamento de segredo de Shamir é seguro contra um adversário passivo quando $t<{\frac {n}{2}}$ e um adversário ativo quando $t<{\frac {n}{3}}$ ao alcançar a segurança teórica da informação, o que significa que mesmo que o adversário tenha poder computacional ilimitado, eles não pode obter nenhuma informação sobre o segredo subjacente a um compartilhamento. O protocolo BGW, que define como computar adição e multiplicação em compartilhamentos de secredos, é frequentemente usado para computar funções com compartilhamentos de secredos de Shamir. Esquemas aditivos de compartilhamento de segredos podem tolerar que o adversário controle todas as partes, exceto uma, que é $t<n$, enquanto mantém a segurança contra um adversário passivo e ativo com poder computacional ilimitado. Alguns protocolos exigem uma fase de configuração, que só pode ser segura contra um adversário limitado computacionalmente.

Vários sistemas implementaram várias formas de MPC com esquemas de compartilhamento de segredos. O mais popular é o SPDZ, que implementa a MPC com compartilhamentos de segredos aditivos e é seguro contra adversários ativos.

Outros protocolos

Em 2014, um "modelo de justiça na computação segura no qual uma parte adversária que aborta ao receber a saída é forçada a pagar uma penalidade monetária mutuamente predefinida" foi descrito para a rede Bitcoin ou para loteria justa.

Sistemas práticos de MPC

Muitos avanços foram feitos nos sistemas 2PC e MPC nos últimos anos.

Protocolos baseados em Yao

Um dos principais problemas ao trabalhar com protocolos baseados em Yao é que a função a ser avaliada com segurança (que poderia ser um programa arbitrário) deve ser representada como um circuito, geralmente consistindo em portas XOR e AND. Como a maioria dos programas do mundo real contém loops e estruturas de dados complexas, essa é uma tarefa altamente não trivial. O sistema Fairplay foi a primeira ferramenta projetada para resolver este problema. O Fairplay compreende dois componentes principais: O primeiro deles é um compilador que permite aos usuários escrever programas em uma linguagem simples de alto nível e produzir esses programas em uma representação de circuito booleano. O segundo componente pode, então, truncar o circuito e executar um protocolo para avaliar com segurança o circuito truncado. Assim como a computação de duas partes com base no protocolo de Yao, o Fairplay também pode realizar protocolos multi partidários. Isso é feito usando o protocolo BMR, que estende o protocolo passivamente seguro de Yao para o caso ativo.

Nos anos que se seguiram à introdução do Fairplay, muitas melhorias no protocolo básico de Yao foram criadas, na forma de melhorias de eficiência e técnicas para segurança ativa. Isso inclui técnicas como o método XOR livre, que permite uma avaliação muito mais simples de portas XOR, e redução de linhas truncadas, reduzindo o tamanho de tabelas truncadas com duas entradas em 25%.

A abordagem que até agora parece ser a mais frutífera na obtenção de segurança ativa vem de uma combinação da técnica de truncagem e do paradigma “cortar e escolher”. Esta combinação parece tornar construções mais eficientes. Para evitar os problemas acima mencionados com relação ao comportamento desonesto, muitas truncagens do mesmo circuito são enviadas do construtor para o avaliador. Em seguida, cerca de metade deles (dependendo do protocolo específico) são abertos para verificar a consistência e, se assim for, a grande maioria dos que não foram abertos estão corretos com alta probabilidade. O resultado é a maioria dos votos de todas as avaliações. Observe que aqui a saída principal é necessária. Se houver desacordo nas saídas, o receptor sabe que o remetente está trapaceando, mas ele não pode reclamar, caso contrário, isso vazaria informações sobre sua entrada.

Esta abordagem para segurança ativa foi iniciada por Lindell e Pinkas. Essa técnica foi implementada por Pinkas et al. em 2009, isso forneceu a primeira avaliação de duas partes ativamente segura do circuito padrão de criptografia avançado (AES), considerado uma função não trivial altamente complexa (consistindo em cerca de 30.000 portas AND e XOR) (também com alguns aplicações potenciais), levando cerca de 20 minutos para computar e exigindo 160 circuitos para obter uma probabilidade de trapaça de $2^{-40}$.

Como muitos circuitos são avaliados, as partes (incluindo o receptor) precisam se comprometer com suas entradas para garantir que em todas as iterações os mesmos valores sejam usados. Os experimentos de Pinkas et al. relatados mostram que o gargalo do protocolo reside nas verificações de consistência. Eles tiveram que enviar pela rede cerca de 6.553.600 compromissos para vários valores para avaliar o circuito AES. Em resultados recentes, a eficiência de implementações baseadas em Yao ativamente seguras foi melhorada ainda mais, exigindo apenas 40 circuitos, e muito menos compromissos, para obter probabilidade de trapaça de $2^{-40}$. As melhorias vêm de novas metodologias para realizar o cortar e escolher nos circuitos transmitidos.

Mais recentemente, tem havido um foco em implementações altamente paralelas baseadas em circuitos ilegíveis, projetados para serem executados em CPUs com muitos núcleos. Kreuter, et al. descreve uma implementação em execução em 512 núcleos de um poderoso computador cluster. Usando esses recursos, eles puderam avaliar a função de edição de distância de 4095 bits, cujo circuito compreende quase 6 bilhões de portas. Para conseguir isso, eles desenvolveram um compilador de circuito personalizado e melhor otimizado do que o Fairplay e várias novas otimizações, como pipelining, em que a transmissão do circuito truncado pela rede começa enquanto o resto do circuito ainda está sendo gerado. O tempo para calcular AES foi reduzido para 1,4 segundos por bloco no caso ativo, usando uma máquina de cluster de 512 nós, e 115 segundos usando um nó. Shelat e Shen melhoram isso, usando hardware comum, para 0,52 segundos por bloco. O mesmo relatório informa sobre uma taxa de transferência de 21 blocos por segundo, mas com uma latência de 48 segundos por bloco.

Enquanto isso, outro grupo de pesquisadores investigou o uso de GPUs de consumo para atingir níveis semelhantes de paralelismo. Eles utilizam extensões OT e algumas outras técnicas inovadoras para projetar seu protocolo específico de GPU. Esta abordagem parece alcançar eficiência comparável à implementação de computação em cluster, usando um número semelhante de núcleos. No entanto, os autores relatam apenas a implantação do circuito AES, que possui cerca de 50.000 porta's. Por outro lado, o hardware necessário aqui é muito mais acessível, pois dispositivos semelhantes já podem ser encontrados em computadores de área de trabalho ou consoles de jogos de muitas pessoas. Os autores obtêm um tempo de 2,7 segundos por bloco AES em um desktop padrão, com uma GPU padrão. Se eles permitirem que a segurança diminua para algo semelhante à segurança encoberta, eles obtêm um tempo de execução de 0,30 segundos por bloco AES. No caso da segurança passiva, há relatos de processamento de circuitos com 250 milhões de portas, e à uma taxa de 75 milhões de portas por segundo.

Ver também

• Criptografia homomórfica

Ligações externas

• Uma descrição simples do problema do milionário (em inglês)
• Links de Helger Lipmaa sobre computação multi partidária (em inglês)
• Nick Szabo, "Os protocolos de Deus (em inglês)" no Wayback Machine (arquivado em 2006-12-30)
• Kit de ferramentas EMP — Kit de ferramentas de computação multi partidária eficiente. Inclui a implementação de primitivas MPC básicas, bem como protocolos com segurança semi honesta e segurança maliciosa. (em inglês)
• Solucionadores de CSP distribuídos seguros (DisCSP) — um aplicativo web com um miniaplicativo intérprete para projetar e executar sua própria computação multi partidária totalmente segura (com base na linguagem declarativa SMC). Usa avaliação de circuito aritmético seguro e redes de mixagem (em inglês).
• VMCrypt Uma biblioteca Java para computação segura escalonável. Por Lior Malka (em inglês).
• Projeto Fairplay — Inclui um pacote de software para computação segura de duas partes, onde a função é definida usando uma linguagem de descrição de função de alto nível e avaliada usando o protocolo de Yao para avaliação segura de circuitos booleanos (em inglês).
• Projeto SIMAP; O gerenciamento e processamento de informaçõessSeguras ('SIMP) é um projeto patrocinado pela Agência Nacional de Pesquisa Dinamarquesa que visa implementar a computação multi partidária segura (em inglês).
• Linguagem de computação multi partidária segura - projeto para desenvolvimento de uma "linguagem de programação específica de domínio para computação multipartidária segura" e tempo de execução criptográfico associado (em inglês).
• VIFF: Framework de funcionalidade ideal virtual — Framework para cálculos assíncronos de várias partes (código disponível sob a LGPL). Oferece aritmética com valores de secredos compartilhados, incluindo comparação segura (em inglês).
• MPyC: Computação multi partidária segura em Python (e notebooks Jupyter) — Pacote de código aberto para MPC usando um tipo personalizado de co rotinas Python, suportando aplicativos avançados como árvores de decisão ID3, programação linear, redes neurais CNN/MLP, AES, cadeias hash unidirecionais e muitos mais. Lançado em maio de 2018 (em inglês).
• SCALE-MAMBA MPC: Algoritmos de computação segura de LEuven — Framework para vários protocolos MPC, incluindo a família SPDZ (código disponível sob o BSD). Oferece aritmética com valores de segredos compartilhados, incluindo comparação segura e suporte para aritmética de ponto fixo e ponto flutuante (em inglês).
• Sharemind: analisa dados confidenciais sem comprometer a privacidade — Uma máquina virtual distribuída com a capacidade de executar operações de preservação de privacidade. Possui uma linguagem de programação que preserva a privacidade para ferramentas de mineração de dados. Inclui ferramentas de desenvolvedor (em inglês).
• MPCLib: Biblioteca de computação multi partidária — Uma biblioteca escrita em C# e C++ que implementa vários blocos de construção necessários para implementar protocolos de computação multi partidária segura. O MPCLib possui um mecanismo de simulação de eventos discretos que pode ser usado para simular protocolos MPC em redes virtuais (em inglês).
• Partes virtuais em SMC Um protocolo para partes virtuais em SMC (computação multi partidária segura) (em inglês)
• SEPIA Uma biblioteca java para SMC usando compartilhamento secreto. As operações básicas são otimizadas para um grande número de invocações paralelas (código disponível em LGPL).
• Introdução ao SMC no GitHub
• Projeto Myst - Applet JavaCard que implementa geração, assinatura e descriptografia de chave multi partidária segura.
• Bibliografia essencial Computação multi partidária segura