💻 computer science

A Broadcast Authenticated Encryption with Keyword Search in the Standard Model: Tightly Secure in Multi-User, Multi-Challenge Settings

Este artigo propõe um novo esquema de Criptografia Autenticada de Transmissão com Busca por Palavra-chave (BAEKS) fortemente seguro no modelo padrão que aborda configurações realistas de múltiplos usuários e múltiplos desafios, garantindo propriedades de ocultação e não falsificabilidade fortes, juntamente com uma variante eficiente de receptor único e avaliação experimental.

Autores originais: Sayantan Mukherjee

Publicado 2026-09-01

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Sayantan Mukherjee

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Na era digital, informações sensíveis são frequentemente guardadas em cofres criptografados, protegidas de olhares curiosos, mas também inacessíveis às próprias pessoas que precisam encontrar detalhes específicos dentro deles. Imagine um hospital onde os registros dos pacientes estão embaralhados para proteger a privacidade; um médico precisa encontrar um arquivo sobre uma alergia específica, mas não pode simplesmente pesquisar o texto embaralhado. Para resolver isso, os criptógrafos desenvolveram um sistema chamado criptografia pesquisável. Isso permite que um usuário gere uma chave especial, conhecida como porta lógica (trapdoor), que atua como uma impressão digital única para uma palavra-chave específica. Um servidor que detém os arquivos criptografados pode usar essa impressão digital para verificar se um arquivo contém essa palavra sem nunca ver a palavra em si ou o conteúdo do arquivo. No entanto, este sistema possui uma falha crítica: como as chaves de criptografia são públicas, um ator malicioso pode adivinhar palavras comuns, criar seus próprios arquivos de teste e compará-los com a porta lógica para fazer engenharia reversa da palavra-chave secreta. Isso é conhecido como ataque de adivinhação de palavra-chave, e ameaça expor os próprios segredos que o sistema foi projetado para proteger.

Pesquisadores tentaram corrigir isso introduzindo a autenticação, garantindo que apenas um remetente específico possa criar um arquivo pesquisável e apenas um receptor específico possa pesquisá-lo. Isso evoluiu para um cenário mais complexo chamado criptografia autenticada de transmissão com pesquisa de palavra-chave, onde um único remetente pode querer compartilhar um segredo com um grupo de receptores autorizados, como um médico compartilhando um diagnóstico com uma equipe de especialistas. Embora as tentativas anteriores desta tecnologia tenham oferecido alguma proteção, elas ficaram aquém em ambientes realistas e de alto risco. Elas frequentemente falharam ao não considerar cenários onde um invasor poderia comprometer múltiplos usuários ou fazer milhares de palpites simultâneos, e suas provas de segurança baseavam-se em atalhos matemáticos que as deixavam vulneráveis a ataques astutos. As soluções existentes eram como uma fechadura que funcionava perfeitamente em um laboratório de testes, mas poderia falhar se alguém tentasse arrombar a porta enquanto ela estava sendo chutada por uma multidão.

Um pesquisador do Instituto Indiano de Tecnologia, Jammu, propôs agora uma nova construção que aborda essas fraquezas de frente. Ele projetou um sistema que permanece seguro mesmo quando um invasor pode corromper múltiplos usuários e fazer um vasto número de consultas simultâneas de maneira caótica e intercalada. Seu trabalho introduz uma definição rigorosa de segurança que garante que a palavra-chave, a identidade do remetente e a identidade do receptor permaneçam completamente ocultas, mesmo sob os ataques mais agressivos. Ao contrário de modelos anteriores que dependiam de suposições idealizadas, este novo esquema é provado seguro no modelo padrão, o que significa que sua segurança se mantém sob escrutínio matemático do mundo real sem precisar depender de atalhos de "oráculo aleatório" hipotéticos que muitas vezes desmoronam sob pressão.

O pesquisador construiu sua solução usando um tipo específico de estrutura matemática conhecida como grupos de pareamento bilinear, que atuam como um filtro complexo e de múltiplas camadas para os dados. Ele demonstrou que seu sistema é "fortemente seguro" (tightly secure), um termo técnico que significa que a garantia de segurança não se degrada à medida que o número de usuários ou o número de ataques aumenta. Em muitos sistemas antigos, quanto mais usuários existem, mais fraca se torna a segurança, mas este novo design mantém sua força independentemente da escala. Eles também provaram que seu método impede que um invasor falsifique uma chave de pesquisa falsa ou um arquivo criptografado falso, garantindo que apenas o remetente e o receptor genuínos possam participar da pesquisa.

