Improved Search-to-Decision Reduction for Random Local Functions

Resumo Técnico: Redução Melhorada de Busca para Decisão para Funções Locais Aleatórias

1. Problema e Contexto

O artigo aborda a segurança das Funções Locais Aleatórias (Random Local Functions), uma classe de primitivas criptográficas propostas por Goldreich [Gol11] como candidatas a Funções de Mão Única (OWF) de baixa complexidade (computáveis em tempo constante paralelo, ou seja, em circuitos de profundidade constante, $NC^0$).

• Definição: Uma função local aleatória $f_{G,P}$ é definida por um predicado $P$ de aridade $d$ (constante) e um hipergrafo $G$. Cada bit de saída é o resultado de aplicar $P$ a $d$ bits de entrada escolhidos aleatoriamente conforme as arestas do hipergrafo.
• O Desafio: A segurança dessas funções depende da dificuldade de dois problemas relacionados:
  1. Problema de Decisão (Decision Problem): Distinguir a saída da função (com uma semente aleatória) de uma string aleatória com o mesmo viés (bias). Se for difícil, a função atua como um Gerador de Números Pseudoaleatórios (PRG).
  2. Problema de Busca (Search Problem): Inverter a função, ou seja, recuperar a semente de entrada $s$ dada a saída.
• A Lacuna: Embora existam reduções conhecidas que transformam um algoritmo de decisão em um algoritmo de busca (redução Search-to-Decision), as reduções anteriores (como as de Applebaum [App12]) exigiam que o predicado $P$ fosse sensível (ou seja, que a mudança de uma variável de entrada sempre alterasse a saída). Muitos predicados candidatos não possuem essa propriedade, limitando a aplicabilidade das reduções existentes.

2. Contribuições Principais

Os autores (Kel Zin Tan e Prashant Nalini Vasudevan) apresentam uma nova redução Search-to-Decision que elimina a necessidade de o predicado ser sensível.

• Generalização do Predicado: A redução funciona para qualquer predicado de aridade constante, independentemente de possuir propriedades de sensibilidade. Isso amplia o conjunto de funções locais que podem ser provadas seguras (como PRGs) com base na dificuldade de inverter.
• Complexidade de Amostra: Dado um algoritmo eficiente que distingue a saída da função de aleatoriedade com vantagem $\epsilon$, os autores constroem um algoritmo de busca que inverte a função com probabilidade de sucesso $\Omega(\epsilon)$.
  • O algoritmo de busca requer $O(m(n/\epsilon)^2 \log^3(n/\epsilon))$ instâncias (onde $m$ é o número de saídas e $n$ o número de entradas).
  • Embora haja um custo de complexidade de amostra (fator polinomial em $n$) comparado a reduções para predicados sensíveis, a generalidade é o ganho principal.
• Generalizações Adicionais: O trabalho estende a redução para:
  • Aridade não constante ($d = \text{polylog}(n)$).
  • Hipergrafos com vértices distintos nas arestas (modelo alternativo comum).
  • Predicados ruidosos (adicionando ruído Bernoulli à saída), conectando-se ao problema de Learning Parity with Noise (LPN) esparsa.

3. Metodologia e Técnicas Chave

A abordagem difere fundamentalmente das técnicas anteriores (como a de Applebaum), que dependiam de construir um "preditor de próximo bit" intermediário. A nova técnica opera diretamente sobre o algoritmo de decisão através de transformações aleatórias no hipergrafo.

A. Ideia Central da Redução
O objetivo é usar o distinguidor $D$ (com vantagem $\epsilon$) para construir preditores $S_i$ que determinam a relação entre bits da semente secreta (ex: $s_1 \oplus s_i$).

1. Transformação $T_{a,b}$: Define-se uma transformação aleatória no hipergrafo $G$ que, para dois índices $a, b$, mantém os vértices inalterados se não forem $a$ ou $b$, e troca aleatoriamente entre $a$ e $b$ se o vértice for um deles.

   • Se $s_a = s_b$, a saída da função local permanece inalterada após a transformação (a distribuição não muda).
   • Se $s_a \neq s_b$, a transformação "desacopla" a saída da semente original, fazendo com que a distribuição se assemelhe mais a uma string aleatória (distribuição nula).

