Resumo Técnico: Funções de Independência Limitada Rápidas e Seus Duals

Declaração do Problema

O artigo aborda o desafio de construir primitivas criptográficas que mimetizem as propriedades estatísticas de funções aleatórias e códigos lineares aleatórios, mantendo um overhead computacional constante. Especificamente, os autores buscam implementações "rápidas" — definidas como computáveis por circuitos aritméticos de tamanho linear (tamanho $O(n)$) — que satisfaçam:

1. Independência Limitada: Funções de hash que são $t$-vezes independentes para qualquer $t$ constante.
2. Códigos Duals Rápidos: Famílias de códigos lineares onde tanto o código quanto seu dual admitem codificação sistemática rápida e alcançam distâncias próximas ao limite de Gilbert-Varshamov (GV).
3. Propriedades de Aleatoriedade Mais Fortes: Extensão além da simples distância para propriedades como decodificabilidade de lista, garantindo que os códigos se comportem como códigos lineares aleatórios mesmo sob restrições locais (similaridade local).

Trabalhos anteriores, como [IKOS08] e [DI14], estabeleceram funções de hash pareadas independentes rápidas e códigos rápidos que se aproximam do limite GV, mas frequentemente com limitações em relação ao parâmetro de independência $t$, o campo de operação ou a capacidade de otimizar simultaneamente o código e seu dual. Uma construção recente de [BR26] melhorou os códigos duals rápidos, mas foi restrita a campos binários, exigia uma taxa fixa de 1/2, possuía probabilidade de falha não negligenciável e carecia de codificação sistemática.

Metodologia

Os autores baseiam-se na "construção IKOS" (Ishai, Kushilevitz, Ostrovsky, Sahai) e na "construção DI" (Druk, Ishai), generalizando-as para parâmetros de independência mais elevados.

1. Generalizando Funções de Hash

A construção central para funções de hash segue um pipeline de três etapas:

1. Codificação Externa: Aplica um código linear rápido com grande distância sobre um alfabeto grande (mas constante) à entrada.
2. Hashing Interno: Aplica funções de hash $t$-vezes independentes de tamanho constante a cada coordenada do vetor codificado.
3. Extração: Aplica a transposta de uma matriz geradora de um bom código (atuando como um extrator) ao resultado.

Para alcançar a independência $t$-vezes, os autores substituem as funções de hash pareadas de tamanho constante na etapa interna por funções de hash $t$-vezes independentes de tamanho constante. Eles provam que, se o código externo tiver distância suficientemente grande (especificamente $> 1 - 1/t^2$), a distinção de $t$ entradas é preservada através de uma fração suficiente de coordenadas, permitindo que as funções de hash internas produzam saídas uniformes e independentes que a etapa de extração final preserva.

2. Família de Saída Uniforme Linear (LUOF)

Para construir os códigos, os autores utilizam o conceito de uma Família de Saída Uniforme Linear (LUOF). Uma matriz $A$ é uma LUOF se, para qualquer entrada não nula $x$, a saída $xA$ for uniformemente distribuída.

• LUOF Rápida: Os autores generalizam a construção de [DI14] para criar uma $t$-LUOF rápida. Uma matriz $A$ é uma $t$-LUOF se, para qualquer conjunto de $t$ entradas linearmente independentes $x_1, \dots, x_t$, as saídas $x_1A, \dots, x_tA$ forem uniformes e estocasticamente independentes.
• Construção: Semelhante à construção de funções de hash, isso envolve um código externo, uma camada de matrizes constantes aleatórias (atuando como a função "interna") e uma etapa de extração. Os autores provam que, se o código externo tiver distância suficiente, as matrizes aleatórias internas mapeiam entradas linearmente independentes para saídas uniformes e independentes.

3. Construindo Códigos Duals Rápidos

Usando uma matriz $t$-LUOF $A \in \mathbb{F}_q^{k \times r}$, os autores definem um código $C$ com o mapa de codificação sistemática $x \mapsto (x, xA)$.

• Dualidade: O código dual $C^\perp$ é gerado pelo mapa $y \mapsto (-yA^\top, y)$.
• Princípio da Transposição: Citando o princípio da transposição (Lema 3.4), eles argumentam que, se computar $xA$ é rápido (tamanho linear), então computar $yA^\top$ também é rápido.
• Independência do Dual: Uma contribuição técnica crucial é provar que, se $A$ é uma $t$-LUOF, então $A^\top$ também é uma $t$-LUF (Lema 3.9). Isso depende do Lema XOR de Vazirani e garante que o código dual herde as fortes propriedades de aleatoriedade do código primal.

Principais Contribuições e Resultados

1. Funções de Hash $t$-vezes Independentes Rápidas