Para verificar se o seu design teórico poderia realmente funcionar na prática, o pesquisador implementou o sistema em uma máquina virtual padrão. Ele realizou experimentos com varying números de usuários e diferentes tamanhos de grupos de receptores, simulando tudo, desde um único médico pesquisando um registro até uma grande rede hospitalar compartilhando dados entre cem especialistas. Os resultados mostraram que o sistema é eficiente o suficiente para uso no mundo real. Para uma única pesquisa, o processo leva menos de um segundo e, mesmo ao pesquisar em um grupo de cem pessoas, o tempo necessário permanece gerenciável. O custo computacional escala linearmente, o que significa que, conforme o grupo cresce, o tempo necessário para pesquisar aumenta de forma previsível e constante, em vez de explodir em atrasos inutilizáveis.

Este trabalho representa um passo significativo à frente na proteção de dados criptografados contra adversários sofisticados. Ao refinar as definições de segurança e fornecer uma construção que resiste a ataques adaptativos, o pesquisador ofereceu uma ferramenta robusta para ambientes onde a privacidade é primordial. Suas descobertas sugerem que é possível ter um sistema onde os dados não estão apenas criptografados, mas também são pesquisáveis e autenticados, sem sacrificar a segurança em prol da conveniência ou da escala. O artigo conclui que, embora sua implementação atual seja uma prova de conceito, ela estabelece as bases para sistemas futuros que possam resistir a atores maliciosos que estão tentando ativamente quebrar a criptografia, garantindo que as informações sensíveis permaneçam verdadeiramente privadas mesmo em um cenário digital lotado.

Resumo Técnico: Criptografia Autenticada de Broadcast com Busca por Palavra-Chave Tightly Secure em Ambientes Multi-Usuário e Multi-Desafio

1. Definição do Problema

A Criptografia de Busca (Searchable Encryption - SE) permite que usuários realizem buscas sobre dados criptografados. Embora a Criptografia de Chave Pública com Busca por Palavra-Chave (PEKS) possibilite isso, ela é vulnerável a Ataques de Adivinhação de Palavras-Chave (Keyword Guessing Attacks - KGA), nos quais um adversário gera criptogramas para testar contra uma armadilha (trapdoor) e deduz a palavra-chave. Para mitigar isso, a Criptografia de Chave Pública Autenticada com Busca por Palavra-Chave (PAEKS) foi introduzida, exigindo a chave secreta do remetente para a criptografia. Isso foi posteriormente generalizado para a Criptografia de Broadcast Autenticada com Busca por Palavra-Chave (BAEKS) para suportar um remetente criptografando uma palavra-chave para um conjunto de receptores autorizados.

Apesar dos trabalhos existentes em BAEKS e PAEKS, várias lacunas críticas permanecem:

Modelos de Segurança: Esquemas existentes frequentemente carecem de definições de segurança para o cenário multi-usuário, multi-desafio, que é mais realista para sistemas implantados. Especificamente, eles falham em considerar corrupções adaptativas (onde um adversário obtém chaves secretas de usuários) e consultas intercaladas (onde um adversário desafia criptogramas e armadilhas simultaneamente).
Tightness (Estreiteza): As reduções de segurança atuais sofrem de perdas de segurança multiplicativas não triviais (por exemplo, proporcionais ao número de consultas ou usuários), o que significa que a garantia de segurança degrada significativamente à medida que o sistema escala.
Consistência: Provas anteriores de consistência computacional para BAEKS (especificamente em trabalhos de Emura) foram identificadas como incompletas ou carentes de argumentos de redução formais.
Anonimato: Muitos esquemas não ocultam simultaneamente a palavra-chave, a identidade do remetente e as identidades dos receptores tanto nos criptogramas quanto nas armadilhas sob modelos adversariais fortes.

2. Metodologia e Construção

O autor propõe um novo esquema BAEKS, denominado baeks, construído em grupos de emparelhamento bilinear (Tipo-3). A metodologia envolve:

Novas Definições de Segurança: O artigo introduz a segurança full-cpa, uma definição que permite a um adversário realizar consultas de desafio intercaladas em criptogramas, armadilhas e chaves secretas (corrupções adaptativas). Também define noções de não-falsificabilidade (ct-cma e trap-cma), que o autor argumenta serem implicadas pela segurança full-cpa.
Estratégia de Codificação: Diferente de construções anteriores que utilizavam codificações de hash Boneh-Boyen (que falham em cenários de múltiplos desafios devido a dependências lineares), o autor adota uma estrutura inspirada em Criptografia Baseada em Identidade (IBE) e IBE Hierárquica (HIBE) estritamente seguras (tightly secure) usando estruturas PRF de Naor-Reingold randomizadas.
- Usuários são representados por matrizes $U_j$ (remetente) e $V_j$ (receptor).
- Palavras-chave são codificadas via matrizes $K_{\iota, b}$ .
- Uma tupla $(S, \omega, R)$ é codificada como uma soma desses componentes: $\sum U_{S,i} + \sum K_{\omega,i} + \sum V_{R,i}$ .
- A aleatoriedade é injetada via uma função aleatória $RF(S||\omega||R)$ nas codificações do criptograma e da armadilha.
Técnica de Prova: A prova de segurança utiliza um argumento de híbrido envolvendo uma série de jogos ( $G_0$ $G_{0}$ a $G_6$ $G_{6}$ ). Um componente crucial é um Core Lemma (Teorema 2) que estabelece a indistinguibilidade do sistema sob consultas de oráculo específicas. A prova baseia-se na suposição Lateral Matrix Diffie-Hellman (lat-MDDH).
- A prova lida com corrupções adaptativas garantindo que, mesmo quando as chaves secretas de usuários não desafiados são reveladas, a entropia das chaves dos usuários desafiados permanece suficiente para injetar aleatoriedade sem detecção.
- O autor aborda a condição de "não-trivialidade" restringindo o adversário de consultar chaves secretas para usuários envolvidos em criptogramas ou armadilhas de desafio.

