Ciphertext-Policy ABE for $\mathsf{NC}^1$ Circuits with Constant-Size Ciphertexts from Succinct LWE

Resumo Técnico: CP-ABE para Circuitos NC1 com Cifras de Tamanho Constante a partir de LWE Sucinto

1. O Problema

A Criptografia Baseada em Atributos (ABE) permite um controle de acesso granular a dados criptografados. Existem dois tipos principais:

• KP-ABE (Key-Policy): A política está na chave, o atributo no texto cifrado.
• CP-ABE (Ciphertext-Policy): A política está no texto cifrado, o atributo na chave.

O foco deste trabalho é o CP-ABE para políticas representadas por circuitos na classe NC1 (circuitos booleanos de profundidade logarítmica e tamanho polinomial).
O desafio central na área é a eficiência. Muitas construções anteriores de CP-ABE baseadas em LWE (Learning With Errors) resultam em:

1. Tamanho do texto cifrado dependente do tamanho do circuito: O tamanho do ciphertext cresce com o número de portas ou a profundidade do circuito de acesso, tornando-o impraticável para políticas complexas.
2. Dependência de suposições não padrão: Muitas soluções otimizadas dependem de suposições de LWE "evasivas" ou de grupos bilineares (que são vulneráveis a ataques quânticos).
3. Parâmetros de segurança: A necessidade de reduzir o tamanho do texto cifrado para constante (independente do tamanho da política) sem comprometer a segurança no modelo padrão.

2. Metodologia e Construção

Os autores propõem um esquema de CP-ABE baseado em reticulados (lattices) que atinge tamanho de texto cifrado constante ($O(1)$) para políticas NC1, sob a suposição de LWE Sucinto ($\ell$-succinct LWE), introduzida por Wee (CRYPTO 2024).

Componentes Chave da Metodologia:

• Suposição de Segurança: O esquema baseia-se na suposição $\ell$-succinct LWE. Esta é uma suposição mais forte que o LWE padrão, mas ainda considerada resistente a ataques quânticos, onde a relação entre o módulo e o ruído é sub-exponencial.
• Técnica de Comprometimento de Matriz (Matrix Commitment):
  • Inspirados no trabalho de Wee [Wee25] e Datta et al. [DKW21], os autores utilizam um esquema de comprometimento de matriz para comprimir a informação das políticas.
  • Em vez de incluir componentes de ciphertext para cada linha da matriz de acesso (o que tornaria o tamanho dependente de $\ell$, o número de atributos), eles comprometem uma matriz que representa todas as possíveis combinações de atributos.
  • O texto cifrado consiste apenas em três componentes: $c_1, c_2, c_3$, onde $c_2$ é uma combinação linear envolvendo uma matriz de comprometimento $C$.
