💻 computer science

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$ , Generically)

Este artigo introduz uma transformação genérica que converte PRFs fracas em PRFs fortes com sobrecarga mínima de profundidade, permitindo a construção de PRFs computáveis em $\mathsf{NC}^1$ a partir de pressupostos padrão, incluindo LWE, LPN e CDH, resolvendo assim problemas abertos de longa data na criptografia de baixa profundidade.

Autores originais: Youlong Ding, Aayush Jain, Ilan Komargodski

Publicado 2026-08-27

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Youlong Ding, Aayush Jain, Ilan Komargodski

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

No mundo digital, a segurança muitas vezes depende de um tipo especial de ferramenta matemática chamada função pseudorandom (pseudorandom function). Imagine uma máquina que recebe um código secreto e um pedaço de dado, e então cospe uma sequência de números que parece completamente aleatória para quem está observando. Se a máquina estiver funcionando corretamente, ninguém consegue distinguir sua saída de uma sequência verdadeiramente aleatória, mesmo que tenham visto a máquina trabalhar muitas vezes antes. Essas ferramentas são as fechaduras e chaves invisíveis que protegem tudo, desde o banco online até mensagens privadas. Durante décadas, pesquisadores têm tentado construir essas máquinas para que elas funcionem o mais rápido possível, especificamente fazendo com que operem em pouquíssimos passos. Na linguagem da ciência da computação, isso significa construí-las com um circuito muito raso, permitindo que o cálculo aconteça quase instantaneamente em processadores modernos. Quanto mais rápidas e simples forem essas ferramentas, mais eficientemente elas podem ser usadas em sistemas complexos como votação segura ou compartilhamento de dados privados.

Por muito tempo, houve uma lacuna persistente em nossa capacidade de construir essas máquinas rápidas e rasas. Sabíamos como criá-las usando pressupostos matemáticos muito fortes e complexos, mas estes exigiam circuitos profundos e lentos. Por outro lado, podíamos construir circuitos rasos, mas apenas se dependêssemos de pressupostos mais fracos e menos comprovados ou de estruturas matemáticas muito específicas e rígidas. Era como ter uma chave que abria uma porta, mas era pesada demais para carregar, ou uma chave que era leve, mas só servia em uma fechadura única e estranha. O objetivo era encontrar uma maneira de criar uma chave leve que pudesse abrir qualquer porta, usando apenas as fechaduras mais padrão e confiáveis disponíveis. Esse desafio permaneceu por quase trinta anos, limitando o quão eficientemente podíamos proteger o mundo digital.

Uma equipe de pesquisadores conseguiu agora preencher essa lacuna com um novo método geral que transforma uma ferramenta mais fraca e fácil de construir em uma ferramenta forte e segura sem reduzir sua velocidade. O trabalho deles, publicado no artigo intitulado "Pseudorandom Functions in NC1 from LWE/LPN/CDH", demonstra que é possível construir essas máquinas rápidas e rasas usando três dos pressupostos mais fundamentais e amplamente confiáveis da criptografia. Os pesquisadores alcançaram isso refinando uma ideia antiga chamada construção GGM, que constrói uma função complexa ao percorrer uma árvore de cálculos menores. A maneira tradicional de fazer isso era como caminhar por um corredor longo onde cada passo exigia a mesma quantidade de esforço, tornando a jornada total longa e lenta. O novo método muda a forma do corredor. À medida que o processo avança mais profundamente na árvore, a quantidade de trabalho necessária em cada etapa diminui geometricamente. Os primeiros passos são pesados, mas os passos subsequentes tornam-se cada vez mais leves, tão rapidamente que o esforço total permanece pequeno. Essa técnica de "decréscimo" (tapering) permite que os pesquisadores mantenha todo o processo dentro dos limites de um circuito raso e rápido.

