Secret sharing with additive access structures from correlated random variables

Resumo Técnico: Compartilhamento de Segredos com Estruturas de Acesso Aditivas a partir de Variáveis Aleatórias Correlacionadas

Enunciado do Problema
O artigo aborda o problema do compartilhamento de segredos em um ambiente dinâmico onde o conjunto de participantes autorizados (a estrutura de acesso) evolui ao longo do tempo. Os modelos tradicionais de compartilhamento de segredos tipicamente assumem uma estrutura de acesso fixa; se a estrutura muda, as partes devem ser redistribuídas, o que gera ineficiência. Embora o modelo de "Estrutura de Acesso Evolutiva" (EAS) permita um crescimento monotônico, ele assume que os participantes ingressam sequencialmente e recebem as partes via canais privados.

Este trabalho introduz o modelo de Estrutura de Acesso Aditiva (AAS), que difere do EAS em duas maneiras fundamentais:

1. Inicialização Simultânea: Todos os participantes estão presentes inicialmente.
2. Fonte de Aleatoriedade Correlacionada: As partes são geradas simultaneamente a partir de uma fonte de aleatoriedade correlacionada (por exemplo, medições de ganho de canal em redes sem fio) em vez de serem distribuídas por canais privados.
3. Comunicação Pública: O distribuidor comunica-se com os participantes através de um canal público, sem ruído e autenticado. O distribuidor toma conhecimento das mudanças na estrutura de acesso (novos grupos autorizados) apenas no momento em que elas ocorrem e deve adaptar a estratégia de compartilhamento de segredos iterativamente.

O objetivo é determinar uma estratégia de compartilhamento de segredos que permita que grupos autorizados recuperem um segredo com alta confiabilidade, garantindo ao mesmo tempo que grupos não autorizados obtenham informações desprezíveis, tudo isso enquanto maximiza a taxa de segredo (o tamanho do segredo compartilhado normalizado pelo número de observações da fonte).

Metodologia
Os autores propõem uma estratégia de compartilhamento de segredos baseada em binagem aleatória (random binning) adaptada para um cenário dinâmico. O núcleo da metodologia envolve:

• Binagem Quantizada: O distribuidor observa uma sequência $Y^n$ de uma fonte correlacionada $(Y, X_L)$. Para cada passo de tempo $t$, o distribuidor e os participantes utilizam funções de binagem pré-determinadas ($g_i$ e $h_j$) que mapeiam sequências da fonte para índices.
• Codificação Iterativa: Em cada passo de tempo $t$, o distribuidor determina o número de índices de binagem ($k_t$) a incluir na mensagem pública e o número de índices ($\sigma_t$) a designar como o segredo. Essas contagens são escolhidas com base no conjunto autorizado atual $A_t$ e no conjunto não autorizado $U_t$.
• Especificação de Estratégia A Priori: Um aspecto inovador da prova é a introdução de um número quantizado de binagens. Isso permite a construção de uma única estratégia de compartilhamento de segredos que é totalmente especificada a priori. Crucialmente, esta estratégia não depende do conhecimento de como a AAS evoluirá em passos de tempo futuros; o distribuidor só precisa conhecer a estrutura de acesso atual para determinar a mensagem e o segredo para aquele passo específico.
• Decodificação: Participantes autorizados utilizam suas observações locais ($X^n_A$), as mensagens públicas acumuladas e as funções de binagem para identificar a sequência única da fonte consistente com as restrições de tipicidade e os índices de binagem recebidos.

Contribuições Principais e Resultados
O artigo estabelece os seguintes resultados teóricos:

1. Alcançabilidade de Taxas de Estrutura Fixa: Os autores provam que existe uma estratégia para o modelo AAS onde a taxa de segredo alcançável em qualquer passo de tempo $t$ é independente das estruturas de acesso em todos os outros passos de tempo. Especificamente, a taxa alcançável $R_t$ corresponde à melhor taxa alcançável conhecida para um modelo de estrutura fixa:
   $$R_t = \min_{U \in U_t} H(Y | X_U) - \max_{A \in A_t} H(Y | X_A)$$
   Este resultado implica que a natureza dinâmica da estrutura de acesso não degrada inerentemente a taxa de segredo em comparação com um cenário estático.

2. Capacidade para Estruturas de Acesso de Limiar (Threshold): O artigo prova que, quando a estrutura de acesso em um determinado passo de tempo forma uma Estrutura de Acesso de Limiar (onde qualquer grupo de tamanho $\ge f_1(t)$ é autorizado e qualquer grupo de tamanho $\le f_2(t)$ é não autorizado), a estratégia proposta atinge a capacidade. Para um caso específico onde o distribuidor compartilha chaves privadas independentes com os participantes, a capacidade é mostrada como:
   $$R_t = H(X)(f_1(t) - f_2(t))$$

3. Onisciência vs. Causalidade: Uma descoberta significativa é que, para o caso de AAS de limiar, um distribuidor onisciente (que conhece toda a sequência futura de estruturas de acesso) não obtém vantagem sobre um distribuidor causal (que conhece apenas a estrutura atual) em termos de taxas de segredo alcançáveis.

Significância e Alegações
O artigo afirma generalizar os modelos de compartilhamento de segredos que dependem de aleatoriedade correlacionada de estruturas de acesso aditivas fixas para dinâmicas. A principal significância reside em demonstrar que a adaptabilidade dinâmica não ocorre às custas da eficiência da taxa de segredo. Os autores mostram que é possível alcançar os mesmos limites de desempenho das melhores estratégias estáticas sem exigir conhecimento prévio da evolução do sistema.

O trabalho destaca que o resultado "surpreendente" é a independência da taxa alcançável no tempo $t$ em relação ao histórico ou futuro da estrutura de acesso. Embora o artigo forneça uma prova de existência não construtiva para o caso geral de AAS (baseando-se no método probabilístico para mostrar a existência de funções de binagem adequadas), ele nota explicitamente que fornecer uma prova de alcançabilidade construtiva para o caso geral de AAS permanece um problema em aberto, distinguindo-o das provas construtivas existentes para estruturas fixas.

O artigo conclui que, para estruturas dinâmicas baseadas em limiar, a capacidade é totalmente caracterizada, e a falta de previsão quanto às mudanças futuras na estrutura de acesso não penaliza o desempenho do sistema.