💻 computer science

Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits

Este trabalho propõe a avaliação tensorial oblívia sucinta (OTE) baseada no problema LWE, uma nova ferramenta que permite a construção de primitivas criptográficas avançadas, incluindo a primeira avaliação de função lacônica adaptativamente segura para todas as funções.

Autores originais: Damiano Abram, Giulio Malavolta, Lawrence Roy

Publicado 2026-04-21

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Damiano Abram, Giulio Malavolta, Lawrence Roy

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

Imagine que você tem um segredo muito longo, como uma lista de compras gigante (vamos chamar de Alice), e seu amigo tem uma lista pequena de ingredientes específicos que ele quer usar (vamos chamar de Bob). O objetivo deles é combinar essas duas listas para criar uma "receita mestra" (o produto tensorial) sem que Alice revele sua lista completa e sem que Bob revele quais ingredientes ele escolheu.

O problema é que, normalmente, para fazer isso com segurança, eles teriam que trocar mensagens gigantescas, o que seria lento e caro.

Este artigo de pesquisa propõe uma solução mágica chamada Avaliação Cega de Tensores (OTE). É como se Alice e Bob pudessem trocar apenas duas mensagens curtas (como dois bilhetes de papel) e, ao final, ambos tivessem pedaços de uma receita secreta que, quando somados, revelam o resultado perfeito, sem que ninguém tenha visto o segredo do outro.

Aqui está uma explicação passo a passo, usando analogias do dia a dia:

1. O Grande Truque: A "Caixa de Ferramentas" (OTE)

Pense no OTE como uma caixa de ferramentas mágica.

Alice tem uma caixa cheia de ferramentas (sua lista longa).
Bob tem uma chave pequena (sua lista curta).
Eles querem saber o que acontece quando a chave de Bob abre todas as ferramentas de Alice.
A inovação: Em vez de Alice enviar todas as ferramentas (o que seria uma caixa enorme), ela envia apenas um resumo (um "hash" ou impressão digital) da caixa. Bob envia uma chave codificada.
Com apenas essas duas pequenas peças de papel, eles conseguem calcular o resultado final localmente. A mensagem de Alice não cresce com o tamanho da lista dela; ela permanece pequena, não importa se a lista tem 10 ou 10 milhões de itens.

2. O Segredo da Matemática: "Chaves de Cadeado" (LWE)

Como eles fazem isso sem que um espione o outro? Eles usam um conceito matemático chamado Learning With Errors (LWE).

Imagine que Alice e Bob estão jogando com cadeados e chaves, mas as chaves têm um pouco de "ferrugem" ou "ruído" nelas.
Para um espião, o cadeado parece aleatório e impossível de abrir. Mas para Alice e Bob, que sabem exatamente onde está a ferrugem, eles conseguem combinar as peças perfeitamente.
O artigo mostra como usar esse "ruído" a favor deles para criar um sistema onde a comunicação é mínima, mas a segurança é máxima.

3. As Aplicações Mágicas (O que podemos fazer com isso?)

O artigo não para apenas na caixa de ferramentas; ele mostra como usar essa ferramenta para criar outros superpoderes criptográficos:

A. O "Carteiro Cego" (Função Laconica)

Imagine que você quer que um carteiro (Alice) entregue uma carta para você (Bob) baseada em um código secreto.

Antes: O carteiro precisava ler todo o seu endereço, escrever um bilhete gigante e enviar.
Com o novo método: O carteiro envia apenas um carimbo (hash) do seu endereço. Você, com seu código secreto, gera uma resposta curta. O carteiro recebe a resposta e sabe exatamente o que fazer, sem nunca ter lido seu endereço completo.
O diferencial: Isso funciona mesmo se o carteiro escolher o endereço depois de ver o carimbo (segurança adaptativa), algo que antes era impossível sem assumir que a matemática era mais forte do que realmente é.

B. A "Fábrica de Chaves" (Hashing com Armadilha)

Imagine que você tem uma máquina complexa (uma função) e quer que ela processe seus dados.

O problema: Geralmente, você precisa enviar a descrição inteira da máquina para o processador.
A solução: Você envia apenas um carimbo da máquina. O processador envia uma chave de entrada. Juntos, eles geram o resultado.
A mágica: O tamanho do carimbo da máquina é fixo e pequeno, não importa o quão complexa seja a máquina. Isso permite processar programas inteiros (como um sistema operacional) com mensagens minúsculas.

C. O "Segredo Dividido" (Compartilhamento de Segredos)

Imagine que Alice e Bob querem calcular algo juntos, mas não querem confiar um no outro.