2. Argumento de Híbridos (Hybrid Argument):

   • Constroem-se uma sequência de distribuições híbridas $H_0, \dots, H_t$.
   • $H_0$ é a distribuição original (plantada).
   • $H_t$ é estatisticamente próxima da distribuição nula (aleatória).
   • Aplica-se um número $t = O(n \log(n/\epsilon))$ de transformações aleatórias. O tempo de mistura (mixing time) do processo garante que, após $t$ passos, o hipergrafo se torne independente da semente original.

3. Construção do Preditor $S_i$:

   • O preditor $S_i$ recebe $(G, y)$.
   • Aplica uma transformação aleatória $T_{a,b}$ seguida de uma transformação específica $T_{\pi(1), \pi(i)}$ (onde $\pi$ é uma permutação).
   • Se $s_1 = s_i$, a transformação final não altera a saída, mantendo a distribuição próxima de $H_r$.
   • Se $s_1 \neq s_i$, a transformação final move a distribuição para um estado próximo de $H_{r+1}$ (mais próximo do ruído).
   • O distinguidor $D$ é aplicado ao resultado. A diferença na probabilidade de $D$ retornar 1 entre os dois casos ($s_1=s_i$ vs $s_1 \neq s_i$) fornece uma vantagem de $\Omega(\epsilon/t)$.

4. Amplificação:

   • Como a vantagem do preditor é pequena ($\Omega(\epsilon/t)$), utiliza-se repetição e a desigualdade de Hoeffding para amplificar a confiança.
   • Testa-se ambos os valores possíveis para $s_1$ (0 ou 1). Para cada $i \in [2, n]$, estima-se a relação $s_1 \oplus s_i$.
   • Com alta probabilidade, recupera-se todos os bits da semente $s$.

B. Tratamento de Casos Especiais

• Predicados Não Sensíveis: A prova não depende da sensibilidade, mas sim das propriedades de mistura do hipergrafo e da correlação do predicado com paridades de subconjuntos (c-correlação).
• Predicados Ruidosos: Mostra-se que o ruído apenas reduz a distância estatística entre a saída e a distribuição aleatória, preservando a validade da redução, desde que o viés do predicado determinístico subjacente seja limitado.

4. Resultados e Implicações

• Teorema Principal (Informal): Se existe um algoritmo eficiente com vantagem $\epsilon$ para o problema de decisão de funções locais definidas por qualquer predicado $P$, então existe um algoritmo eficiente com sucesso $\Omega(\epsilon)$ para o problema de busca, usando $O(m(n/\epsilon)^2 \log^3(n/\epsilon))$ amostras.
• Construção de PRGs Fortes: Combinando este resultado com o compilador "weak-to-strong" de Applebaum e Kachlon [AK19], conclui-se que se uma família de funções locais é uma OWF (mesmo para predicados não sensíveis), então é possível construir um PRG local forte (com vantagem de distinção negligenciável) a partir dela.
• Limites Ótimos: Os autores discutem que, para predicados gerais, existe um "gap" trivial de $\sqrt{n}$ entre os problemas de busca e decisão (exemplo com predicado maioria). Sua redução está a um fator $\tilde{O}(n^{1.5})$ do limite teórico ideal, mas abre caminho para futuras otimizações.

5. Significado e Impacto

Este trabalho é significativo por:

1. Remover Barreiras Estruturais: Ao eliminar a exigência de sensibilidade, permite que uma gama muito mais ampla de predicados seja considerada segura para criptografia local, fortalecendo a base teórica das OWFs em $NC^0$.
2. Novas Técnicas: A introdução de transformações aleatórias no hipergrafo como ferramenta para reduzir problemas de busca para decisão é uma inovação técnica que pode ser aplicada em outros contextos de criptografia e teoria da complexidade.
3. Conexões com LPN e CSP: Reforça a ligação entre a segurança de funções locais e problemas fundamentais como Learning Parity with Noise (LPN) e Problemas de Satisfação de Restrições (CSP), sugerindo que a dureza de inverter essas funções é um pressuposto robusto para a criptografia pós-quântica e de baixa complexidade.

Em suma, o artigo fornece uma ferramenta teórica poderosa para transformar a dificuldade de distinguir saídas de funções locais em uma garantia de segurança para a recuperação da chave secreta, independentemente de propriedades estruturais específicas do predicado utilizado.