Para provar que este novo método funciona, a equipe o aplicou a três problemas matemáticos específicos que são conhecidos por serem difíceis de resolver. O primeiro é o problema de Aprendizado com Erros (Learning With Errors), que envolve encontrar um padrão oculto em um conjunto de dados ruidosos. Tentativas anteriores de construir máquinas rápidas a partir deste problema exigiam uma versão mais complexa e específica da matemática que utilizava números muito grandes. O novo trabalho mostra que a versão padrão, com números muito menores, é suficiente. O segundo problema, Aprendizado de Paridade com Ruído (Learning Parity with Noise), lida com a busca de um padrão oculto em um fluxo de bits que teve seus valores invertidos aleatoriamente. Os pesquisadores mostraram que seu método funciona com a versão padrão deste problema, eliminando a necessidade das versões especializadas e estruturadas que eram anteriormente exigidas. O terceiro problema, a suposição de Diffie-Hellman Computacional (Computational Diffie-Hellman), um pilar da segurança da internet moderna usado para trocar chaves secretas. Durante décadas, a única maneira conhecida de construir máquinas rápidas a partir desta suposição dependia de uma versão mais forte e restritiva do problema. A nova construção prova que a versão padrão é suficiente.

A significância deste trabalho reside em sua generalidade e em sua dependência de pressupostos padrão. Ao demonstrar que uma ferramenta fraca e rasa pode ser elevada a uma ferramenta forte e segura sem adicionar profundidade, os pesquisadores desbloquearam a capacidade de construir funções rápidas e seguras a partir dos problemas matemáticos mais básicos e bem estudados. Isso resolve várias questões de longa data no campo e fornece um novo e flexível modelo para futuros sistemas criptográficos. Os pesquisadores não apenas sugeriram que isso poderia ser possível; eles forneceram uma construção concreta, passo a passo, e uma prova rigorosa de que funciona. Eles demonstraram que a profundidade da máquina resultante é essencialmente a mesma que a profundidade da ferramenta inicial, preservando a vantagem de velocidade enquanto ganham a segurança necessária.

Esta conquista significa que, pela primeira vez, podemos construir estas ferramentas de segurança essenciais usando os fundamentos matemáticos mais comuns e confiáveis, sem sacrificar a velocidade. Isso remove a necessidade de variantes especializadas e complexas desses problemas que anteriormente se pensava serem necessárias para a eficiência. O resultado é uma base mais robusta e versátil para a segurança digital do futuro, permitindo métodos de criptografia mais rápidos e eficientes que podem ser implantados em uma ampla gama de tecnologias. O trabalho serve como uma prova definitiva de que a barreira entre ferramentas rápidas e fracas e ferramentas rápidas e fortes foi quebrada, abrindo as portas para uma nova era de design criptográfico eficiente.

Resumo Técnico: Funções Pseudoaleatórias em NC1 de LWE/LPN/CDH

1. Enunciado do Problema

A construção de Funções Pseudoaleatórias (PRFs) com baixa complexidade paralela (especificamente dentro da classe NC1, computáveis por circuitos de profundidade logarítmica e tamanho polinomial) tem sido um problema aberto de longa data na criptografia. Embora as PRFs possam ser construídas genericamente a partir de Geradores de Números Pseudoaleatórios (PRGs) através da transformação Goldreich-Goldwasser-Micali (GGM), este método é inerentemente sequencial. Mesmo que o PRG subjacente seja computável em profundidade logarítmica, a PRF resultante exigirá uma profundidade $\omega(\log n)$ , colocando-a fora de NC1.

Antes deste trabalho, as PRFs computáveis em NC1 conhecidas eram escassas e dependiam de estruturas algébricas altamente específicas ou suposições fortes:

Naor-Reingold (1997, 2004): Construíram PRFs em $TC_0 \subseteq NC1$ a partir de Decisional Diffie-Hellman (DDH) e fatoração.
Banerjee-Peikert-Rosen (2012): Construíram PRFs em $TC_0$ a partir de Ring-LWE, mas exigiram uma razão módulo-ruído superpolinomial.
Ding-Jain-Komargodski (2025): Construíram PRFs a partir de variantes estruturadas de Learning Parity with Noise (LPN), como SeededLPN ou Ring-LPN.

O desafio central é alcançar PRFs computáveis em NC1 a partir de suposições padrão (LWE com razão módulo-ruído polinomial, LPN padrão e Computational Diffie-Hellman) sem depender de variantes estruturadas ou parâmetros superpolinomiais.

2. Metodologia

