Compartilhamento visual de segredos e esquemas aditivos

O compartilhamento visual de segredos (Naor e Shamir, 1994) divide uma imagem em n transparências, de modo que sobrepor k transparências revele a imagem secreta, enquanto qualquer quantidade menor não revele nada — nem mesmo para um adversário com poder computacional ilimitado.

Cada pixel do segredo é expandido para um bloco de 2x2. Para um pixel preto: as duas partes recebem padrões complementares (quando sobrepostas, tudo fica preto). Para um pixel branco: as duas partes recebem o mesmo padrão (quando sobrepostas, 50% preto = cinza). O olho percebe a diferença.

Para cadeias de bits: compartilhe o segredo S gerando R_1, R_2, ..., R_{n-1} aleatórios. Defina R_n = S XOR R_1 XOR ... XOR R_{n-1}. A aplicação de XOR a todas as n partes resulta em S. Qualquer subconjunto de n-1 partes é uniformemente aleatório — não revela nada sobre S.

O compartilhamento baseado em XOR ou aditivo é n de n (todas as partes são necessárias). O SSS de Shamir é k de n (quaisquer k partes). O compartilhamento aditivo é mais simples e rápido; Shamir lida com limiares arbitrários. Os protocolos MPC frequentemente usam compartilhamento aditivo para operações aritméticas.

Para segredos inteiros: compartilhe S como S = s_1 + s_2 + ... + s_n (módulo p). Cada s_i é um elemento aleatório de Z_p. Para somar dois valores compartilhados A+B, cada participante adiciona localmente suas partes: (a_i + b_i) módulo p. Nenhuma comunicação é necessária para a adição.

Multiplicar valores compartilhados em segredo exige interação. O método clássico da tripla de Beaver consiste em pré-calcular (a, b, c=ab) aleatórios e compartilhados. Para multiplicar x*y, revele (x-a) e (y-b) a todos os participantes (esses valores não revelam nada sobre x e y) e então calcule x*y usando a tripla.

Um Esquema Linear de Compartilhamento de Segredos (LSSS) implementa qualquer estrutura de acesso monótona. Shamir é um LSSS. Os LSSS são a base da criptografia baseada em atributos (ABE) e dos sistemas de controle de acesso com múltiplas autoridades.

O esquema Shamir agrupado compartilha vários segredos em um único polinômio: codifique k segredos como coeficientes de um polinômio de grau (n-k). Isso permite amortizar o custo de comunicação em protocolos MPC quando muitos valores precisam ser compartilhados simultaneamente.

Os esquemas básicos de compartilhamento não oferecem proteção contra participantes maliciosos que enviem partes inválidas. O Compartilhamento Verificável de Segredos (VSS) adiciona compromissos; o Compartilhamento Robusto de Segredos adiciona correção de erros, de modo que a reconstrução seja bem-sucedida mesmo com t partes inválidas.

Criptografia visual: autenticação de documentos impressos e cédulas eleitorais seguras. Compartilhamento aditivo: MPC SPDZ e agregação segura no aprendizado federado (Google). Esquemas de limiar: backup de sementes de carteiras de hardware e gerenciamento empresarial de chaves.

Um esquema de rampa (k,n) é mais fraco: menos de k-d partes revelam informações parciais (d níveis de sigilo). Ele é usado quando não é necessário o sigilo perfeito das partes parciais, mas a eficiência de armazenamento é essencial. Permite partes menores que as de Shamir.

A criptografia visual divide imagens em transparências; o compartilhamento aditivo usa XOR em esquemas de n de n; Shamir lida com esquemas de k de n. O MPC usa compartilhamento aditivo com triplas de Beaver para a multiplicação. A seguir: assinaturas de limiar e uso no mundo real.