• Geração de Chaves e Trapdoors:
  • A chave secreta é gerada usando um trapdoor para a matriz $B$ (parte da instância LWE sucinta).
  • Para responder a consultas de chaves secretas sem vazar informações sobre o LWE subjacente, os autores utilizam uma técnica inovadora: eles constroem trapdoors para matrizes da forma $[I_{\ell'} \otimes B \mid W']$ a partir do trapdoor original $T$ presente nos parâmetros públicos. Isso permite gerar chaves para conjuntos de atributos não autorizados sem usar o trapdoor mestre $td_B$, preservando a indistinguibilidade nas provas de segurança.
• Compressão de Parâmetros Públicos:
  • Embora os parâmetros públicos inicialmente pareçam depender do tamanho do circuito ($s$), os autores observam que a maior parte é uniformemente distribuída. Eles propõem o uso de um Gerador de Números Pseudoaleatórios (PRG) para comprimir a parte uniforme, reduzindo o tamanho efetivo dos parâmetros públicos para $O(1)$ (dependendo apenas do parâmetro de segurança $\lambda$).

3. Principais Contribuições

1. CP-ABE com Ciphertext de Tamanho Constante:

   • O esquema suporta políticas de acesso representadas por circuitos NC1.
   • Tamanho do Ciphertext: $O(1)$ (independente da profundidade $d$, do tamanho $s$ e do comprimento de entrada $\ell$ do circuito).
   • Tamanho da Chave Pública: $O(1)$ (após compressão via PRG).
   • Tamanho da Chave Secreta: $O(\ell)$, onde $\ell$ é o número de atributos associados à chave (pode ser reduzido para $O(1)$ se o usuário tiver um número constante de atributos).

2. Segurança no Modelo Padrão:

   • A segurança é provada de forma seletiva (selectively secure) no modelo padrão, baseada na suposição de LWE Sucinto (poly($\lambda$)-succinct LWE), sem depender de oráculos aleatórios ou suposições de grupos bilineares.

3. Aplicação em Criptografia de Difusão (Broadcast Encryption):

   • Como caso especial, o esquema fornece um sistema de Broadcast Encryption para $N$ usuários.
   • Parâmetros:
     • Tamanho do Ciphertext: $\text{poly}(\lambda)$ (independente de $\log N$).
     • Tamanho da Chave Secreta: $\text{poly}(\lambda, \log N)$.
     • Tamanho da Chave Pública: $\text{poly}(\lambda)$ (após compressão).
   • Isso representa um esquema de difusão ótimo em termos de tamanho do ciphertext, superando soluções anteriores que tinham dependência logarítmica no tamanho do ciphertext.

4. Resultados e Análise de Parâmetros

• Complexidade Assintótica:

  • $|pk| = O(1)$ (com compressão).
  • $|sk| = O(\ell)$ (ou $O(1)$ para usuários com poucos atributos).
  • $|ct| = O(1)$.
  • Onde $O(\cdot)$ esconde fatores polinomiais em $\lambda$.

• Comparação com Trabalhos Anteriores:

  • Comparado a [Wee25], este trabalho suporta uma classe mais restrita de políticas (NC1 vs. todos os circuitos), mas oferece ciphertexts de tamanho constante e chaves públicas de tamanho constante (independentes da profundidade do circuito), enquanto [Wee25] tem ciphertexts dependentes do comprimento do atributo.
  • Melhora os parâmetros de [DKW21] ao eliminar a dependência linear do tamanho do ciphertext em relação ao número de linhas da matriz de acesso.

• Prova de Segurança:

  • A prova utiliza uma sequência de jogos híbridos.
  • O ponto crucial é a transição onde o desafiador gera chaves secretas para conjuntos não autorizados usando um trapdoor derivado de $T$ (do LWE sucinto) em vez de $td_B$. Isso garante que, mesmo quando os componentes do ciphertext são substituídos por valores uniformes, a distribuição das chaves secretas permanece estatisticamente indistinguível, evitando vazamento de informação sobre o LWE.

5. Significância

Este trabalho é significativo porque:

1. Resistência Quântica: Oferece uma solução eficiente para controle de acesso granular baseada em reticulados, uma das poucas famílias de primitivas criptográficas consideradas seguras contra computadores quânticos.
2. Eficiência Prática: A obtenção de ciphertexts de tamanho constante é um marco para a escalabilidade do CP-ABE. Em aplicações reais (como IoT ou nuvem), onde as políticas de acesso podem ser complexas, não ter que aumentar o tamanho da mensagem criptografada conforme a política cresce é uma vantagem enorme.
3. Otimização de Broadcast Encryption: Resolve o problema de longo prazo de criar esquemas de difusão com ciphertexts independentes do número de usuários, alcançando limites ótimos sob suposições de reticulados.
4. Avanço Teórico: Demonstra a utilidade prática da suposição de LWE Sucinto, mostrando como ela pode ser usada para comprimir estruturas complexas (como políticas de acesso) em primitivas criptográficas padrão.

Em resumo, o artigo apresenta uma construção teórica robusta que equilibra segurança pós-quântica e eficiência extrema, tornando o CP-ABE mais viável para cenários de larga escala.