3. Principais Contribuições

Nova Definição de Segurança: O artigo define a segurança full-cpa para BAEKS, cobrindo ambientes multi-usuário, multi-desafio e corrupções adaptativas com consultas intercaladas. Esta é a primeira tal definição para BAEKS (e PAEKS) que alcança segurança estreita (tight security) (a perda de redução de segurança é constante, independente do número de consultas).
Construção Tightly Secure: O autor apresenta uma nova construção BAEKS que alcança segurança full-cpa adaptativa sob a suposição padrão lat-MDDH no modelo padrão. Restringir isso a um único receptor produz um PAEKS estritamente seguro.
Não-falsificabilidade: O artigo demonstra que a noção de segurança full-cpa proposta implica inerentemente a não-falsificabilidade tanto para criptogramas quanto para armadilhas.
Análise de Consistência: O autor fornece uma análise rigorosa das provas de consistência em trabalhos anteriores (especificamente o de Emura), identificando lacunas e oferecendo uma construção estatisticamente consistente para seu próprio esquema.
Implementação: O esquema foi implementado em Python usando o framework Charm. Experimentos foram conduzidos em uma máquina virtual para avaliar o desempenho através de variações no número de receptores ( $\ell$ ), níveis de segurança ( $k$ ) e tamanhos de espaço de palavra-chave/usuário ( $\alpha, u$ ).

4. Resultados

Segurança: O esquema é provado seguro no modelo padrão sob a suposição lat-MDDH. A redução de segurança é estreita (tight), evitando a perda multiplicativa ( $\Theta(|Q_{Ct}| + |Q_{Tr}|)$ ) encontrada em esquemas BAEKS e PAEKS anteriores.
Desempenho:
- Setup e KeyGen: São executados uma vez por sistema/usuário. A complexidade do Setup escala linearmente com o tamanho do espaço de palavras-chave $\alpha$ .
- SrchEnc e TrapGen: São eficientes. O custo da criptografia e da geração de armadilha é amplamente independente do número de usuários $u$ , escalando linearmente com o comprimento da palavra-chave $\alpha$ e o número de receptores $\ell$ .
- Teste: O servidor em nuvem realiza $2\ell$ emparelhamentos bilineares para verificar uma correspondência. Para PAEKS ( $\ell=1$ ), isso requer apenas 2 emparelhamentos.
- Dados Experimentais: O autor relata que para $\ell=1$ (PAEKS), o esquema é comparável em eficiência aos trabalhos existentes, enquanto oferece segurança mais estreita. Para valores maiores de $\ell$ , o overhead é gerenciável, embora o esquema seja notado como ligeiramente menos eficiente em tamanho de criptograma/chave comparado ao esquema de consistência estatística de Mukherjee [42], porém superior em garantias de segurança.

5. Significância e Alegações

O artigo afirma reformular os modelos de segurança de BAEKS ao abordar os cenários de ameaça mais realistas: ambientes multi-usuário com corrupções adaptativas e desafios intercalados. A principal significância reside em alcançar segurança estreita (tight security) nesses cenários, o que era um problema em aberto para BAEKS e PAEKS.

O autor enfatiza que seu trabalho fornece o primeiro formalismo para BAEKS que simultaneamente garante:

Ocultamento da palavra-chave.
Anonimato do remetente e do receptor.
Resistência a corrupções adaptativas.
Reduções de segurança estreitas (tight).

O artigo conclui modestamente, observando que, embora a construção atual seja uma prova de conceito prática, trabalhos futuros poderiam visar construções robustas contra adversários maliciosos que geram seus próprios pares de chaves e, potencialmente, otimizar ainda mais o tamanho do criptograma. O trabalho também destaca que a segurança estreita de sua construção BAEKS traduz-se imediatamente para um PAEKS estritamente seguro, preenchendo uma lacuna na literatura para criptografia de busca autenticada de receptor único.