O artigo introduz uma abordagem de duas frentes: uma transformação genérica preservadora de profundidade de WPRFs para PRFs fortes, e novas construções de WPRFs (ou sintetizadores) eficientes em profundidade a partir de suposições padrão.

2.1 Tapering-GGM: Uma Transformação Genérica

Os autores propõem uma nova adaptação da construção de árvore GGM, denominada Tapering-GGM, que eleva uma WPRF a uma PRF forte enquanto preserva a profundidade do circuito de avaliação.

O Mecanismo de Afunilamento (Tapering): Em uma árvore GGM padrão, o tamanho do estado permanece constante e a profundidade acumula linearmente com o número de níveis da árvore ( $\ell \cdot d_{WPRF}$ ). No Tapering-GGM, o tamanho do estado diminui geometricamente em cada nível. Se o parâmetro de segurança no nível $i$ é $\lambda^{(i)}$ , os autores definem $\lambda^{(i)} = \lambda^{2^{-i+1}}$ . Consequentemente, a profundidade da chamada da WPRF no nível $i$ , denotada por $d(\lambda^{(i)})$ , diminui geometricamente.
Análise de Profundidade: Se a WPRF base possui profundidade $d(\lambda) = \Theta(\log \lambda)$ , a profundidade total da construção Tapering-GGM torna-se:
$d_{total} = O(\log \lambda) + \sum_{i=1}^{\ell} d(\lambda^{(i)}) \approx O(\log \lambda) + \sum_{i=1}^{\ell} \log(\lambda^{2^{-i+1}}) = O(\log \lambda)$
Este decaimento geométrico garante que a profundidade total permaneça $O(d(\lambda))$ , mantendo a construção dentro de NC1 se a WPRF de entrada estiver em NC1.
Desafios de Segurança e Soluções:
- Desafio: À medida que a árvore se aprofunda, o parâmetro de segurança $\lambda^{(i)}$ torna-se pequeno (subpolinomial), potencialmente quebrando a segurança computacional da WPRF subjacente.
- Solução 1 (Hashing): A entrada é primeiro processada via uma função de hash paritária independente (pairwise independent). Isso garante que, com alta probabilidade, as consultas do adversário sejam "fragmentadas" (mapeadas para caminhos distintos) dentro dos primeiros $O(\log_\Delta q)$ níveis, onde o parâmetro de segurança ainda é polinomial.
- Solução 2 (Uniformidade de Chave): Para níveis abaixo do ponto de fragmentação, a construção depende de segurança informacional. Os autores exigem que a WPRF seja chave-uniforme (independente de 1 vez). Se o estado no nível de fragmentação for pseudoaleatório, a composição subsequente de transformações chave-uniformes mapeia esse estado para uma saída perfeitamente uniforme, independentemente da dureza computacional das WPRFs de nível inferior.

2.2 Construções de WPRF Eficientes em Profundidade

Os autores instanciam o framework Tapering-GGM com novas construções de WPRF a partir de suposições padrão:

A partir de LWE (Learning With Errors):
- Os autores constroem a primeira NC1 WPRF a partir de LWE padrão com uma razão módulo-ruído polinomial ( $\alpha = n^{-\epsilon}$ ).
- Ferramenta Técnica Principal: Um Amostrador Gaussiano Arredondado (Rounded Gaussian Sampler) computável em profundidade $O(\text{poly}(\log \log \lambda))$ . Eles aproximam a transformada de Box-Muller usando aproximações polinomiais de baixa profundidade para $\ln$ , $\cos$ e iteração de Newton para raízes quadradas.
- Construção: Eles empregam um paradigma de encadeamento (inspirado em Kim [Kim20]). A construção calcula produtos internos mascarados de LWE camada por camada. Os bits de ordem superior da saída de uma camada amostra deterministicamente a distribuição de erro para a próxima camada. A limitação do amostrador de erro garante estabilidade, permitindo que a prova de segurança proceda via híbridos.
A partir de LPN (Learning Parity with Noise):
- Os autores aproveitam um resultado recente de Ding, Jain e Komargodski [DJK25] que fornece WPRFs em NC1 a partir de LPN padrão (ruído arbitrário de inverso polinomial).
- Ao combinar isso com o Tapering-GGM, eles obtêm as primeiras NC1 PRFs a partir de LPN padrão, eliminando a necessidade de variantes estruturadas (ex: Ring-LPN).
A partir de CDH (Computational Diffie-Hellman):
- Os autores observam que o Tapering-GGM requer, na verdade, um primitivo mais fraco que uma WPRF: um Sintetizador (onde o conjunto de entrada é oculto ao adversário).
- Eles instanciam a transformação utilizando a construção de sintetizador Naor-Reingold [NR95, NR99], que é computável em NC1 sob a suposição CDH. Isso resulta nas primeiras NC1 PRFs a partir de CDH, melhorando as construções anteriores baseadas em DDH.

