Hierarchical Identity-Based Signature with Designated Aggregator from Lattices

Resumo Técnico: Assinatura Hierárquica Baseada em Identidade com Agregador Designado a partir de Lattices

Declaração do Problema
Em organizações hierárquicas de grande escala (ex: universidades, agências governamentais, corporações), autenticar dados de múltiplos usuários em diferentes níveis apresenta desafios significativos. A Infraestrutura de Chave Pública (PKI) tradicional depende de Autoridades de Certificação (CAs), criando uma sobrecarga substancial de gerenciamento. Embora a Criptografia Baseada em Identidade (IBC) elimine os certificados ao utilizar identidades como chaves públicas, os esquemas padrão de Assinatura Baseada em Identidade (IBS) dependem tipicamente de um único Gerador de Chave Privada (PKG). Essa centralização cria um gargalo de desempenho e um ponto único de falha, tornando-a inadequada para hierarquias grandes e distribuídas. Além disso, quando inúmeros usuários em uma hierarquia precisam assinar dados, armazenar e verificar assinaturas individuais para cada usuário é ineficiente em termos de tempo, espaço e largura de banda. Os esquemas de Assinatura Baseada em Identidade Hierárquica (HIBS) existentes frequentemente dependem de suposições de teoria dos números (como o problema do Logaritmo Discreto), que são vulneráveis a ataques quânticos, ou carecem da capacidade de agregar assinaturas de múltiplos ramos em uma única prova compacta.

Metodologia
Os autores propõem um esquema de Assinatura Hierárquica Baseada em Identidade com Agregador Designado (HIBS-DA) construído sobre lattices (redes), proporcionando segurança pós-quântica. A metodologia integra três componentes principais:

1. Delegação de Chave Hierárquica: O sistema utiliza uma estrutura em árvore onde um PKG Raiz delega a geração de chaves para $t$ níveis. Uma entidade filha deriva sua chave secreta a partir da chave secreta de seu pai usando o algoritmo BasisDelegation (especificamente BasisDel), garantindo que a estrutura de trapdoor seja preservada sem revelar o trapdoor do pai.
2. Criptografia Baseada em Lattices: O esquema baseia-se na dureza do problema da Solução de Inteiro Curto (SIS). Ele emprega algoritmos como TrapGen para gerar matrizes públicas e bases de trapdoor curtas, SamplePre para gerar assinaturas (vetores curtos) e SampleRwithBasis para gerar matrizes invertíveis.
3. Agregação Designada: Para abordar a ineficiência de verificar múltiplas assinaturas, o esquema introduz um agregador designado. Esta entidade coleta assinaturas individuais de $N$ usuários em um nível hierárquico específico $k$. Usando o Teorema Chinês do Resto (CRT), o agregador combina essas assinaturas em uma única assinatura agregada compacta. Um passo crucial envolve projetar o vetor combinado na interseção dos lattices associados aos $N$ usuários para garantir que a assinatura agregada resultante permaneça curta e válida.

Principais Contribuições

• Primeira Construção de HIBS-DA Baseada em Lattices: O artigo afirma apresentar a primeira construção de um esquema HIBS-DA baseado em suposições de lattice, preenchendo uma lacuna na literatura onde tal esquema não existia anteriormente.
• Sintaxe Formal e Modelo de Segurança: Os autores definem formalmente o framework HIBS-DA, composto por seis algoritmos: Setup, Derive, Sign, Verify, Aggregate e AggregateVerify. Eles estabelecem um modelo de segurança baseado em Inexistência de Forja sob Ataque de Identidade Adaptativa e de Mensagem Escolhida (EUF-ID-CMA).
• Prova de Segurança: O esquema é provado seguro sob a suposição de que o problema SIS é computacionalmente inviável. A prova utiliza uma abordagem reducionista, mostrando que qualquer adversário de tempo polinomial probabilístico (PPT) capaz de forjar uma assinatura agregada pode ser usado para resolver o problema SIS.
• Análise de Eficiência: O artigo fornece uma análise abrangente de complexidade, demonstrando que o esquema é não interativo (complexidade de rodadas zero) e oferece reduções significativas nos custos de comunicação e verificação em comparação com a verificação de assinaturas individuais.

Resultados

• Corretude: O esquema garante que as assinaturas individuais sejam válidas e que a assinatura agregada autentique corretamente todas as mensagens e identidades subjacentes do nível hierárquico específico.
• Segurança: A construção alcança segurança EUF-ID-CMA, resistindo à forja mesmo quando um adversário tem acesso a oráculos de extração de chave e de assinatura para várias identidades e mensagens.
• Métricas de Complexidade:
  • Comunicação: A complexidade total de comunicação é aproximadamente $O((tm^2 + Nm)\lceil \log_2 q \rceil)$ bits, onde $t$ é a profundidade da hierarquia, $N$ é o número de signatários, e $m, n, q$ são parâmetros de lattice. Isso representa uma redução significativa em comparação com a transmissão de $N$ assinaturas individuais.
  • Computação: A fase de Setup possui complexidade de $\tilde{O}(n^2)$, Derive é $\tilde{O}(k \cdot m^3)$, Sign e Verify são $\tilde{O}(m^2)$ e $O(m^2)$ respectivamente, e Aggregate envolve $O(Nm)$ para CRT e $\tilde{O}(m^2)$ para amostragem. AggregateVerify requer $O(Nm^2)$.
  • Complexidade de Rodadas: O esquema é não interativo, exigindo zero rodadas de comunicação para os processos principais de assinatura e agregação.

Significância
O artigo posiciona o esquema HIBS-DA como uma solução prática para sistemas descentralizados modernos de grande escala que exigem autenticação de dados estruturada e de múltiplas fontes. Ao combinar o gerenciamento de chaves hierárquicas com a agregação de assinaturas, o esquema aborda os problemas de escalabilidade da IBS tradicional e a sobrecarga de certificados da PKI. Crucialmente, ao basear a construção em lattices, o esquema oferece segurança pós-quântica, tornando-o adequado para preparar a infraestrutura crítica em setores como e-governança, compartilhamento seguro de dados e gestão corporativa. Os autores enfatizam que o esquema permite a autenticação eficiente de documentos de múltiplos ramos de uma hierarquia usando uma única assinatura compacta, minimizando assim a sobrecarga computacional e de comunicação.