• Resultado: Para qualquer constante $t$, os autores constroem uma família de funções de hash $t$-vezes independentes computáveis por circuitos de tamanho linear.
• Otimização: Para o campo binário ($q=2$), o grau algébrico é otimizado para $\log_2 t$. Isso é quase ótimo, pois graus menores falhariam em suportar a independência $t$-vezes.
• Eficiência: O tamanho do circuito é $O(k+r)$, onde $k$ é o comprimento da entrada e $r$ é o comprimento da saída. A constante oculta depende de $t$ (aproximadamente $\Theta(t^7)$), mas permanece constante para $t$ fixo.

2. Códigos Rápidos com Duals Rápidos (Limite GV)

• Resultado: Os autores constroem uma família de códigos $C$ e seus duais $C^\perp$ sobre qualquer campo finito $\mathbb{F}_q$ com taxa arbitrária $R \in (0, 1)$.
• Propriedades:
  • Ambos, $C$ e $C^\perp$, admitem codificação sistemática rápida (tamanho linear).
  • Ambos alcançam distâncias $\varepsilon$-próximas ao limite de Gilbert-Varshamov com probabilidade $1 - 2q^{-\varepsilon n}$.
  • A construção possui probabilidade de falha negligenciável (ao contrário de [BR26]).
  • Suporta um circuito universal de tamanho linear para codificação.

3. Códigos de Decodificação de Lista Rápidos com Duals Rápidos

• Resultado: Utilizando a propriedade $t$-LUOF, os autores estendem a construção para códigos que são $t$-localmente similares a códigos lineares aleatórios.
• Decodificação de Lista: Eles provam que, para qualquer constante $t$, os códigos construídos (e seus duais) são $(\rho, L)$-decodificáveis de lista até a capacidade de decodificação de lista, com tamanho de lista $L = O(1/\varepsilon)$.
• Novidade: Esta é a primeira construção (até onde os autores sabem) que simultaneamente alcança codificação rápida, codificação de dual rápida e decodificabilidade de lista ótima para ambos os códigos.

Significância e Aplicações Criptográficas

O artigo demonstra que essas construções servem como blocos de construção poderosos para a criptografia, particularmente em cenários que exigem alta eficiência e fortes garantias de segurança.

1. Computação Multipartidária (MPC) Perfeitamente Segura

Os autores apresentam os primeiros protocolos não triviais de MPC perfeitamente segura onde a complexidade do circuito escala linearmente com o número de partes ($O(n)$).

• Contexto: Protocolos anteriores usando códigos algébricos (como Reed-Solomon) frequentemente incorriam em overhead quase linear.
• Aplicação: Usando os códigos duais rápidos, eles constroem um protocolo de Avaliação Linear Oblíqua (OLE) e o estendem para funções gerais de tamanho constante. O protocolo alcança um limiar de segurança de $t = (1/2 - \varepsilon)n$ contra adversários passivos.

2. Produtos Matriz-Vetor Criptografados (EMVP)

No contexto de criptografia baseada em complexidade, os autores aplicam seus códigos duais rápidos a produtos matriz-vetor criptografados.

• Melhoria: Sua construção supera as limitações da abordagem de [BR26] (que era limitada a $\mathbb{F}_2$ e tinha probabilidade de falha não negligenciável).
• Benefício: Isso permite protocolos de EMVP onde tanto a codificação da matriz quanto a codificação da consulta possuem complexidade de circuito assintoticamente ótima.

3. Substitutos Conservadores para Códigos Lineares Aleatórios

A construção $t$-LUOF fornece um substituto "conservador" para códigos lineares aleatórios em aplicações que dependem da dureza da álgebra linear ruidosa (ex: Aprendizado de Paridade com Ruído - LPN).

• Vantagem: Enquanto construções anteriores dependiam apenas de distância mínima (similaridade local de 1-vez), a $t$-LUF garante similaridade local de $t$-vezes, assegurando propriedades combinatórias mais fortes como a decodificabilidade de lista. Isso oferece uma suposição de segurança mais robusta contra ataques que possam explorar estruturas locais.

4. Hashing Amigável para MPC

As funções de hash $t$-vezes independentes rápidas com baixo grau algébrico são diretamente aplicáveis a protocolos de MPC onde tanto o tamanho do circuito quanto o grau algébrico impactam a complexidade de comunicação e de rodadas. A construção otimiza ambos simultaneamente.

Conclusão

O artigo generaliza com sucesso construções anteriores de tamanho linear para suportar parâmetros de independência mais elevados e propriedades de aleatoriedade mais fortes. Ao introduzir $t$-LUFs rápidas e provar suas propriedades de dualidade, os autores fornecem um framework unificado para construir códigos e funções de hash que são simultaneamente rápidos, sistemáticos e estatisticamente robustos. Esses resultados permitem novos protocolos criptográficos com complexidade assintótica ótima, particularmente em MPC de informação teórica e computação criptografada.