Eles usam o OTE para dividir o resultado em duas partes. Alice tem a metade A, Bob tem a metade B.
Juntos, A + B = o resultado. Sozinhos, A e B são apenas lixo inútil.
O artigo mostra como fazer isso de forma extremamente eficiente, permitindo que Alice envie uma mensagem minúscula, mesmo que seus dados sejam gigantes.

4. Por que isso é importante? (A Analogia do "Sufoco")

Antes deste trabalho, para fazer essas trocas seguras, as mensagens cresciam junto com os dados. Era como tentar enviar um livro inteiro por carta postal para cada pequena pergunta que você tinha.

O problema anterior: Se você tivesse 1 milhão de dados, a mensagem teria 1 milhão de caracteres.
A solução deste artigo: A mensagem tem o tamanho de uma frase, não importa se você tem 1 milhão ou 1 bilhão de dados. É como se você pudesse enviar um livro inteiro por um único SMS.

Resumo Final

Os autores criaram uma nova "chave mestra" matemática (baseada em LWE) que permite que duas pessoas realizem cálculos complexos juntos trocando apenas bilhetes pequenos.

Segurança: Ninguém vê os dados do outro.
Eficiência: As mensagens são curtas, independentemente do tamanho dos dados.
Versatilidade: Serve para proteger privacidade em bancos de dados, permitir computação em nuvem segura e criar sistemas de votação ou leilão onde ninguém sabe quem votou em quê, mas todos sabem o resultado.

É como se a criptografia tivesse descoberto um atalho que permite viajar a velocidades da luz sem precisar de um avião gigante, apenas com um pequeno bilhete de embarque.

Título: Avaliação Cega de Tensores Succinta e Aplicações: Avaliação de Funções Laconica Adaptativamente Segura e Hashing com Porta-Traseira para Todos os Circuitos

1. Problema e Motivação

O artigo aborda o problema da Avaliação Cega de Tensores Não Interativa (NI-OTE). Neste cenário, duas partes, Alice (hasher) e Bob (encoder), possuem vetores $x$ e $y$ , respectivamente. O objetivo é que, após uma única rodada de mensagens simultâneas, elas possam computar localmente um compartilhamento aditivo secreto do produto tensorial $x \otimes y$ , sem revelar $y$ para Alice (privacidade do encoder) e, idealmente, sem revelar $x$ para Bob (privacidade do hasher).

O desafio central é a complexidade de comunicação. Intuitivamente, espera-se que as mensagens sejam proporcionais ao tamanho dos vetores. No entanto, o objetivo é construir protocolos onde o tamanho das mensagens e da Chave de Referência Comum (CRS) seja independente (ou logarítmico) da dimensão do vetor de entrada de Alice ( $|x|$ ), mantendo a segurança baseada em suposições padrão de criptografia pós-quântica, especificamente o Learning With Errors (LWE).

Além disso, o trabalho visa resolver problemas abertos na Avaliação de Funções Laconica (LFE), especificamente a construção de esquemas que sejam simultaneamente:

Adaptativamente seguros: O adversário pode escolher a entrada $x$ após ver os parâmetros públicos.
Taxa-1 (Rate-1): O tamanho da codificação é essencialmente igual ao tamanho da entrada mais o da saída, sem fatores de overhead polinomial grandes.

2. Metodologia e Contribuições Técnicas

Os autores propõem uma nova abordagem baseada em três pilares técnicos principais:

A. Avaliação Cega de Tensores Succinta (NI-OTE)

Construção Inicial (Half-Succinct): Os autores primeiro constroem um protocolo onde apenas a mensagem de Alice (o hash) é succinta (independente de $|x|$ ), enquanto a mensagem de Bob depende de $|x|$ . Isso é feito usando uma matriz aleatória $A$ e amostras LWE para codificar $y$ de forma que $Bob$ possa gerar um "share" baseado em $A \cdot x$ .
Bootstrapping para Succinctness Total: Para tornar a mensagem de Bob também succinta, eles utilizam uma técnica de recursão. O problema é que a recursão direta faria o tamanho da mensagem de Bob explodir. A solução inovadora é gerar a matriz de aleatoriedade $S$ (usada na codificação) de forma pseudorrandômica usando LWE, em vez de amostrá-la aleatoriamente. Isso permite que a "semente" de aleatoriedade ( $s$ ) seja pequena e constante, enquanto o hash de Alice é comprimido recursivamente. O resultado é um protocolo NI-OTE totalmente succinta com complexidade de comunicação logarítmica em relação a $|x|$ .

B. Codificações de Rede Adaptativas (Adaptive Lattice Encodings)

