Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring

Título do Trabalho

Compartilhamento Hierárquico de Segredos Assintoticamente Ideal Baseado no Teorema Chinês do Resto para o Anel Inteiro

1. Problema e Contexto

O Compartilhamento de Segredos (SS) é um método fundamental em criptografia onde um segredo é dividido em "partes" (shares) distribuídas entre participantes. O esquema clássico de Shamir assume que todos os participantes têm privilégios iguais (esquema de limiar $(t, n)$). No entanto, em cenários práticos (como sistemas bancários, governamentais ou corporativos), é necessário atribuir diferentes níveis de autoridade a diferentes participantes.

Para resolver isso, foram desenvolvidos esquemas de Compartilhamento Hierárquico de Segredos (HSS), que dividem os participantes em subconjuntos disjuntos com níveis de privilégio distintos. Existem duas estruturas principais:

• Disjuntiva (DHSS): Um conjunto autorizado é formado se houver participantes suficientes em qualquer um dos níveis hierárquicos superiores.
• Conjuntiva (CHSS): Um conjunto autorizado deve satisfazer as condições de limiar em todos os níveis hierárquicos.

Limitações das Soluções Existentes:
A maioria dos esquemas HSS baseados no Teorema Chinês do Resto (CRT) enfrenta um dilema entre segurança e eficiência:

1. Esquemas ideais (taxa de informação $\rho = 1$) baseados em interpolação de Birkhoff ou polimatrizes exigem complexidade computacional exponencial ou verificação de matrizes complexas pelo distribuidor (dealer).
2. Esquemas baseados em CRT que oferecem tamanhos de parte flexíveis e complexidade polinomial frequentemente apresentam falhas de segurança (como os de Harn et al. e Tiplea et al.) ou possuem taxas de informação inferiores a $1/2$ (como os de Ersoy et al.).
3. Esquemas anteriores baseados em CRT que atingiam taxas próximas a 1 foram posteriormente provados inseguros.

O objetivo deste trabalho é preencher essa lacuna: criar esquemas HSS (tanto disjuntivos quanto conjuntivos) que sejam seguros, assintoticamente ideais (taxa de informação $\rho \to 1$) e computacionalmente eficientes, permitindo tamanhos de parte flexíveis.

2. Metodologia

Os autores propõem dois novos esquemas (um para DHSS e outro para CHSS) baseados na combinação de três pilares:

1. Teorema Chinês do Resto (CRT) para Anel Inteiro: Utilizado para a reconstrução do segredo e para permitir que diferentes participantes recebam partes de tamanhos diferentes (baseados em inteiros coprimos).
2. Funções de Uma Via (One-Way Functions): Utilizadas para garantir a segurança e evitar que subconjuntos não autorizados deduzam informações sobre o segredo, superando as falhas de esquemas CRT puros anteriores.
3. Sequências $k$-Compactas de Coprimos: Uma estrutura matemática específica de inteiros coprimos ($m_0, m_1, \dots, m_n$) onde $m_0$ é um primo grande e os demais $m_i$ estão estritamente limitados em um intervalo próximo a $k \cdot m_0$. Essa propriedade é crucial para garantir que a entropia condicional do segredo dado um conjunto não autorizado tenda a zero assintoticamente.

Estrutura dos Esquemas:

• Geração de Partes: O distribuidor gera uma sequência pública de coprimos. Para o esquema conjuntivo, o segredo é dividido em somas modulares ($s = \sum \delta_i \mod m_0$). Para o disjuntivo, o segredo é codificado diretamente. O distribuidor calcula valores intermediários $y_\ell$ e utiliza funções de uma via $h_\ell$ para gerar valores públicos $w^{(\ell)}_i$ que auxiliam na reconstrução sem revelar o segredo.
• Reconstrução: Participantes autorizados utilizam suas partes, as funções de uma via e os valores públicos para recuperar os valores intermediários $y_\ell$ via CRT. Em seguida, recuperam o segredo original $s$.

3. Principais Contribuições

Os autores apresentam duas construções principais:

1. Esquema DHSS Assintoticamente Ideal:
   • Suporta tamanhos de parte flexíveis (diferentes para cada participante).
   • É seguro e assintoticamente perfeito.
   • Atinge uma taxa de informação que tende a 1 à medida que o tamanho do segredo aumenta.
   • Corrige as falhas de segurança de esquemas CRT anteriores (Harn, Ersoy, Tiplea, Yang).
2. Esquema CHSS Assintoticamente Ideal:
   • Similar ao DHSS, mas adaptado para a estrutura de acesso conjuntiva.
   • Oferece segurança e eficiência superior aos esquemas de Tiplea et al. e Ersoy et al.
   • Supera as limitações de complexidade dos esquemas ideais de Tassa e Chen.

Comparação com o Estado da Arte (Tabelas 1 e 2 do artigo):

• Esquemas anteriores ideais (Tassa, Chen) não suportam tamanhos de parte flexíveis.
• Esquemas anteriores com tamanhos flexíveis (Harn, Ersoy, Tiplea) eram inseguros ou tinham baixa taxa de informação ($\rho < 1/2$).
• O esquema proposto é o único que combina: Segurança + Tamanhos Flexíveis + Taxa de Informação Assintoticamente 1.

4. Resultados e Análise de Segurança

• Correção: Foi provado matematicamente que qualquer conjunto autorizado (satisfazendo os limiares hierárquicos) pode reconstruir o segredo corretamente usando o CRT.
• Segurança (Perfeição Assintótica):
  • O artigo demonstra que, para qualquer conjunto não autorizado $B$, a entropia condicional $H(S|V_B)$ (informação sobre o segredo dada as partes de $B$) tende a $H(S)$ (entropia total do segredo) à medida que o primo $m_0$ tende ao infinito.
  • Isso significa que a informação vazada por um ataque é desprezível para segredos suficientemente grandes.
  • A prova utiliza a propriedade das sequências $k$-compactas para mostrar que o número de candidatos possíveis para o segredo tende a uma constante fixa, tornando a probabilidade de adivinhar o segredo correta tendendo a zero.
• Taxa de Informação:
  • A taxa de informação $\rho$ é definida como $\frac{\log_2 |S|}{\max \log_2 |S_i|}$.
  • Devido à propriedade das sequências $k$-compactas ($m_i \approx k \cdot m_0$), a razão entre o tamanho do segredo e o tamanho da maior parte tende a 1 quando $m_0 \to \infty$. Portanto, o esquema é assintoticamente ideal.

5. Significado e Impacto

Este trabalho representa um avanço significativo na teoria de compartilhamento de segredos hierárquicos:

• Resolução de um Problema Aberto: Oferece a primeira construção CRT-based que é simultaneamente segura, flexível em tamanho de partes e assintoticamente ideal, resolvendo o trade-off entre segurança e eficiência que persistia na literatura.
• Aplicabilidade Prática: A flexibilidade no tamanho das partes permite otimizar o armazenamento e a transmissão em redes heterogêneas, enquanto a segurança assintótica garante robustez contra ataques computacionais modernos.
• Eficiência Computacional: Ao evitar a complexidade exponencial de esquemas baseados em polimatrizes e a verificação de matrizes complexas, os novos esquemas são viáveis para implementações em larga escala.

Em resumo, Ding et al. propõem uma solução robusta que une a flexibilidade do CRT com a segurança das funções de uma via e a eficiência matemática das sequências compactas, estabelecendo um novo padrão para esquemas de compartilhamento de segredos hierárquicos.