3. Principais Contribuições

Transformação Genérica Preservadora de Profundidade: Uma transformação de caixa preta que converte qualquer WPRF (ou sintetizador) computável em profundidade $d(\lambda) = \Omega(\log \lambda)$ em uma PRF forte computável em profundidade $O(d(\lambda))$ . Isso resolve a barreira genérica que impedia NC1 PRFs a partir de suposições padrão.
NC1 PRFs de LWE Padrão: A primeira construção de PRFs em NC1 a partir de LWE com uma razão ruído-módulo polinomial ( $\alpha = n^{-\epsilon}$ ), resolvendo um problema aberto explicitamente enunciado nas notas de aula de Vaikuntanathan. Isto baseia-se na dureza de GapSVP com fatores de aproximação polinomial.
NC1 PRFs de LPN Padrão: A primeira construção de NC1 PRFs a partir da suposição LPN padrão, eliminando a necessidade de variantes estruturadas como Ring-LPN ou Sparse LPN.
NC1 PRFs de CDH: A primeira construção de NC1 PRFs a partir da suposição Computational Diffie-Hellman, melhorando o resultado de 30 anos da Naor-Reingold que dependia do decisional DDH mais forte.
Amostrador Gaussiano de Baixa Profundidade: Um novo circuito determinístico para amostragem de erros gaussianos arredondados em profundidade $O(\text{poly}(\log \log \lambda))$ , que é um componente crítico para a WPRF baseada em LWE.

4. Resultados

O artigo estabelece os seguintes resultados concretos:

Teorema: Se existem WPRFs em NC1, então existem PRFs em NC1.
Corolário (LWE): Assumindo que a suposição LWE se mantém para a razão ruído-módulo $\alpha = n^{-\epsilon}$ , existem PRFs em NC1.
Corolário (LPN): Assumindo que a suposição LPN se mantém para a probabilidade de ruído $\mu = n^{-\epsilon}$ , existem PRFs em NC1.
Corolário (CDH): Assumindo que a suposição CDH se mantém, existem PRFs em NC1.
Corolário (GapSVP): Assumindo que GapSVP é difícil de aproximar dentro de um fator $\tilde{O}(n^{1+\epsilon})$ , existem PRFs em NC1.

5. Significância

O artigo afirma resolver vários problemas abertos de longa data na complexidade de primitivos criptográficos. Ao desacoplar a profundidade de avaliação da PRF da natureza sequencial da transformação GGM, os autores demonstram que PRFs fortes podem ser construídas a partir de uma ampla gama de suposições padrão sem sacrificar a eficiência paralela.

Especificamente, o trabalho:

Remove a dependência de Ring-LWE e parâmetros superpolinomiais para NC1 PRFs, movendo-se para LWE padrão com parâmetros polinomiais.
Remove a dependência de variantes de LPN estruturado, movendo-se para LPN padrão.
Enfraquece a suposição de dureza para PRFs baseadas em CDH de DDH para CDH.
Provê um framework genérico (Tapering-GGM) que pode elevar qualquer candidato existente de log-profundidade de WPRF (ex: [ABG+14], [AR16]) em uma PRF de log-profundidade, desde que a suposição subjacente se mantenha.

Os autores posicionam este trabalho como um passo fundamental para entender a complexidade paralela da criptografia, com implicações para protocolos de computação segura, teoria do aprendizado (via conexões entre PRF versus aprendizagem) e metacomplexidade.