O Problema: As codificações de rede clássicas (BGG+14) são seguras apenas no cenário seletivo (onde a entrada é fixada antes de ver a chave pública). Se a entrada for escolhida adaptativamente, existem ataques para recuperar a chave secreta.
A Solução: Os autores introduzem uma nova estrutura de codificação onde o vetor de codificação $c$ é definido como:
$c^\top = s^\top A + r^\top (x^\top \otimes G) + e^\top$
Aqui, $s$ é a chave de criptografia e $r$ é uma chave de autenticação independente. Essa separação permite que as codificações sejam seguras contra ataques adaptativos sob a suposição LWE padrão, eliminando a necessidade de "complexity leveraging" (que exigiria parâmetros de segurança subexponenciais).
Compressão: Eles desenvolvem um método para comprimir essas codificações adaptativas usando o protocolo NI-OTE, reduzindo o tamanho da codificação de $O(|x|)$ para $O(\log |x|)$ .

C. Hashing com Porta-Traseira Reverso (Reverse Trapdoor Hashing - RTDH)

Combinando o NI-OTE succinto com esquemas de LFE existentes, os autores constroem um RTDH. Diferente do hashing tradicional (onde se hash a entrada e gera uma chave para a função), no RTDH reverso, Alice hash a função $f$ e Bob gera uma codificação para a entrada $x$ .
Isso permite que, em uma única rodada, as partes obtenham um compartilhamento secreto de $f(x)$ .

3. Resultados Principais

O trabalho apresenta os seguintes resultados teóricos e construtivos:

NI-OTE Succinta sob LWE:
- Um protocolo para $x \in \mathbb{Z}_q^m$ e $y \in \mathbb{Z}_q^\ell$ com complexidade de comunicação $\ell \cdot \text{poly}(\lambda) + \text{poly}(\lambda, \log m)$ e CRS de tamanho $\text{poly}(\lambda, \log m)$ .
- Segurança provada sob a suposição LWE padrão (não adaptativa).
Avaliação de Funções Laconica (LFE) Adaptativamente Segura e Rate-1:
- Primeira Construção: É a primeira LFE que é simultaneamente adaptativamente segura e Rate-1 para funções de profundidade $D$ .
- Complexidade: Comunicação de $m + \ell + D \cdot \text{poly}(\lambda)$ .
- Melhoria: Supera trabalhos anteriores (como Quach et al., FOCS 2018) que exigiam suposições LWE adaptativas (que foram quebradas pelos próprios autores neste trabalho) ou não eram Rate-1.
Hashing com Porta-Traseira (TDH) para Todas as Funções:
- Construção de um TDH para todas as funções (e programas RAM) baseado em Ring-LWE.
- O tamanho da chave de codificação é $|f| \cdot \text{poly}(\lambda, \log m)$ , o que é próximo do ótimo, superando construções anteriores que suportavam apenas funções lineares ou tinham chaves grandes.
Compartilhamento Secreto Homomórfico (HSS) Succinto:
- Um esquema HSS de chave pública para todas as funções, onde a complexidade de comunicação é logarítmica no tamanho da entrada longa de Alice, uma melhoria significativa sobre trabalhos anteriores que eram limitados a circuitos NC1 ou tinham complexidade polinomial fracionária.
Transferência Cega Laconica (OT) com Taxa 1/2:
- Um protocolo de OT em lote (batch) com taxa de transferência de 1/2 (o melhor possível), onde a mensagem do receptor é de tamanho constante.

4. Contra-Exemplo e Segurança

Os autores demonstram que a suposição de LWE Adaptativo proposta em trabalhos anteriores (Quach et al., 2018) é falsa em configurações de parâmetros otimistas (onde o número de amostras pode ser arbitrariamente maior que a dimensão da rede). Eles apresentam um ataque eficiente que recupera a chave secreta, validando a necessidade de suas novas construções baseadas em LWE padrão e codificações adaptativas seguras.

5. Significado e Impacto

Este trabalho é significativo por várias razões:

Quebra de Barreiras: Resolve o problema de longo prazo de construir LFE adaptativamente segura e Rate-1 sob suposições padrão, algo considerado um problema aberto.
Novas Ferramentas: A introdução de "Adaptive Lattice Encodings" e o protocolo "Succinct NI-OTE" são ferramentas criptográficas de propósito geral que provavelmente encontrarão aplicações em outras áreas (como criptografia baseada em redes, computação segura e privacidade).
Eficiência: As construções oferecem parâmetros de comunicação quase ótimos (logarítmicos ou constantes), tornando protocolos criptográficos complexos mais viáveis na prática.
Unificação: Demonstra como a avaliação de tensores pode ser usada como uma peça fundamental para construir uma variedade de primitivas criptográficas avançadas (TDH, HSS, OT, LFE) de forma unificada e eficiente.

Em resumo, o artigo estabelece um novo marco na criptografia baseada em retículos, fornecendo protocolos eficientes e seguros para computação multipartidária sem interação excessiva, superando limitações de segurança e eficiência de trabalhos anteriores.